A full NT-step infeasible interior-point algorithm for semidefinite optimization
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 533-545.

In this paper, a full Nesterov–Todd-step infeasible interior-point algorithm is presented for semidefinite optimization (SDO) problems. In contrast of some classical interior-point algorithms for SDO problems, this algorithm does not need to perform computationally expensive calculations for centering steps which are needed for classical interior-point methods. The convergence analysis of the algorithm is shown and it is also proved that the complexity bound of the algorithm coincides with the currently best iteration bound obtained by infeasible interior-point algorithms for this class of optimization problems.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016043
Classification : 90C51, 90C22
Mots-clés : Semidefinite optimization, infeasible interior-point method, convergence analysis, polynomial complexity
Pirhaji, Mohammad 1 ; Mansouri, Hosseino 1 ; Zangiabadi, Maryam 1

1 Department of Applied Mathematics, Faculty of Mathematical Science, Shahrekord University, P.O. Box 115, Shahrekord, Iran.
@article{RO_2017__51_3_533_0,
     author = {Pirhaji, Mohammad and Mansouri, Hosseino and Zangiabadi, Maryam},
     title = {A full {NT-step} infeasible interior-point algorithm for semidefinite optimization},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {533--545},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {3},
     year = {2017},
     doi = {10.1051/ro/2016043},
     mrnumber = {3661368},
     zbl = {1387.90274},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2016043/}
}
TY  - JOUR
AU  - Pirhaji, Mohammad
AU  - Mansouri, Hosseino
AU  - Zangiabadi, Maryam
TI  - A full NT-step infeasible interior-point algorithm for semidefinite optimization
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 533
EP  - 545
VL  - 51
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2016043/
DO  - 10.1051/ro/2016043
LA  - en
ID  - RO_2017__51_3_533_0
ER  - 
%0 Journal Article
%A Pirhaji, Mohammad
%A Mansouri, Hosseino
%A Zangiabadi, Maryam
%T A full NT-step infeasible interior-point algorithm for semidefinite optimization
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 533-545
%V 51
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2016043/
%R 10.1051/ro/2016043
%G en
%F RO_2017__51_3_533_0
Pirhaji, Mohammad; Mansouri, Hosseino; Zangiabadi, Maryam. A full NT-step infeasible interior-point algorithm for semidefinite optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 533-545. doi : 10.1051/ro/2016043. http://www.numdam.org/articles/10.1051/ro/2016043/

F. Alizadeh, J.P. Haeberly and M. Overton, Primal-dual interior-point methods for semidefnite programming: Convergence rates, stability and numerical results. SIAM J. Optim. 8 (1998) 746–768. | DOI | MR | Zbl

Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101–128. | DOI | MR | Zbl

E. de Klerk, Aspects of Semidefinite Programming: Interior Point Methods and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002). | MR | Zbl

M. El Ghami, New primal-dual interior-point methods based on kernel functions. Ph.D thesis, Delft University of Technology (2005).

C. Helmberg, F. Rendl, R.J. Vanderbei and H. Wolkowicz, An interior-point method for semidefnite programming. SIAM J. Optim. 6 (1996) 342–361. | DOI | MR | Zbl

R.A. Horn and C.R. Johnson, Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991). | MR

B. Kheirfam, A new infeasible interior-point algorithm with full Nesterov−Todd step for semidefinite optimization. Iranian J. Operat. Res. 4 (2013) 88–107. | MR

M. Kojima, M. Shindoh and S. Hara, Interior point methods for the monotone linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997) 86–125. | DOI | MR | Zbl

M. Kojima, M. Shida and S. Shindoh, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math. Program. 80 (1998) 129–160. | DOI | MR | Zbl

Z.Y. Liu and W.Y. Sun, A full NT-step infeasible interior-point algorithm for SDP based on kernel functions. Appl. Math. Comput. 217 (2011) 4990–4999. | MR | Zbl

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

H. Mansouri, Full-Newton step infeasible interior-point algorithm for SDO problems. Kybernetika 48 (2012) 907–923. | MR | Zbl

H. Mansouri and C. Roos, A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization. J. Numer. Algor. 52 (2009) 225–255. | DOI | MR | Zbl

H. Mansouri, M. Zangiabadi and M. Arzani, A Modified Infeasible-Interior-Point Algorithm for Linear Optimization Problems. J. Optim. Theory Appl. 166 (2015) 605–618. | DOI | MR | Zbl

R.D.C. Monterio, Primal-dual path-following algorithm for semidefinite programming. SIAM J. Optim. 7 (1997) 663–678. | DOI | MR | Zbl

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

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

C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear programming. SIAM J. Optim. 16 (2006) 1110–1136. | DOI | MR | Zbl

C. Roos, An improved and simplified full-Newton step O(n) infeasible interior-point method for linear optimization. SIAM J. Optim. 25 (2015) 102–114. | DOI | MR | Zbl

G.Q. Wang, Y.Q. Bai, X.Y. Gao and D.Z. Wang, Improved Complexity Analysis of Full NesterovTodd Step Interior-Point Methods for Semidefinite Optimization. J. Optim. Theory Appl. 165 (2015) 242–262. | DOI | MR

H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of semidefinite programming: theory, Algorithms and Applications. Kluwer, Norwell, MA (1999). | MR | Zbl

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

L.P. Zhang, L.M. Sun and Y.H. Xu, Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming. Optimization 62 (2013) 169–191. | DOI | MR | Zbl

Cité par Sources :