A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

By Xinyuan Zhao, Defeng Sun, Kim-Chuan Toh. SIAM Journal on Optimization, 2010

443 citations recorded by the source corpus.

We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems. Numerical experiments on a variety of large-scale SDP problems with the matrix dimension $n$ up to $4,110$ and the number of equality constraints $m$ up to $2,156,544$ show that the proposed method is very efficient. We are also able to solve the SDP problem fap36 (with $n=4,110$ and $m=1,154,467$) in the Seventh DIMACS Implementation Challenge much more accurately than in previous attempts.

View Paper: https://www.semanticscholar.org/paper/4e896d53b69966931525e375e72bb7e2c953a55e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2013, methodology): “’ There are several other methods that share similar characteristics, such as [55–62], as well as some techniques for solving the split-feasibility problem [35].”
Randomized Iterative Methods for Linear Systems (2015, unknown): “For instance, in the ﬁeld of large scale optimization, there is a growing interest in inexact and approximate Newton-type methods for [7, 11, 1, 40, 39, 13], which can beneﬁt from fast subroutines for calculating approximate solutions of linear systems.”
A feasible method for optimization with orthogonality constraints (2012, methodology): “2 were taken from the recent work [38], in which the resulted SDPs were solved by a specialized numerical method tailored from algorithms in [35, 62]”
Alternating direction augmented Lagrangian methods for semidefinite programming (2010, methodology): “Since running SDPNAL on “fap25” and “fap36” is very time consuming (for example, in the results reported in [35], SDPNAL took more than 65 hours to solve problem “fap36”), we did not run SDPNAL on our own computer on these two problems and the results presented here were taken from Table 3 in [35].”