Optimization Online


A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

Xinyuan Zhao (g0500493***at***nus.edu.sg)
Defeng Sun (matsundf***at***nus.edu.sg)
Kim-Chuan Toh (mattohkc***at***nus.edu.sg)

Abstract: 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 SDPs 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 previous attempts.

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: 02/03/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society