A Squared Smoothing Newton Method for Semidefinite Programming

被引:0
作者
Liang, Ling [1 ]
Sun, Defeng [2 ]
Toh, Kim-Chuan [3 ,4 ]
机构
[1] Univ Maryland, Dept Math, College Pk, MD 20742 USA
[2] Hong Kong Polytech Univ, Dept Appl Math, Hung Hom, Hong Kong 999077, Peoples R China
[3] Natl Univ Singapore, Dept Math, Singapore 119076, Singapore
[4] Natl Univ Singapore, Inst Operat Res & Analyt, Singapore 119076, Singapore
关键词
semidefinite programming; smoothing Newton method; Huber function; nondegeneracy; AUGMENTED LAGRANGIAN METHOD; CONSTRAINT NONDEGENERACY; CONTINUATION METHODS; COMPLEMENTARITY; CONVERGENCE; RANK; REGULARIZATION; OPTIMIZATION; ALGORITHMS; BINARY;
D O I
10.1287/moor.2023.0311
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper proposes a squared smoothing Newton method via the Huber smoothing function for solving semidefinite programming problems (SDPs). We first study the fundamental properties of the matrix-valued mapping defined upon the Huber function. Using these results and existing ones in the literature, we then conduct rigorous convergence analysis and establish convergence properties for the proposed algorithm. In particular, we show that the proposed method is well-defined and admits global convergence. Moreover, under suitable regularity conditions, that is, the primal and dual constraint nondegenerate conditions, the proposed method is shown to have a super-linear convergence rate. To evaluate the practical performance of the algorithm, we conduct extensive numerical experiments for solving various classes of SDPs. Comparison with the state-of-the-art SDP solvers demonstrates that our method is also efficient for computing accurate solutions of SDPs.
引用
收藏
页数:36
相关论文
共 75 条
[1]   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
[2]   Complementarity and nondegeneracy in semidefinite programming [J].
Alizadeh, F ;
Haeberly, JPA ;
Overton, ML .
MATHEMATICAL PROGRAMMING, 1997, 77 (02) :111-128
[3]  
[Anonymous], 2013, Perturbation Analysis of Optimization Problems
[4]  
Boumal N, 2016, ADV NEUR IN, V29
[5]  
Boumal N, 2014, J MACH LEARN RES, V15, P1455
[6]   Local minima and convergence in low-rank semidefinite programming [J].
Burer, S ;
Monteiro, RDC .
MATHEMATICAL PROGRAMMING, 2005, 103 (03) :427-444
[7]   A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization [J].
Burer, S ;
Monteiro, RDC .
MATHEMATICAL PROGRAMMING, 2003, 95 (02) :329-357
[9]  
Caratheodory C., 1911, Rendiconti Del Circolo Matematico di Palermo, V32, P193, DOI DOI 10.1007/BF03014795
[10]   A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging [J].
Chambolle, Antonin ;
Pock, Thomas .
JOURNAL OF MATHEMATICAL IMAGING AND VISION, 2011, 40 (01) :120-145