Optimization Online


Approximate Versions of the Alternating Direction Method of Multipliers

Jonathan Eckstein (jeckstei***at***rci.rutgers.edu)
Wang Yao (yaowang74***at***gmail.com)

Abstract: We present three new approximate versions of alternating direction method of multipliers (ADMM), all of which require only knowledge of subgradients of the subproblem objectives, rather than bounds on the distance to the exact subproblem solution. One version, which applies only to certain common special cases, is based on combining the operator-splitting analysis of the ADMM with a relative-error proximal point algorithm of Solodov and Svaiter. A byproduct of this analysis is a new, relative-error version of the Douglas-Rachford splitting algorithm for monotone operators. The other two approximate versions of the ADMM are more general and based on the Lagrangian splitting analysis of the ADMM: one uses a summable absolute error criterion, and the other uses a relative error criterion and an auxiliary iterate sequence. We experimentally compare our new algorithms to an essentially exact form of the ADMM and to an inexact form that can be easily derived from prior theory (but again applies only to certain common special cases). These experiments show that our methods can significantly reduce total computational effort when iterative methods are used to solve ADMM subproblems.

Keywords: Convex optimization, decomposition, ADMM

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: RUTCOR, Rutgers University, December 2016

Download: [PDF]

Entry Submitted: 01/06/2016
Entry Accepted: 01/06/2016
Entry Last Modified: 06/17/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society