On the Asymptotic Superlinear Convergence of the Augmented Lagrangian Method for Semidefinite Programming with Multiple Solutions

Abstract

Solving large scale convex semidefinite programming (SDP) problems has long been a challenging task numerically. Fortunately, several powerful solvers including SDPNAL, SDPNAL+ and QSDPNAL have recently been developed to solve linear and convex quadratic SDP problems to high accuracy successfully. These solvers are based on the augmented Lagrangian method (ALM) applied to the dual problems with the subproblems being solved by semismooth Newton-CG methods. Noticeably, thanks to Rockafellar's general theory on the proximal point algorithms, the primal iteration sequence generated by the ALM enjoys an asymptotic Q-superlinear convergence rate under a second order sufficient condition {for the primal problem}. This second order sufficient condition implies that the primal problem has a unique solution, which can be restrictive in many applications. For gaining more insightful interpretations on the high efficiency of these solvers, in this paper we conduct an asymptotic superlinear convergence analysis of the ALM for convex SDP when the primal problem has multiple solutions (can be unbounded). Under a fairly mild second order growth condition, we prove that the primal iteration sequence generated by the ALM converges asymptotically Q-superlinearly, while the dual feasibility and the dual objective function value converge asymptotically R-superlinearly. Moreover, by studying the metric subregularity of the Karush-Kuhn-Tucker solution mapping, we also provide sufficient conditions to guarantee the asymptotic R-superlinear convergence of the dual iterate.

References in corpus (5)

• A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming
• QSDPNAL: A two-phase augmented Lagrangian method for convex quadratic semidefinite programming
• A Unified Approach to Error Bounds for Structured Convex Optimization Problems
• Characterization of the Robust Isolated Calmness for a Class of Conic Programming Problems

Cited by in corpus (10)

• QSDPNAL: A two-phase augmented Lagrangian method for convex quadratic semidefinite programming
• On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
• On efficiently solving the subproblems of a level-set method for fused lasso problems
• Efficient sparse semismooth Newton methods for the clustered lasso problem
• Quadratic growth conditions for convex matrix optimization problems associated with spectral functions
• Strong calmness of perturbed KKT system for a class of conic programming with degenerate solutions
• Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming
• KL property of exponent $1/2$ of quadratic functions under nonnegative zero-norm constraints and applications
• Critical Multipliers in Semidefinite Programming
• Computation of graphical derivatives of normal cone maps to a class of conic constraint sets