A new second-order corrector interior-point algorithm for semidefinite programming

被引：16
作者：
Liu, Changhe [1 ,2 ]
Liu, Hongwei [2 ]
机构：
[1] Henan Univ Sci & Technol, Dept Appl Math, Luoyang, Peoples R China
[2] Xidian Univ, Dept Math, Xian, Peoples R China
来源：
MATHEMATICAL METHODS OF OPERATIONS RESEARCH | 2012年 / 75卷 / 02期
基金：
中国国家自然科学基金;
关键词：
Semidefinite programming; Interior-point methods; Second-order methods; Polynomial complexity; CONVERGENCE;
D O I：
10.1007/s00186-012-0379-4
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we propose a second-order corrector interior-point algorithm for semidefinite programming (SDP). This algorithm is based on the wide neighborhood. The complexity bound is O(root nL) for the Nesterov-Todd direction, which coincides with the best known complexity results for SDP. To our best knowledge, this is the first wide neighborhood second-order corrector algorithm with the same complexity as small neighborhood interior-point methods for SDP. Some numerical results are provided as well.
引用
收藏
页码：165 / 183
页数：19
相关论文
共 32 条
[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]   Neighborhood-following algorithms for linear programming [J].
Ai, WB .
SCIENCE IN CHINA SERIES A-MATHEMATICS, 2004, 47 (06) :812-820
[3]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[4]   Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J].
Alizadeh, F ;
Haeberly, JPA ;
Overton, ML .
SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) :746-768
[5]  
[Anonymous], 1985, Matrix Analysis
[6]  
[Anonymous], 1999, SPRINGER SCI
[7]  
[Anonymous], 1991, THESIS U MINNESOTA M
[8]  
Boyd S., 1994, LINEAR MATRIX INEQUA
[9]   Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming [J].
Cartis, Coralia .
APPLIED NUMERICAL MATHEMATICS, 2009, 59 (05) :1110-1119
[10]  
de Klerk E., 2002, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications
1234