Optimization Online


On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

Wei Deng (wd5***at***rice.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: The formulation min f(x)+g(y) subject to Ax+By=b, where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous gradient. On this kind of problem, a very effective approach is the alternating direction method of multipliers (ADM or ADMM), which solves a sequence of f/g-decoupled subproblems. However, its effectiveness has not been matched by a provably fast rate of convergence; only sublinear rates such as O(1/k) and O(1/k^2) were recently established in the literature, though these rates do not require strict convexity. This paper shows that global linear convergence can be guaranteed under the above assumptions on strict convexity and Lipschitz gradient on one of the two functions, along with certain rank assumptions on A and B. The result applies to the generalized ADMs that allow the subproblems to be solved faster and less exactly in certain manners. In addition, the rate of convergence provides some theoretical guidance for optimizing the ADM parameters. In addition, this paper makes meaningful extensions to the existing global convergence theory of the generalized ADM.

Keywords: alternating direction method of multipliers, ADMM, linear convergence, sparse optimization, distributed optimization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Rice University CAAM Technical Report TR12-14

Download: [PDF]

Entry Submitted: 08/19/2012
Entry Accepted: 08/24/2012
Entry Last Modified: 02/22/2014

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