Subgradient Ascent for Non-Smooth Duals

In Lagrangian relaxation we form the dual function

$$g(\lambda) = \min_x L(x, \lambda) = \min_x \left[ c(x) + \lambda^T(Ax - b) \right],$$

where $\lambda \ge 0$ are the multipliers attached to relaxed inequality constraints $Ax \le b$.

For each fixed $x$, $L(x, \lambda)$ is affine in $\lambda$. Taking the pointwise minimum over $x$ of a family of affine functions produces a function that is concave and piecewise linear — it has kinks at every $\lambda$ where the minimizing $x$ switches. Ordinary gradient ascent fails at these kinks.

Instead we use a subgradient: a vector $s$ is a subgradient of the concave function $g$ at $\lambda$ if

$$g(\mu) \le g(\lambda) + s^T(\mu - \lambda) \quad \text{for all } \mu \ge 0.$$

Geometrically, $s$ defines a flat hyperplane that touches $g$ at $\lambda$ and lies on or above $g$ everywhere else.

Key fact. If $x^\star(\lambda)$ is any minimizer of $L(\,\cdot\,, \lambda)$, then

$$s \,=\, A x^\star(\lambda) - b$$

is a subgradient of $g$ at $\lambda$. The components of $s$ are exactly the constraint slacks evaluated at $x^\star$: $s_i > 0$ means relaxed constraint $i$ is violated, while $s_i < 0$ means it has slack.

Illustrative computation. Relax the single constraint $x_1 + 2x_2 \le 8$ with multiplier $\lambda \ge 0$. If at $\lambda = 1.5$ the Lagrangian minimizer is $x^\star = (3, 4)$, then

$$s = 3 + 2(4) - 8 = 3.$$

The positive sign says constraint 1 is currently violated, so raising $\lambda$ should tighten the dual bound.