Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming

被引:59
作者
Chan, Zi Xian [1 ]
Sun, Defeng [1 ,2 ]
机构
[1] Natl Univ Singapore, Dept Math, Singapore 117548, Singapore
[2] Natl Univ Singapore, Risk Management Inst, Singapore 117548, Singapore
关键词
semidefinite programming; constraint nondegeneracy; strong regularity; nonsingularity; variational analysis; quadratic convergence;
D O I
10.1137/070681235
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, and the nonsingularity of the corresponding Clarke's generalized Jacobian, at a KKT point, are all equivalent. Moreover, we prove the equivalence between each of these conditions and the nonsingularity of Clarke's generalized Jacobian of the smoothed counterpart of this nonsmooth system used in several globally convergent smoothing Newton methods. In particular, we establish the quadratic convergence of these methods under the primal and dual constraint nondegeneracies, but without the strict complementarity.
引用
收藏
页码:370 / 396
页数:27
相关论文
共 49 条
[1]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[2]   Complementarity and nondegeneracy in semidefinite programming [J].
Alizadeh, F ;
Haeberly, JPA ;
Overton, ML .
MATHEMATICAL PROGRAMMING, 1997, 77 (02) :111-128
[3]  
[Anonymous], 2003, J MATH SCI-U TOKYO, DOI DOI 10.1023/A:1022940300114
[4]  
Arnold V.I., 1971, R. Math. Surveys, V26, P29
[5]  
Bhatia R., 2013, MATRIX ANAL
[6]   Second order optimality conditions based on parabolic second order tangent sets [J].
Bonnans, JF ;
Cominetti, R ;
Shapiro, A .
SIAM JOURNAL ON OPTIMIZATION, 1999, 9 (02) :466-492
[7]   Sensitivity analysis of optimization problems under second order regular constraints [J].
Bonnans, JF ;
Cominetti, R ;
Shapiro, A .
MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (04) :806-831
[8]  
Bonnans JF., 2013, PERTURBATION ANAL OP
[9]   BACKWARD ERRORS FOR EIGENVALUE AND SINGULAR-VALUE DECOMPOSITIONS [J].
CHANDRASEKARAN, S ;
IPSEN, ICF .
NUMERISCHE MATHEMATIK, 1994, 68 (02) :215-223
[10]   Non-interior continuation methods for solving semidefinite complementarity problems [J].
Chen, X ;
Tseng, P .
MATHEMATICAL PROGRAMMING, 2003, 95 (03) :431-474