A newton-cg augmented lagrangian method for semidefinite programming

X.-Y. Zhao, Defeng Sun, K.-C. Toh

Research output: Journal article publicationJournal articleAcademic researchpeer-review

176 Citations (Scopus)

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 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. Copyright © 2010, Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)1737-1765
Number of pages29
JournalSIAM Journal on Optimization
Volume20
Issue number4
DOIs
Publication statusPublished - 29 Apr 2010
Externally publishedYes

Keywords

  • Augmented lagrangian
  • Iterative solver
  • Newton method
  • Semidefinite programming
  • Semismoothness

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this