  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-CG method for finding an
approximate SOSP of unconstrained optimization and show that it enjoys a
substantially better complexity than the Newton-CG method [56]. 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{\cal
O}(\epsilon^{-7/2})$ and an operation complexity of $\widetilde{\cal
O}(\epsilon^{-7/2}\min\{n,\epsilon^{-3/4}\})$ for finding an
$(\epsilon,\sqrt{\epsilon})$-SOSP of nonconvex equality constrained
optimization with high probability, which are significantly better than the
ones achieved by the proximal AL method [60]. Besides, we show that it has a
total inner iteration complexity of $\widetilde{\cal O}(\epsilon^{-11/2})$ and
an operation complexity of $\widetilde{\cal
O}(\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 ones in [56,60].

Optimization and Control;Machine Learning;Numerical Analysis;Numerical Analysis;Machine Learning