Dual Descent ALM and ADMM

Abstract

Classical primal-dual algorithms attempt to solve ${\max }_{\mu }{\min }_x\mathcal{L}(x,\mu )$ by alternatively minimizing over the primal variable $x$ through primal descent and maximizing the dual variable $\mu$ through dual ascent. However, when $\mathcal{L}(x,\mu )$ is highly nonconvex with complex constraints in $x$, the minimization over $x$ may not achieve global optimality, and hence the dual ascent step loses its valid intuition. This observation motivates us to propose a new class of primal-dual algorithms for nonconvex constrained optimization with the key feature to reverse dual ascent to a conceptually new dual descent, in a sense, elevating the dual variable to the same status as the primal variable. Surprisingly, this new dual scheme achieves some best iteration complexities for solving nonconvex optimization problems. In particular, when the dual descent step is scaled by a fractional constant, we name it scaled dual descent (SDD), otherwise, unscaled dual descent (UDD). For nonconvex multiblock optimization with nonlinear equality constraints, we propose SDD-ADMM and show that it finds an $\epsilon$-stationary solution in $\mathcal{O}({\epsilon }^{-4})$ iterations. The complexity is further improved to $\mathcal{O}({\epsilon }^{-3})$ and $\mathcal{O}({\epsilon }^{-2})$ under proper conditions. We also propose UDD-ALM, combining UDD with ALM, for weakly convex minimization over affine constraints. We show that UDD-ALM finds an $\epsilon$-stationary solution in $\mathcal{O}({\epsilon }^{-2})$ iterations. These complexity bounds for both algorithms either achieve or improve the best-known results in the ADMM and ALM literature. Moreover, SDD-ADMM addresses a long-standing limitation of existing ADMM frameworks.

References in corpus (15)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• Penalty Dual Decomposition Method For Nonsmooth Nonconvex Optimization
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• A two-level distributed algorithm for nonconvex constrained optimization
• Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs
• Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective
• Extending the ergodic convergence rate of the proximal ADMM
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing

Cited by in corpus (1)

• Global Complexity Bound of a Proximal ADMM for Linearly-Constrained Nonseperable Nonconvex Composite Programming