Geodesic
Full-Newton step infeasible interior-point algorithm for SDO problems
Kybernetika, Tome 48 (2012) no. 5, pp. 907-923 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the $\mu^+$-center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems.
In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the $\mu^+$-center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems.
Classification : 90C05, 90C51
Keywords: semidefinite optimization; infeasible interior-point method; primal-dual method; polynomial complexity; Newton-step; optimal solutions 
@article{KYB_2012_48_5_a5,
     author = {Mansouri, Hossein},
     title = {Full-Newton step infeasible interior-point algorithm for {SDO} problems},
     journal = {Kybernetika},
     pages = {907--923},
     year = {2012},
     volume = {48},
     number = {5},
     mrnumber = {3086859},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a5/}
}
TY  - JOUR
AU  - Mansouri, Hossein
TI  - Full-Newton step infeasible interior-point algorithm for SDO problems
JO  - Kybernetika
PY  - 2012
SP  - 907
EP  - 923
VL  - 48
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a5/
LA  - en
ID  - KYB_2012_48_5_a5
ER  - 
%0 Journal Article
%A Mansouri, Hossein
%T Full-Newton step infeasible interior-point algorithm for SDO problems
%J Kybernetika
%D 2012
%P 907-923
%V 48
%N 5
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a5/
%G en
%F KYB_2012_48_5_a5
Mansouri, Hossein. Full-Newton step infeasible interior-point algorithm for SDO problems. Kybernetika, Tome 48 (2012) no. 5, pp. 907-923. http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a5/

[1] Alizadeh, F.: Interior-point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (2006), 13-51. | DOI | MR | Zbl

[2] Helmberg, C.: Semidefinite Programming for Combinatorial Optimization. Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechink Berlin 2000.

[3] Horn, R. A., Johnson, C. R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge 1991. | MR | Zbl

[4] Klerk, E. de: Aspects of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht 2002. | MR | Zbl

[5] Kojima, M., Shida, M., Shindoh, S.: Local convergence of predictor-corrector infeasible interior-point algorithm for SDPs and SDLCPs. Math. Program. 80 (1998), 129-160. | DOI | MR

[6] Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Comput. Sci. 538, Springer, Berlin 1991. | DOI | MR | Zbl

[7] Luo, Z. Q., Sturm, J., Zhang, S. Z.: Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming. SIAM J. Optim. 8 (1998), 59-81. | DOI | MR | Zbl

[8] Lustig, I. J.: Feasible issues in a primal-dual interior point method for linear programming. Math. Program. 49 (1990/1991), 145-162. | DOI | MR

[9] Lütkepohl, H.: Handbook of Matrices. John Wiley \& Sons, Chichester 1996. | MR | Zbl

[10] Mansouri, H.: Full-Newton Step Interior-Point Methods for Conic Optimization. Ph.D. Thesis, Faculty of Mathematics and Computer Science, TU Delft, 2008.

[11] Mansouri, H., Roos, C.: A new full-Newton step $o(n)$ infeasible interior-point algorithm for semidefinite optimization. J. Numer. Algorithms 52 (2009), 2, 225-255. | DOI | MR | Zbl

[12] Mansouri, H., Zangiabadi, M.: New complexity analysis of full Nesterov-Todd steps for semidefinite optimization. Bull. Iranian Math. Soc. 1 (2011), 269-286. | MR

[13] Mansouri, H., Siyavash, T., Zangiabadi, M.: A path-following infeasible interior-point algorithm for semidefinite programming. Iranian J. Oper. Res. 3 (2012), 1, 11-30.

[14] Nesterov, Y. E., Todd, M. J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22 (1997), 1, 1-42. | DOI | MR | Zbl

[15] Nesterov, Y. E., Todd, M. J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 2, 324-364. | DOI | MR | Zbl

[16] Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002), 129-171. | DOI | MR | Zbl

[17] Potra, F. A., Sheng, R.: A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8 (1998), 1007-1028. | DOI | MR | Zbl

[18] Roos, C.: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136. | DOI | MR | Zbl

[19] Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley and Sons, Chichester 1997. (Second Edition Springer 2005.) | MR | Zbl

[20] Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht 2000. | MR | Zbl

[21] Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998), 365-386. | DOI | MR | Zbl