Self equivalence of the alternating direction method of multipliers

DOI10.1007/978-3-319-41589-5_5zbMATH Open1372.65186arXiv1407.7400OpenAlexW2113924882MaRDI QIDQ5350477FDOQ5350477

Authors: Ming Yan, Wotao Yin 

Publication date: 1 September 2017

Published in: Splitting Methods in Communication, Imaging, Science, and Engineering (Search for Journal in Brave)

Abstract: The alternating direction method of multipliers (ADM or ADMM) breaks a complex optimization problem into much simpler subproblems. The ADM algorithms are typically short and easy to implement yet exhibit (nearly) state-of-the-art performance for large-scale optimization problems. To apply ADM, we first formulate a given problem into the "ADM-ready" form, so the final algorithm depends on the formulation. A problem like $mbox{minimize}_{m}athbfxu(mathbfx)+v(mathbfCmathbfx)$ has six different "ADM-ready" formulations. They can be in the primal or dual forms, and they differ by how dummy variables are introduced. To each "ADM-ready" formulation, ADM can be applied in two different orders depending on how the primal variables are updated. Finally, we get twelve different ADM algorithms! How do they compare to each other? Which algorithm should one choose? In this paper, we show that many of the different ways of applying ADM are equivalent. Specifically, we show that ADM applied to a primal formulation is equivalent to ADM applied to its Lagrange dual; ADM is equivalent to a primal-dual algorithm applied to the saddle-point formulation of the same problem. These results are surprising since the primal and dual variables in ADM are seemingly treated very differently, and some previous work exhibit preferences in one over the other on specific problems. In addition, when one of the two objective functions is quadratic, possibly subject to an affine constraint, we show that swapping the update order of the two primal variables in ADM gives the same algorithm. These results identify the few truly different ADM algorithms for a problem, which generally have different forms of subproblems from which it is easy to pick one with the most computationally friendly subproblems.

Full work available at URL: https://arxiv.org/abs/1407.7400

Recommendations

• Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
• On the global and linear convergence of the generalized alternating direction method of multipliers
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• scientific article; zbMATH DE number 679861
• ADMM for multiaffine constrained optimization

zbMATH Keywords

alternating direction method of multipliersnumerical examplesalgorithmlarge-scale optimization problems

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06)

Cited In (22)

• Douglas-Rachford splitting and ADMM for pathological convex optimization
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
• ARock: an algorithmic framework for asynchronous parallel coordinate updates
• A Parallel Douglas–Rachford Algorithm for Minimizing ROF-like Functionals on Images with Values in Symmetric Hadamard Manifolds
• Accelerated stochastic Peaceman-Rachford method for empirical risk minimization
• A proximal point analysis of the preconditioned alternating direction method of multipliers
• A primal-dual flow for affine constrained convex optimization
• On the order of the operators in the Douglas-Rachford algorithm
• On the global and linear convergence of the generalized alternating direction method of multipliers
• Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
• Equivalent resolvents of Douglas-Rachford splitting and other operator splitting algorithms: a unified degenerate proximal point analysis
• Split-Douglas--Rachford Algorithm for Composite Monotone Inclusions and Split-ADMM
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis
• A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
• Alternating direction method for separable variables under pair-wise constraints
• Conic optimization via operator splitting and homogeneous self-dual embedding
• A generalized forward-backward splitting operator: degenerate analysis and applications
• Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms

This page was built for publication: Self equivalence of the alternating direction method of multipliers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5350477)