A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

Xinyuan Zhao (g0500493nus.edu.sg)
Defeng Sun (matsundfnus.edu.sg)
Kim-Chuan Toh (mattohkcnus.edu.sg)

Abstract: We consider a Newton-CG augmented Lagrangian (NCGAL) method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of the method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems in the NCGAL method, 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 SDPs with matrix dimensions up to 1,600 and number of equality constraints up to 1,283,258 show that the proposed method is very efficient.

Keywords: Semidefinite programming, Augmented Lagrangian, Semismoothness, Newton's method, Iterative solver

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: preprint, National University of Singapore, March 2008.

Download: [PDF]

Entry Submitted: 03/13/2008
Entry Accepted: 03/13/2008
Entry Last Modified: 03/24/2008

Modify/Update this entry