A NEWTON-CG BASED BARRIER METHOD FOR FINDING A SECOND-ORDER STATIONARY POINT OF NONCONVEX CONIC OPTIMIZATION WITH COMPLEXITY GUARANTEES

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 based barrier method for finding an (Formula Presented)-SOSP of this problem. Our method not only is implementable but also achieves an iteration complexity of (Formula Presented), which matches the best known iteration complexity of second-order methods for finding an (Formula Presented)-SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of (Formula Presented) Cholesky factorizations and (Formula Presented) other fundamental operations, is also established for our method, where n is the problem dimension and (Formula Presented) represents (Formula Presented) with logarithmic terms omitted.