On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming

Ying Cui, Defeng Sun, Kim Chuan Toh

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

Due to the possible lack of primal-dual-type error bounds, it was not clear whether the Karush–Kuhn–Tucker (KKT) residuals of the sequence generated by the augmented Lagrangian method (ALM) for solving convex composite conic programming (CCCP) problems converge superlinearly. In this paper, we resolve this issue by establishing the R-superlinear convergence of the KKT residuals generated by the ALM under only a mild quadratic growth condition on the dual of CCCP, with easy-to-implement stopping criteria for the augmented Lagrangian subproblems. This discovery may help to explain the good numerical performance of several recently developed semismooth Newton-CG based ALM solvers for linear and convex quadratic semidefinite programming.

Original languageEnglish (US)
Pages (from-to)381-415
Number of pages35
JournalMathematical Programming
Volume178
Issue number1-2
DOIs
StatePublished - Nov 1 2019
Externally publishedYes

Bibliographical note

Funding Information:
The authors would like to thank the associate editor and two anonymous referees for their helpful comments on improving the quality of this paper. Thanks also go to Professor Terry Rockafellar for his comments on the unboundedness of the Lagrangian multipliers of the KKT solution mapping of the original form leading to the current form of Example 2 during his visit to the Hong Kong Polytechnic University.

Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

Keywords

  • Augmented Lagrangian method
  • Convex composite conic programming
  • Implementable criteria
  • Quadratic growth condition
  • R-superlinear

Fingerprint

Dive into the research topics of 'On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming'. Together they form a unique fingerprint.

Cite this