Optimization

Augmented Lagrangian

Combine a quadratic penalty with explicit multiplier estimates to reach feasibility without driving the penalty weight to infinity.

Best of both worlds

Pure penalty methods need the penalty weight to grow unboundedly, causing ill-conditioning. The augmented Lagrangian method (also called the method of multipliers) adds a Lagrange-multiplier term to the penalized objective, so exact feasibility is reached at a finite, moderate penalty. This keeps the subproblems well conditioned.

The augmented function

For equality constraints h(x) = 0, the augmented Lagrangian is L_A(x, lambda, mu) = f(x) + lambda dot h(x) + (mu/2) ||h(x)||^2. It combines the Lagrangian (with multiplier estimate lambda) and a quadratic penalty (with weight mu). Minimizing over x, then updating lambda, drives constraints to zero.

The multiplier update

Minimize L_A over x with current lambda and mu to get x_k.
Update the multipliers: lambda_{k+1} = lambda_k + mu * h(x_k).
Increase mu only if feasibility is not improving fast enough.
Repeat until constraints are satisfied to tolerance.

Why the multiplier update works

The gradient update lambda_{k+1} = lambda_k + mu h(x_k) is a steepest-ascent step on the dual function. As lambda converges to the true optimal multipliers, the quadratic penalty no longer needs to grow, so mu stays bounded and conditioning stays manageable, unlike pure penalty methods.

ADMM and applications

The alternating direction method of multipliers (ADMM) is an augmented Lagrangian scheme that splits variables into blocks minimized alternately, which suits large distributed and machine-learning problems. Augmented Lagrangian solvers such as LANCELOT and ALGENCAN handle large constrained nonlinear programs robustly.

python

lam = 0.0; mu = 10.0
for _ in range(K):
    x = minimize_x(lambda x: f(x) + lam*h(x) + 0.5*mu*h(x)**2)
    lam = lam + mu*h(x)

The augmented Lagrangian and ADMM solve large constrained and distributed optimization problems that arise in design and data analysis.