A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees
This work addresses a theoretical optimization problem for researchers in mathematical optimization, providing complexity guarantees for a specific class of nonconvex problems, but it is incremental as it extends known methods to constrained settings.
The paper tackles the problem of finding an approximate second-order stationary point for nonconvex conic optimization by proposing a Newton-CG based barrier method, achieving an iteration complexity of O(ε^{-3/2}) and matching the best known complexity for unconstrained cases.
In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an $(ε,\sqrtε)$-SOSP of this problem. Our method is not only implementable, but also achieves an iteration complexity of ${\cal O}(ε^{-3/2})$, which matches the best known iteration complexity of second-order methods for finding an $(ε,\sqrtε)$-SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of ${\cal O}(ε^{-3/2})$ Cholesky factorizations and $\widetilde{\cal O}(ε^{-3/2}\min\{n,ε^{-1/4}\})$ other fundamental operations, is also established for our method.