论文标题
基于牛顿-CG的屏障方法，用于查找具有复杂性的非凸圆锥优化的二阶固定点
A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees
论文作者
论文摘要
在本文中，我们考虑找到非凸锥优化的近似二阶固定点（SOSP），该点在仿射子空间和凸锥的交点上最小化了两倍的可微分函数。特别是，我们提出了一个基于牛顿 - 偶联的梯度（Newton-CG）的屏障方法，用于查找此问题的$（ε，\sqrtε）$ - SOSP。我们的方法不仅可以实现，而且还达到了$ {\ cal o}（ε^{ - 3/2}）$的迭代复杂性，它匹配了找到$（ε，\sqrtε）$的二阶方法的最著名的迭代复杂性 - 未约束的非convex optavex的$ - sosp。操作复杂性，由$ {\ cal o}（ε^{ - 3/2}）$ cholesky factorizations和$ \ wideTilde {\ cal o}（\ cal o}（ε^{ - 3/2} \ min \ min \ min \ {
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.
