A Brief Overview of ADMM

The alternating direction method of multipliers (ADMM) has emerged as an important algorithm for convex optimization. Here are some of my notes on how it works. If this piques your interest, I highly recommend you watch this lecture by Stephen Boyd, the OG of ADMM (slides here).

As Boyd puts it: “The alternating direction method of multipliers (ADMM) is an algorithm that solves convex optimization problems by breaking them into smaller pieces, each of which are then easier to handle.”

We will consider the problem

minimizef(x)+g(z)subject toAx+Bz=c

where f and g are convex.

Many practical problems can be written this way. Frequently, f is smooth and easy to minimize, and g is a rule or a penalty: e.g. keep inside a set, constrain most entries to be zero, keep a matrix positive semidefinite.

How ADMM Works

The way ADMM works is to introduce a dual variable y, with one entry per row of the constraint, and a penalty parameter ρ>0. Then we iteratively update x, z, and y. At each iteration we do the following:

The x-step. Fix z and y and minimize over x alone. We consider f and not g.

xk+1:=argminx⁡f(x)+(yk)TAx+ρ2‖Ax+Bzk−c‖22

The z-step. The same thing for z, using the x we just computed. Now we consider g and not f.

zk+1:=argminz⁡g(z)+(yk)TBz+ρ2‖Axk+1+Bz−c‖22

The y-step. Now we update y using whatever is left of the constraint violation. We scale it by ρ.

yk+1:=yk+ρ(Axk+1+Bzk+1−c)

As Boyd notes, you can think of y as a vector of prices for violating the constraint Ax+Bz=c. In the x-step, f is the focus, but we pay the current price for the “x share” of the violation, plus a quadratic penalty. In the z-step, g does the same. In the y-step, we raise the price wherever the constraint is still violated. Note that y stops changing only when Ax+Bz=c.

In certain cases it’s far, far easier to solve these subproblems, as compared to the original problem. And sometimes we can monitor our progress and stop when we have a “good enough” solution. These properties can make ADMM a very desirable approach in many cases.

So let’s take a step back and walk through how we derive the approach above. Then we will go through an example.

Derivation

The first step is to form the Augmented Lagrangian:

Lρ(x,z,y)=f(x)+g(z)+yT(Ax+Bz−c)+ρ2‖Ax+Bz−c‖22

The first three terms are the usual Lagrangian. The last is the “augmented” part. It is zero at every point that satisfies the constraint, so it does not change the solution. What it buys us is subproblems that behave well even when f and g are not strictly convex, which is exactly the situation when g is a rule like “stay inside this set.” This is basically the “good news” on Boyd’s slide 11.

The older method of multipliers minimizes Lρ over x and z together, then raises the price of violating the constraint: y:=y+ρ(Ax+Bz−c). The problem with this is that it’s hard to minimize over both together: that’s what we wanted to avoid in the first place. This is why in ADMM we break it up: minimize over x, then over z, once each, and update y right away. This going back and forth is the “alternating direction” part.

xk+1:=argminx⁡Lρ(x,zk,yk)zk+1:=argminz⁡Lρ(xk+1,z,yk)yk+1:=yk+ρ(Axk+1+Bzk+1−c)

There are more details but I will refer you to the slides or the talk if you are interested. The point is that ADMM converges to the optimal value under reasonable conditions. It’s good for situations where you want to get pretty good accuracy on big problems.

Example

Claude came up with a great example, so here we go. Let’s find the lowest point of a tilted bowl inside a box. The bowl is

f(x)=12(x−a)TQ(x−a),Q=[2112],a=[20]

and the box C is −1≤x1≤1, −1≤x2≤1. The bottom of the bowl is at a, which is outside the box. The obvious guess is the point of the box closest to a, which is (1,0). That guess is wrong. The off-diagonal entries of Q tilt the bowl, and sliding up the wall to x⋆=(1,12) lowers f from 1 to 34.

A square box C with the elliptical contour lines of a tilted bowl whose bottom, a = (2, 0), lies outside the box to the right. The point of the box nearest a is (1, 0); the lowest point of the bowl inside the box is x* = (1, 1/2), higher up the same wall.
The contour through the answer just touches the box. The nearest point to the bottom of the bowl is not the lowest one.

Writing it in ADMM form

Let g be the function that is 0 inside the box and +∞ outside. Then our problem is to minimize f(x)+g(x). Give g its own copy of the variable (z), and require the copies to match:

minimizef(x)+g(z)subject tox−z=0

That is our template with A=I, B=−I, and c=0. Neither piece is hard by itself, which is why ADMM is great for this example.

The three steps

Plug A, B and c into the steps from before.

The x-step. We minimize f(x)+(yk)Tx+ρ2‖x−zk‖22. This is quadratic, so set the gradient to zero: Q(x−a)+yk+ρ(x−zk)=0. That gives

xk+1:=(Q+ρI)−1(Qa+ρzk−yk)

a 2 × 2 linear solve: easy.

The z-step. We minimize g(z)−(yk)Tz+ρ2‖xk+1−z‖22. Completing the square, this is the same as minimizing

g(z)+ρ2‖z−(xk+1+1ρyk)‖22

TL;DR: find the point of the box closest to xk+1+yk/ρ. For a box that means clipping each coordinate to [−1,1]:

zk+1:=clip⁡(xk+1+1ρyk,−1,1)

The bowl is nowhere to be seen.

The y-step.

yk+1:=yk+ρ(xk+1−zk+1)

Running it

Take ρ=1 and start from z0=y0=(0,0). The first iteration can be done by hand:

  • x-step: solve [3113]x=Qa=[42], so x1=(1.25,0.25). This is outside the box.
  • z-step: clip (1.25,0.25) to get z1=(1,0.25).
  • y-step: y1=(0,0)+(1.25,0.25)−(1,0.25)=(0.25,0).

Here is how it continues:

kxkzkyk‖xk−zk‖2
1(1.2500, 0.2500)(1, 0.2500)(0.2500, 0)0.25
2(1.5000, 0.2500)(1, 0.2500)(0.7500, 0)0.50
3(1.3125, 0.3125)(1, 0.3125)(1.0625, 0)0.31
5(1.1094, 0.4219)(1, 0.4219)(1.3594, 0)0.11
10(1.0059, 0.4951)(1, 0.4951)(1.4932, 0)0.0059
20(1.0000, 0.5000)(1, 0.5000)(1.5000, 0)0.00001

In the second iteration x actually moves farther outside the box. The x-step still wants the bottom of the bowl, and a price of 0.25 is not nearly enough to talk it out of that. So the y-step raises the price again, and again, each time by the amount x still overshoots the wall. Meanwhile z stays on the wall and slides up it. After 24 iterations both residuals are below 10−6.

You can step through it yourself:

ADMM · a tilted bowl inside a set
Iteration
0
Starting from z = y = (0, 0). Press Step to run one iteration: an x-step, a z-step and a y-step.
x
–
z
(0.0000, 0.0000)
y
(0.0000, 0.0000)
Primal residual ‖x − z‖
–
Dual residual ρ‖z − z_prev‖
–
110⁻⁴10⁻⁸both below this line: stop11020residuals by iteration appear here
Each iteration is an x-step, a z-step and a y-step. The dashed line is the gap between x and z, the primal residual. The two arrows at x are the forces on it; the dual residual is how far they are from cancelling.

Example in Python

import numpy as np

Q = np.array([[2.0, 1.0], [1.0, 2.0]])
a = np.array([2.0, 0.0])
rho = 1.0
z = np.zeros(2)
y = np.zeros(2)

for k in range(1, 25):
    x = np.linalg.solve(Q + rho * np.eye(2), Q @ a + rho * z - y)  # x-step: a linear solve
    z_prev = z
    z = np.clip(x + y / rho, -1, 1)                                # z-step: clip to the box
    y = y + rho * (x - z)                                          # y-step: reprice
    r = np.linalg.norm(x - z)                                      # primal residual
    s = rho * np.linalg.norm(z - z_prev)                           # dual residual
    print(k, x, z, y, r, s)

In future posts, I will apply ADMM to an old friend: QAP.