A new wide-neighborhood predictor-corrector interior-point method for semidefinite optimization

被引:0
作者
Kheirfam, Behrouz [1 ]
Osmanpour, Naser [2 ]
机构
[1] Azarbaijan Shahid Madani Univ, Dept Math, Tabriz, Iran
[2] Univ Guilan, Fac Math Sci, Rasht, Iran
关键词
Semidefinite optimization; Wide neighborhood; Predictor-corrector methods; Interior-point methods; Polynomial complexity; CENTRAL PATH; ALGORITHM; CONVERGENCE;
D O I
10.1007/s12190-021-01579-w
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we present a new predictor-corrector interior-point algorithm based on a wide neighborhood for semidefinite optimization. The proposed algorithm is a Mizuno-Todd-Ye predictor-corrector type and uses the Nesterov-Todd (NT) search direction in predictor step and a commutative class of search directions involving Helmberg-Kojima-Monteiro and NT directions in corrector step. We show that the proposed algorithm at every both predictor and corrector steps reduces the duality gap. The method enjoys the iteration complexity of O (root n kappa L-infinity), which matching to the currently best known iteration bound for wide neighborhood algorithms. Numerical results also confirm the algorithm is reliable and promising.
引用
收藏
页码:1365 / 1385
页数:21
相关论文
共 28 条
[1]   An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP [J].
Ai, WB ;
Zhang, SZ .
SIAM JOURNAL ON OPTIMIZATION, 2005, 16 (02) :400-417
[2]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[3]  
ALIZADEH F, 1991, COMBINATORIAL OPTIMI
[4]  
Boyd S., 1994, LINEAR MATRIX INEQUA, V15
[5]  
de Klerk Etienne., 2002, APPL OPTIMIZATION, V65, DOI DOI 10.1007/B105286
[6]   A new O(√nL)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming [J].
Feng, Zengzhe ;
Fang, Liang .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2014, 256 :65-76
[7]   On the convergence of the central path in semidefinite optimization [J].
Halická, M ;
de Klerk, E ;
Roos, C .
SIAM JOURNAL ON OPTIMIZATION, 2002, 12 (04) :1090-1099
[8]   An interior-point method for semidefinite programming [J].
Helmberg, C ;
Rendl, F ;
Vanderbei, RJ ;
Wolkowicz, H .
SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) :342-361
[9]   PREDICTOR-CORRECTOR METHOD FOR LINEAR COMPLEMENTARITY-PROBLEMS WITH POLYNOMIAL COMPLEXITY AND SUPERLINEAR CONVERGENCE [J].
JI, J ;
POTRA, FA ;
HUANG, S .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1995, 85 (01) :187-199
[10]  
Kheirfam B., 2015, Iranian J Oper Res, V6, P1