Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates

Understand

We develop two new variants of alternating direction methods of multipliers (ADMM) and two parallel primal-dual decomposition algorithms to solve a wide range class of constrained convex optimization problems.

• Our approach relies on a novel combination of the augmented Lagrangian framework, partial alternating/linearization scheme, Nesterov's acceleration technique, and adaptive strategy.
• The proposed algorithms have the following new features compared to existing ADMM variants.
• First, they have a Nesterov's acceleration step on the primal variables instead of the dual ones as in several ADMM variants.