A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

Abstract

In this paper we consider finding a second-order stationary point (SOSP) of noncon-vex equality constrained optimization when a nearly feasible point is known. In particular, we firstpropose a new Newton-conjugate gradient (Newton-CG) method for finding an approximate SOSPof unconstrained optimization and show that it enjoys a substantially better complexity than theNewton-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 find-ing an approximate SOSP of nonconvex equality constrained optimization, in which the proposedNewton-CG method is used as a subproblem solver. We show that under a generalized linear indepen-dence 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 non-convex equality constrained optimization with high probability, which are significantly better thanthe 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 anoperation complexity of \widetilde \scrO (\epsilon 11/2 min\{ n, \epsilon 5/4\} ) when the GLICQ does not hold. To the best of ourknowledge, all the complexity results obtained in this paper are new for finding an approximate SOSPof nonconvex equality constrained optimization with high probability. Preliminary numerical resultsalso demonstrate the superiority of our proposed methods over the other competing algorithms.