A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization

Abstract

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 $\epsilon$-stationary solution of the linearly constrained nonconvex minimization problem within $\mathcal{O}(1/{\epsilon }^2)$ iterations, which is the best known iteration complexity for this class of nonconvex problems.

22 pages

References in corpus (1)

• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria

Cited by in corpus (2)

• Dual Descent ALM and ADMM
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems