ADMM and Primal-Dual Methods — Mathematics Knowledge System

Overview

The Alternating Direction Method of Multipliers (ADMM) and primal-dual methods are splitting algorithms for solving convex optimization problems with separable structure: min f(x) + g(z) subject to Ax + Bz = c. ADMM splits the problem into alternating updates of x and z (exploiting separability) while updating dual variables. Primal-dual methods simultaneously update primal and dual variables. These methods are widely used in distributed optimization, compressed sensing, image processing, and machine learning. ADMM was introduced by Glowinski-Marrocco (1975) and Gabay-Mercier (1976), and popularized in machine learning by Boyd et al. (2011).

Intuition

Suppose you want to minimize f(x) + g(z) subject to x = z (a constraint linking two blocks). The augmented Lagrangian adds a penalty: L_rho(x,z,y) = f(x) + g(z) + y^T(x-z) + (rho/2)||x-z||^2. ADMM alternates: (1) x-update: minimize over x with z,y fixed (which might have a closed form due to f's structure); (2) z-update: minimize over z with x,y fixed (using g's structure); (3) y-update: y <- y + rho*(x-z) (dual ascent). The splitting exploits the structure of f and g separately, avoiding the difficulty of minimizing f+g jointly.

Formal Definition

Definition

For the separable problem min f(x) + g(z) s.t. Ax + Bz = c (primal variables x, z; dual variable y), the augmented Lagrangian is L_rho(x,z,y) = f(x) + g(z) + <y, Ax+Bz-c> + (rho/2)||Ax+Bz-c||^2. ADMM updates: x_{k+1} = argmin_x L_rho(x, z_k, y_k); z_{k+1} = argmin_z L_rho(x_{k+1}, z, y_k); y_{k+1} = y_k + rho*(A*x_{k+1} + B*z_{k+1} - c). Under mild convexity, ADMM converges: primal residuals r_k = A*x_k + B*z_k - c -> 0 and dual residuals s_k = rho*A^T*B*(z_k - z_{k-1}) -> 0.

x^{k+1} = \arg\min_x\, f(x) + \langle y^k, Ax\rangle + \tfrac{\rho}{2}\|Ax + Bz^k - c\|^2

ADMM x-update

z^{k+1} = \arg\min_z\, g(z) + \langle y^k, Bz\rangle + \tfrac{\rho}{2}\|Ax^{k+1} + Bz - c\|^2

ADMM z-update

y^{k+1} = y^k + \rho(Ax^{k+1} + Bz^{k+1} - c)

ADMM dual update

\min_{x,z}\; f(x)+g(z) \equiv \max_y\min_{x,z}\; L_\rho(x,z,y)

Saddle-point formulation

Notation

Notation	Meaning
$L_\rho(x,z,y)$	Augmented Lagrangian with penalty parameter rho
$\rho > 0$	Penalty/step-size parameter in ADMM
$r^k, s^k$	Primal and dual residuals at iteration k
$y$	Dual variable (Lagrange multiplier for Ax+Bz=c)

Theorems

Theorem 1: ADMM Convergence Theorem

For the problem min f(x) + g(z) s.t. Ax + Bz = c with f, g closed convex proper, A and B with full column rank, and assuming a saddle point exists, ADMM converges: (1) primal residual r^k = Ax^k + Bz^k - c -> 0; (2) dual residual s^k = rho*A^T B*(z^k - z^{k-1}) -> 0; (3) objective f(x^k) + g(z^k) -> f* + g* (optimal value). Convergence is O(1/k) in objective value for general convex f, g; linear under strong convexity.

Theorem 2: Chambolle-Pock Primal-Dual Algorithm

For the saddle-point problem min_x max_y <Kx, y> + f(x) - g*(y) (with K a linear operator, g* the convex conjugate of g), the Chambolle-Pock algorithm alternates: x^{k+1} = prox_{tau f}(x^k - tau*K^T y^k); y^{k+1} = prox_{sigma g*}(y^k + sigma*K*x-bar^{k+1}); x-bar^{k+1} = x^{k+1} + theta*(x^{k+1} - x^k). For tau*sigma*||K||^2 < 1 and theta in [0,1], this converges at rate O(1/N) in the primal-dual gap.

Theorem 3: ADMM for Distributed Optimization

For minimizing sum_{i=1}^m f_i(x) (consensus problem), the distributed ADMM formulation min_{x_i, z} sum_i f_i(x_i) s.t. x_i = z allows each agent i to update x_i locally (using only f_i) while the central variable z coordinates. The z-update is z = (1/m) sum_i (x_i + y_i/rho) (average of local estimates). This achieves linear convergence for strongly convex f_i, enabling distributed machine learning.

Worked Examples

1
Introduce z = x. LASSO: min f(x) + g(z) s.t. x = z, where f(x) = (1/2)||Ax-b||^2 and g(z) = lambda||z||_1.
2
x-update: x^{k+1} = argmin_x {(1/2)||Ax-b||^2 + (rho/2)||x-z^k+y^k/rho||^2}. This is a ridge regression: x^{k+1} = (A^T A + rho I)^{-1}(A^T b + rho(z^k - y^k/rho)).
$x^{k+1} = (A^\top A + \rho I)^{-1}(A^\top b + \rho z^k - y^k)$
3
z-update: z^{k+1} = argmin_z {lambda||z||_1 + (rho/2)||z - x^{k+1} - y^k/rho||^2} = S_{lambda/rho}(x^{k+1} + y^k/rho) (soft thresholding).
$z^{k+1} = S_{\lambda/\rho}(x^{k+1} + y^k/\rho)$
4
y-update: y^{k+1} = y^k + rho*(x^{k+1} - z^{k+1}).

✓ Answer

ADMM for LASSO: alternately solve a ridge regression (x-step, linear system) and apply soft-thresholding (z-step), updating the dual variable y at each iteration.

Practice Problems

Hardfree response

Explain the role of the penalty parameter rho in ADMM and its effect on convergence.

Common Mistakes

Common Mistake

Thinking ADMM always converges faster than gradient descent.

ADMM's advantage is not raw speed but the ability to handle non-smooth objectives (via splitting) and exploit separable structure. For smooth strongly convex problems, ADMM typically has linear convergence but may be slower than accelerated gradient methods (FISTA, L-BFGS). For problems with non-smooth structure (LASSO, SVM, total variation), ADMM often outperforms gradient-based methods because the subproblems can be solved exactly using proximal operators.

Quiz

In ADMM, the z-update often has a closed form because:

It involves only the dual variable yIt minimizes an augmented Lagrangian in z alone, which for structured g (like L1) has a closed-form proximal operatorIt is always a linear systemz and x are updated simultaneously

Historical Background

The method of multipliers (augmented Lagrangian) was introduced independently by Hestenes (1969) and Powell (1969). Glowinski and Marrocco (1975) and Gabay and Mercier (1976) introduced ADMM as a splitting extension. The primal-dual framework was developed by Chambolle and Pock (2011) for non-smooth problems. Boyd, Parikh, Chu, Peleato, and Eckstein's 2011 survey made ADMM widely known in the machine learning community. ADMM convergence theory was strengthened by He-Yuan and Deng-Yin (2012).

1969
Hestenes and Powell independently introduce the augmented Lagrangian method
Magnus Hestenes, Michael Powell
1976
Gabay-Mercier introduce ADMM as alternating splits of augmented Lagrangian
Daniel Gabay, Bertrand Mercier
2011
Boyd et al. survey popularizes ADMM in machine learning and signal processing
Stephen Boyd
2011
Chambolle-Pock primal-dual algorithm for non-smooth saddle-point problems
Antonin Chambolle, Thomas Pock

Summary

ADMM solves min f(x)+g(z) s.t. Ax+Bz=c by alternating x-update, z-update, and dual update.
Augmented Lagrangian: L_rho = f(x)+g(z)+<y, Ax+Bz-c>+(rho/2)||Ax+Bz-c||^2.
x-update and z-update often have closed forms (linear system, prox operator).
Convergence: O(1/k) for general convex; linear for strongly convex; widely used in distributed optimization.

References

BookBoyd, S. et al. Distributed Optimization and Statistical Learning via ADMM. Foundations and Trends in ML, 2011.
BookBeck, A. First-Order Methods in Optimization. SIAM, 2017.
WebsiteWikipedia -- Augmented Lagrangian method