Self Equivalence of the Alternating Direction Method of Multipliers

Abstract

In this paper, we show interesting self equivalence results for the alternating direction method of multipliers (ADM or ADMM). Specifically, we show that ADM on a primal problem is equivalent to ADM on its Lagrange dual problem; ADM is equivalent to a primal-dual algorithm applied to a saddle- point formulation of the problem; when one of the two objective functions is quadratic with an a ne domain, we can swap the update order of the two variables in ADM and obtain an equivalent algorithm. An example in extended monotropic programming is given to demonstrate that the primal-dual algorithm may be preferable over the other equivalent algorithms for its lower per-iteration complexity and, in the setting of distributed computation, better load balancing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 11, 2014
Accession Number
ADA610274

Entities

People

  • Ming Yan
  • Wotao Yin

Organizations

  • University of California, Los Angeles

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Equations
  • Hilbert Space
  • Identities
  • Image Processing
  • Information Operations
  • Iterations
  • Mathematical Analysis
  • Mathematics
  • Numerical Analysis
  • Optimization
  • Sequences
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Operations Research