field notes · lagrangian duality

Why the Dual Is Always a Dome

A close look at one specific problem — minimize \((x-2)^2+(y-2)^2\) subject to \(x+y-2<0\) — that reveals a fact with nothing to do with quadratics at all.

the kernel

The dual function is the lowest point of a whole family of straight lines — one line per point in the primal domain. However you tilt and place a bunch of straight lines, the shape traced by their lowest points is always a dome, never a saddle. That's the entire reason. The fact that \(f\) is a quadratic bowl never enters into it.

01

A bowl, fenced off

\(f(x,y)=(x-2)^2+(y-2)^2\) is a paraboloid bowl with its bottom sitting at \((2,2)\). The constraint \(x+y-2<0\) fences off half the plane — everything on one side of the diagonal line \(x+y=2\) is off-limits.

Notice immediately: the bowl's true bottom, \((2,2)\), gives \(x+y-2=2\), which is on the wrong side of the fence. So the constrained problem is genuinely constrained — the fence is doing real work, not just standing there decoratively.

The bowl and the fence live · drag the point
point: (x, y) f(x,y) = – x+y−2 = – –
contours of f feasible region (x+y<2) unconstrained minimum
Drag the parchment-colored point anywhere. Watch how the fence and the bowl pull in different directions.
02

Freeze the point, and the constraint becomes a price

Pick any single spot \((x,y)\) and hold it fixed. The Lagrangian charges a price \(\lambda\) for standing on the wrong side of the fence:

\[ L(x,y,\lambda) = f(x,y) + \lambda\,(x+y-2) \]

For a fixed point, this is embarrassingly simple: it's just a straight line in \(\lambda\). The intercept is \(f(x,y)\) — what you pay at zero price. The slope is \(x+y-2\) — how far over the fence you are.

One point → one line linked · drag the point
L(λ) = –
Drag the point on the left. Its line on the right just tilts and slides — it never curves. A single point can only ever draw a straight line.
03

The dual is the floor beneath all of these lines

The dual function doesn't fix one point — it asks, for every price \(\lambda\), which point is cheapest right now?

\[ g(\lambda) = \min_{x,y} L(x,y,\lambda) \]

That means \(g(\lambda)\) is the pointwise minimum, over every point in the plane, of a straight line. Add lines below, one per point. Watch what their lower boundary does as more arrive.

This is the whole mechanism. It works whether \(f\) is a tidy bowl or a landscape of nonsense — the envelope of a pile of lines is always a dome.
The lower envelope of every possible line staged · add lines
one line per point (x,y) the envelope g(λ)
Press "Add a line" to place the first point's line.
04

Solve it exactly, and watch the touch-point trace the roof

For this particular \(f\) we can do the inner minimization with calculus. Setting \(\partial L/\partial x = \partial L/\partial y = 0\):

\[ x^*(\lambda) = y^*(\lambda) = 2 - \tfrac{\lambda}{2} \]

Substituting back gives a closed form for the dome we built numerically above:

\[ g(\lambda) = 2\lambda - \tfrac{\lambda^2}{2}, \qquad g''(\lambda) = -1 \]

Drag \(\lambda\) below. Watch the optimal point slide along the diagonal in the bowl, and watch its line rotate until it exactly grazes the envelope at that \(\lambda\) — because that's the definition of the envelope: the one line, among infinitely many, that happens to be lowest right there.

Why is this the Legendre transform?
Minimizing a convex function against a linear "bribe" term is exactly the Legendre transform: \(\min_x\big[(x-2)^2+\lambda x\big] = -\lambda^2/4 + \text{const}\). Legendre transforms of convex functions are always concave in the dual variable — same fact, different clothes. Each coordinate here contributes one \(-\lambda^2/4\) term; summing the \(x\) and \(y\) contributions and folding in the \(-2\lambda\) from the constant term gives \(g(\lambda)=2\lambda-\lambda^2/2\).
The optimal point and its tangent line live · drag λ
x*=y* = – g(λ) = – g'(λ) = –
At λ*=2, g'(λ)=0 — the dual optimum. Check: primal optimum is x=y=1, f(1,1)=2, and g(2)=2. No gap.
05

Putting it together

Restate the kernel with the specifics now filled in: \(g(\lambda)=\min_{x,y}L(x,y,\lambda)\) is a minimum, taken over \((x,y)\), of a function that is affine in \(\lambda\) for every fixed \((x,y)\). A pointwise minimum of affine functions is concave — full stop, no assumptions on \(f\) required. Step 3 showed it by brute force (pile up lines, watch the dome emerge); Step 4 confirmed it in closed form for this specific quadratic.

What quadratics do buy you, separately, is strong duality — the dome's peak, \(g(2)=2\), exactly matches the primal optimum \(f(1,1)=2\). That's Slater's condition doing its job (a convex feasible region with an interior point), and it's a second, independent fact. Swap \(f\) for something nonconvex and \(g(\lambda)\) is still, provably, a dome — you'd just lose the guarantee that its peak reaches the true primal answer.

The one-sentence version

The dual is concave because it's a minimum over a family of straight lines — and no family of straight lines can ever have a lower envelope shaped like anything but a dome.

Where this shows up

  • Every Lagrangian dual in convex optimization — SVMs, LASSO, portfolio problems — inherits this for free, regardless of how the primal looks.
  • Lagrangian relaxation for integer/combinatorial programs: the primal is wildly nonconvex, yet the dual bound \(g(\lambda)\) is still concave and can be maximized with plain gradient ascent.
  • The same min-of-affine-family argument is why value functions in convex MDPs and support functions in convex geometry are concave/convex "for free."