论文标题
绑定的全局双误差及其应用于线性约束非convex优化的分析
A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
论文作者
论文摘要
错误结合分析使用最佳残差估算了一个点与优化问题的解决方案集的距离，是一阶优化算法分析的强大工具。在本文中，我们使用全局误差约束分析来研究线性约束的非凸最小化问题的一阶算法的迭代复杂性。我们通过使用新颖的``分解''技术来为此非凸问题的正则版本开发一个全局双重误差分析。配备了这种全局双重错误绑定，我们证明了一种适当设计的原始双二阶方法可以生成$ \ Mathcal {o}（O}（1/ε^2）内的线性约束非convex最小化问题的$ε$ - 平稳解决方案，这是该类别非conconve问题的最佳迭代复杂性。
Error bound analysis, which estimates the distance of a point to the solution set of an optimization problem using the optimality residual, is a powerful tool for the analysis of first-order optimization algorithms. In this paper, we use global error bound analysis to study the iteration complexity of a first-order algorithm for a linearly constrained nonconvex minimization problem. we develop a global dual error bound analysis for a regularized version of this nonconvex problem by using a novel ``decomposition'' technique. Equipped with this global dual error bound, we prove that a suitably designed primal-dual first order method can generate an $ε$-stationary solution of the linearly constrained nonconvex minimization problem within $\mathcal{O}(1/ε^2)$ iterations, which is the best known iteration complexity for this class of nonconvex problems.
