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.

arXiv comment22 pages

References in corpus (4)

• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria
• k-Means Clustering Is Matrix Factorization
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization

Cited by in corpus (7)

• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Dual Descent ALM and ADMM
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems