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.
Accepté le :
DOI : 10.1051/ro/2016043
Keywords: Semidefinite optimization, infeasible interior-point method, convergence analysis, polynomial complexity
Pirhaji, Mohammad 1 ; Mansouri, Hosseino 1 ; Zangiabadi, Maryam 1
@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},
year = {2017},
publisher = {EDP Sciences},
volume = {51},
number = {3},
doi = {10.1051/ro/2016043},
mrnumber = {3661368},
zbl = {1387.90274},
language = {en},
url = {https://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 - https://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 https://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
, and , Primal-dual interior-point methods for semidefnite programming: Convergence rates, stability and numerical results. SIAM J. Optim. 8 (1998) 746–768. | MR | Zbl | DOI
, and , A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101–128. | MR | Zbl | DOI
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).
, , and , An interior-point method for semidefnite programming. SIAM J. Optim. 6 (1996) 342–361. | MR | Zbl | DOI
R.A. Horn and C.R. Johnson, Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991). | MR
, A new infeasible interior-point algorithm with full Nesterov−Todd step for semidefinite optimization. Iranian J. Operat. Res. 4 (2013) 88–107. | MR
, and , Interior point methods for the monotone linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997) 86–125. | MR | Zbl | DOI
, and , Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math. Program. 80 (1998) 129–160. | MR | Zbl | DOI
and , A full NT-step infeasible interior-point algorithm for SDP based on kernel functions. Appl. Math. Comput. 217 (2011) 4990–4999. | MR | Zbl
, and , Superlinear convergence of a symmetric primaldual path following algorithm for semidefinite programming. SIAM J. Optim. 8 (1998) 59-81. | MR | Zbl | DOI
, Full-Newton step infeasible interior-point algorithm for SDO problems. Kybernetika 48 (2012) 907–923. | MR | Zbl
and , A new full-Newton step infeasible interior-point algorithm for semidefinite optimization. J. Numer. Algor. 52 (2009) 225–255. | MR | Zbl | DOI
, and , A Modified Infeasible-Interior-Point Algorithm for Linear Optimization Problems. J. Optim. Theory Appl. 166 (2015) 605–618. | MR | Zbl | DOI
, Primal-dual path-following algorithm for semidefinite programming. SIAM J. Optim. 7 (1997) 663–678. | MR | Zbl | DOI
and , Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22 (1997) 1-42. | MR | Zbl | DOI
, and , Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002) 129–171. | MR | Zbl | DOI
, A full-Newton step infeasible interior-point algorithm for linear programming. SIAM J. Optim. 16 (2006) 1110–1136. | MR | Zbl | DOI
, An improved and simplified full-Newton step infeasible interior-point method for linear optimization. SIAM J. Optim. 25 (2015) 102–114. | MR | Zbl | DOI
, , and , Improved Complexity Analysis of Full NesterovTodd Step Interior-Point Methods for Semidefinite Optimization. J. Optim. Theory Appl. 165 (2015) 242–262. | MR | DOI
H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of semidefinite programming: theory, Algorithms and Applications. Kluwer, Norwell, MA (1999). | MR | Zbl
, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998) 365–386. | MR | Zbl | DOI
, and , Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming. Optimization 62 (2013) 169–191. | MR | Zbl | DOI
Cité par Sources :
