Lagrangian Duality

Hard constraints become prices. The Lagrangian adds each violation times its price, and the best prices certify how good any solution can be.

Pricing the bound constraint turns the primal minimum 4 into a dual maximum 4, so the best price 4 certifies optimality with zero gap.

Why Does This Exist?

Constrained problems are hard to certify. Claiming 4 is optimal needs proof that no feasible 3.9 exists, and enumerating feasibility is hopeless at scale. Duality manufactures certificates cheaply: any dual-feasible price vector yields a lower bound with no enumeration.

This page is the pricing view with gaps and certificates. The equality-only tangency mechanism lives in Lagrange multipliers. The full constrained-to-dual story with the SVM dual and the kernel trick lives in constrained optimisation and duality. The four-condition inequality test lives in KKT conditions and is checked step by step in optimality conditions. Convexity background lives in convex optimization, and the splitting algorithm that climbs the dual lives in ADMM.

The prerequisite is one idea: pricing a violation means charging $\lambda_i \ge 0$ per unit of $f_i(x) > 0$ , where $f_i$ is the $i$ -th inequality function and $\lambda_i$ its price. Feasible points pay nothing extra and infeasible ones pay up, so the dual searches prices that make even the cheapest $x$ expensive.

Think of It Like This

Parking fines instead of gates

A lot owner can gate every spot or set fines so parking elsewhere beats violating. Gating is the primal route: enforce each constraint directly. Fines are the dual route: price each violation and let drivers sort themselves out.

Any fine schedule yields a revenue lower bound without checking each car, which is weak duality. Well-set fines empty violations exactly, which is strong duality with zero gap. Weak fines leave tolerated cheating, which is a positive gap.

Where it stops: fines need collection power. An ungoverned lot ignores prices, and in optimisation that missing power is a failed constraint qualification, where no price schedule certifies the optimum.

How It Actually Works

For minimise $f_0(x)$ subject to $f_i(x) \le 0$ and $h_j(x) = 0$ , where $f_0$ is the objective, each $f_i$ is one inequality, and each $h_j$ is one equality, form the Lagrangian with prices $\lambda \ge 0$ and $\nu$ free:

L(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_j \nu_j h_j(x)

The dual function is the cheapest Lagrangian over $x$ , written $g(\lambda, \nu) = \inf_x L$ , and the dual problem maximises $g$ over $\lambda \ge 0$ . Every dual-feasible pair lower-bounds the primal minimum $p^{\star}$ , so the dual optimum $d^{\star}$ satisfies $d^{\star} \le p^{\star}$ , which is weak duality and always holds. The saddle view reads $\sup_{\lambda \ge 0, \nu} \inf_x L \le \inf_x \sup_{\lambda \ge 0, \nu} L$ : pricing before choosing beats choosing before pricing.

When the gap closes

Strong duality $d^{\star} = p^{\star}$ needs convexity plus a regularity condition. Slater's condition is the common one: a strictly feasible convex point with $f_i(x) < 0$ for non-affine inequalities. Then the KKT conditions hold and complementary slackness prices exactly the active walls. Dual ascent, augmented Lagrangians, and decomposition climb $g$ when the primal splits across blocks, which is the mechanism behind ADMM.

Worked example

Minimise $x^2$ subject to $x \ge 2$ , written as $2 - x \le 0$ . The primal optimum is $p^{\star} = 4$ at $x = 2$ .

The Lagrangian with price $\lambda \ge 0$ is $L = x^2 + \lambda(2 - x)$ . Minimising over $x$ sets $2x - \lambda = 0$ , so $x = \lambda/2$ , and the dual function is:

g(\lambda) = 2\lambda - \lambda^2/4

Maximise: $g' = 2 - \lambda/2 = 0$ gives $\lambda^{\star} = 4$ and $d^{\star} = 8 - 4 = 4$ . Gap zero, matching the diagram bars at 4 and 4. The price reads as sensitivity: loosening to $x \ge 1.9$ drops the optimum to $1.9^2 = 3.61$ , a fall of $0.39$ against the first-order prediction $4 \times 0.1 = 0.4$ .

Code

The snippet scans the dual curve with only the standard library and confirms the hand calculation.

1def g(lam: float) -> float:2    return 2 * lam - lam ** 2 / 43
4
5grid = [i * 0.5 for i in range(17)]  # 0.0 to 8.06best = max(grid, key=g)7print(round(g(best), 2))  # -> 4.08print(round(best, 1))  # -> 4.09print(round(1.9 ** 2, 2))  # -> 3.6110print(round(2.0 ** 2, 2))  # -> 4.0

Dual peak 4.0 at price 4.0 matches primal 4.0, and the relaxed bound 3.61 confirms the sensitivity reading.

Watch Out For

Assuming zero gap without convexity

On non-convex problems the dual can sit far below the primal, and integer programs routinely show large gaps. Rounding the dual up as optimal ships points certified by nothing.

The symptom is a dual value quoted as the answer with no gap reported. Quote $d^{\star}$ as a bound only, measure $p^{\star} - d^{\star}$ , and switch to branch-and-bound or tracked convex relaxations when the gap will not close.

Dualising into a harder algorithm

Moving coupling constraints into prices can destroy separability a solver exploited, or create a nonsmooth dual needing bundle or augmented methods. Naive dual ascent then crawls or oscillates on step sizes.

The symptom is dual values that bounce instead of climbing. Match the method to dual smoothness with subgradient or augmented Lagrangian steps such as ADMM, and treat the step size as the first suspect when values oscillate.

The Quick Version

The Lagrangian prices violations and the dual maximum always lower-bounds the primal minimum.
The scalar example minimising $x^2$ above 2 gives primal 4 and dual 4 at price 4 with zero gap.
Convexity plus Slater closes the gap, and then KKT holds with priced active walls.
Each price is a sensitivity: $\lambda_i$ values relaxing one unit of its wall.
Non-convex gaps stay open, so report dual values as bounds with measured gaps.
Climb nonsmooth duals with stabilised methods such as ADMM, not raw ascent.