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 \((\epsilon,\sqrt{\epsilon })\) -SOSP of this problem. Our method not only is implementable but also achieves an iteration complexity of \({\mathcal{O}}(\epsilon^{-3/2})\) , which matches the best known iteration complexity of second-order methods for finding an \((\epsilon,\sqrt{\epsilon })\) -SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of \({\mathcal{O}}(\epsilon^{-3/2})\) Cholesky factorizations and \(\widetilde{{\mathcal{O}}}(\epsilon^{-3/2}\min \{n,\epsilon^{-1/4}\})\) other fundamental operations, is also established for our method, where n is the problem dimension and \({\widetilde{\mathcal{O}}}(\cdot )\) represents \({\mathcal{O}}(\cdot )\) with logarithmic terms omitted.Keywordsnonconvex conic optimizationsecond-order stationary pointbarrier methodNewton–conjugate gradient methoditeration complexityoperation complexityMSC codes49M0549M1565F1090C0690C60