A Newton-cg Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees

Chuan He, Zhaosong Lu, Ting Kei Pong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-conjugate gradient (Newton-CG) method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method in [C. W. Royer, M. O'Neill, and S. J. Wright, Math. Program., 180 (2020), pp. 451-488]. We then propose a Newton-CG based augmented Lagrangian (AL) method for finding an approximate SOSP of nonconvex equality constrained optimization, in which the proposed Newton-CG method is used as a subproblem solver. We show that under a generalized linear independence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of widetilde scrO (epsilon 7/2) and an operation complexity of widetilde scrO (epsilon 7/2 min{ n, epsilon 3/4} ) for finding an (epsilon ,surd epsilon )-SOSP of nonconvex equality constrained optimization with high probability, which are significantly better than the ones achieved by the proximal AL method in [Y. Xie and S. J.Wright, J. Sci. Comput., 86 (2021), pp. 1-30]. In addition, we show that it has a total inner iteration complexity of widetilde scrO (epsilon 11/2) and an operation complexity of widetilde scrO (epsilon 11/2 min{ n, epsilon 5/4} ) when the GLICQ does not hold. To the best of our knowledge, all the complexity results obtained in this paper are new for finding an approximate SOSP of nonconvex equality constrained optimization with high probability. Preliminary numerical results also demonstrate the superiority of our proposed methods over the other competing algorithms.

Original languageEnglish
Pages (from-to)1734-1766
Number of pages33
JournalSIAM Journal on Optimization
Volume33
Issue number3
DOIs
Publication statusPublished - 2023

Keywords

  • augmented Lagrangian method
  • iteration complexity
  • Newton conjugate gradient method
  • nonconvex equality constrained optimization
  • operation complexity
  • second-order stationary point

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A Newton-cg Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees'. Together they form a unique fingerprint.

Cite this