Lagrangian Duality, in depth: the dual function, weak and strong duality, Slater and KKT, duality gaps and Lagrangian relaxation

The Lagrangian and the dual function

Start with a problem in standard form: minimize f₀(x) subject to fᵢ(x) ≤ 0 for i = 1..m and hⱼ(x) = 0 for j = 1..p, with optimal value p*. Nothing is assumed about convexity yet. The Lagrangian attaches a multiplier to each constraint:

L(x, λ, ν) = f₀(x) + Σᵢ λᵢ fᵢ(x) + Σⱼ νⱼ hⱼ(x), with λ ≥ 0 and ν unrestricted.

Read it as a pricing scheme. Instead of forbidding constraint violations, the Lagrangian charges λᵢ per unit of violation of inequality i and pays λᵢ per unit of slack. The dual function is the best you can do under those prices, with x now free: g(λ, ν) = inf over x of L(x, λ, ν), possibly minus infinity.

The dual function is concave in (λ, ν) for any primal problem. For each fixed x, L(x, λ, ν) is an affine function of the multipliers; g is the pointwise infimum of a family of affine functions, and such an infimum is always concave. This is why the dual problem, maximize g(λ, ν) subject to λ ≥ 0, is a convex optimization problem even when the primal is a nonconvex mess or an integer program. You may not be able to evaluate g cheaply, but if you can, you can maximize it reliably.

Weak duality: a bound for free

Weak duality takes one line. Let x̃ be any feasible point and λ ≥ 0. Then fᵢ(x̃) ≤ 0 and hⱼ(x̃) = 0, so the penalty terms are at most zero, and L(x̃, λ, ν) ≤ f₀(x̃). The infimum over all x is at most the value at x̃, so g(λ, ν) ≤ f₀(x̃). Taking the best feasible x̃ and the best multipliers gives d* ≤ p*. The difference p* - d* is the duality gap.

Weak duality is what makes the dual useful in practice even when the gap is nonzero. Any dual-feasible (λ, ν) gives a lower bound on the primal minimum, and any feasible x gives an upper bound, so the pair brackets the optimum. A solver that has a feasible solution of cost 105 and a dual bound of 100 knows it is within 5% without ever finding the optimum; that is exactly how branch-and-bound prunes subtrees and how interior-point methods decide to stop.

Strong duality and Slater's condition

Strong duality, d* = p*, holds for convex problems (f₀ and fᵢ convex, hⱼ affine) under a constraint qualification. The usual one is Slater's condition: there exists a point that satisfies every inequality strictly, fᵢ(x) < 0, while meeting the equalities. Affine inequalities need only be satisfied, not strictly, which is why every feasible LP has strong duality. Without such a condition even convex problems can misbehave: minimize x subject to x² ≤ 0 has p* = 0 at x = 0, but no point satisfies x² < 0. Its dual function is g(λ) = -1/(4λ), which approaches 0 but never reaches it, so the gap is zero only in the limit and no optimal multiplier exists.

A worked convex case: minimize x₁² + x₂² subject to x₁ + x₂ ≥ 1, written as 1 - x₁ - x₂ ≤ 0. The Lagrangian is x₁² + x₂² + λ(1 - x₁ - x₂). Setting the gradient in x to zero gives x₁ = x₂ = λ/2, so g(λ) = λ²/2 + λ(1 - λ) = λ - λ²/2. This is concave, as promised, and maximized at λ = 1 with d* = 1/2. The primal optimum is x = (1/2, 1/2) with p* = 1/2. Slater holds (x = (1, 1) is strictly feasible), and the gap is zero.

KKT conditions: certificate and sensitivity

When strong duality holds and the optimum is attained, the primal optimum x* and dual optimum (λ*, ν*) satisfy four conditions, the Karush-Kuhn-Tucker (KKT) conditions:

1. Stationarity: ∇f₀(x*) + Σ λᵢ* ∇fᵢ(x*) + Σ νⱼ* ∇hⱼ(x*) = 0 (for differentiable problems).
2. Primal feasibility: fᵢ(x*) ≤ 0 and hⱼ(x*) = 0.
3. Dual feasibility: λ* ≥ 0.
4. Complementary slackness: λᵢ* fᵢ(x*) = 0 for each i: a constraint with slack has a zero price, and a constraint with a positive price is tight.

For convex problems the KKT conditions are also sufficient, which makes them a certificate: hand someone x* and λ*, and they can check optimality without solving anything. In the example, stationarity is 2x₁ - λ = 0 and 2x₂ - λ = 0, satisfied by x = (1/2, 1/2) and λ = 1; the constraint is tight, so complementary slackness holds.

The multiplier is also a sensitivity. If the right-hand side is perturbed to x₁ + x₂ ≥ 1 - u, the optimal value becomes p*(u) = (1 - u)²/2 and its derivative at u = 0 is -1 = -λ*. In general, dp*/duᵢ = -λᵢ* where p* is differentiable: the multiplier is the marginal value of relaxing that constraint, the same shadow price that appears in LP sensitivity analysis.

When the gap does not close: a knapsack

Without convexity, the gap can be strictly positive, and the integer case is the important one. Take a 0/1 knapsack: maximize 10a + 13b + 7c subject to 4a + 6b + 3c ≤ 8 with a, b, c in {0, 1}. Enumeration gives the optimum 17 (items a and c, weight 7). Dualize the capacity constraint with price λ ≥ 0. For a maximization the dual function is an upper bound:

g(λ) = 8λ + Σᵢ max(0, vᵢ - λwᵢ)

because for fixed λ the relaxed problem decomposes: take item i exactly when its value exceeds its priced weight. g is piecewise linear and convex (the mirror image of concave, since we maximized), with breakpoints at the value-to-weight ratios 13/6, 7/3 and 5/2. Its slope on each piece is 8 minus the weight of the items taken. Below 13/6 all three items are taken (slope 8 - 13 < 0); between 13/6 and 7/3 items a and c are taken (slope +1). So the minimum is at λ = 13/6, where g = 115/6 ≈ 19.17.

The best bound the dual can give is 19.17 against a true optimum of 17: a gap of 2.17. No choice of price closes it, because no price makes the relaxed problem choose a feasible, optimal set. The bound equals the LP relaxation's value, take a and c and one sixth of b, which is a general fact: when the relaxed subproblem's own constraints already have an integral LP description, the Lagrangian bound cannot beat the LP bound. Its value lies elsewhere: the relaxed problem can be far cheaper to solve than an LP of the same size.

Lagrangian relaxation with subgradients

Lagrangian relaxation is the algorithm built on this. Take a hard problem that would be easy without a few coupling constraints, move those constraints into the objective with multipliers, and search over the multipliers for the tightest bound. Because g is nonsmooth, the search uses subgradients: at a price λ with relaxed solution x(λ), the violation of the dualized constraint is a subgradient of g. For the knapsack upper bound, that violation is C minus the weight taken, and the update moves λ against it, raising the price when the relaxed solution overfills the knapsack.

def knapsack_lagrangian(values, weights, capacity, iters=200):
    """Upper bound for a 0/1 knapsack by dualizing the capacity constraint."""
    def relaxed(lam):
        return [1 if v - lam * w > 0 else 0 for v, w in zip(values, weights)]

    def g(lam):
        return capacity * lam + sum(max(0.0, v - lam * w) for v, w in zip(values, weights))

    def repair(x):
        # Greedy primal heuristic: drop worst value/weight items until feasible.
        x = list(x)
        order = sorted(range(len(x)), key=lambda i: values[i] / weights[i])
        for i in order:
            if sum(w * xi for w, xi in zip(weights, x)) <= capacity:
                break
            x[i] = 0
        return x, sum(v * xi for v, xi in zip(values, x))

    lam, best_bound, best_feasible = 0.0, float("inf"), 0
    for k in range(1, iters + 1):
        x = relaxed(lam)
        best_bound = min(best_bound, g(lam))
        best_feasible = max(best_feasible, repair(x)[1])
        subgrad = capacity - sum(w * xi for w, xi in zip(weights, x))
        lam = max(0.0, lam - (1.0 / k) * subgrad)    # diminishing step, project to λ >= 0
    return best_bound, best_feasible

print(knapsack_lagrangian([10, 13, 7], [4, 6, 3], 8))
# about (19.167, 17): bound within 0.001 of 115/6, feasible solution 17

Three details make this work in practice. The step size must shrink (a diminishing rule such as 1/k converges; a fixed step oscillates), and the bound is not monotone, so keep the best one seen. The relaxed solution is usually infeasible, so a cheap repair heuristic turns it into a feasible point and a lower bound, closing the bracket from the other side. And the multipliers carry information: items or constraints with large multipliers are the contested ones, which branching rules can exploit. Large-scale uses include crew scheduling, facility location and unit commitment in power systems, where dualizing a few linking constraints splits a huge problem into many small independent ones that can be solved in parallel; that splitting is called dual decomposition.

Duality in machine learning

In machine learning, the most famous Lagrangian dual is the support vector machine. The soft-margin primal minimizes ½‖w‖² + C Σ ξᵢ subject to yᵢ(w·xᵢ + b) ≥ 1 - ξᵢ and ξᵢ ≥ 0. Forming the Lagrangian, minimizing over w, b and ξ, and substituting back gives the dual: maximize Σ αᵢ - ½ Σᵢ Σⱼ αᵢ αⱼ yᵢ yⱼ (xᵢ·xⱼ) subject to 0 ≤ αᵢ ≤ C and Σ αᵢ yᵢ = 0. Two things fall out. The data enter only through inner products, so they can be replaced by a kernel K(xᵢ, xⱼ). And complementary slackness says αᵢ = 0 for every point strictly outside the margin, so the solution depends only on the support vectors.

The same structure appears in constrained training. Constrained reinforcement learning and fairness-constrained classifiers often train a min-max objective in which the multiplier is itself a learned parameter, updated by gradient ascent on the constraint violation while the model descends on the Lagrangian. Neural objectives are nonconvex, so strong duality is not guaranteed and the multiplier can oscillate; in practice teams damp it with small learning rates or switch to augmented Lagrangian methods, which add a quadratic penalty on violation to stabilize the updates. The gradient dynamics behind these updates are covered in gradient descent analysis.

Failure modes

• Assuming zero gap. A dual bound on an integer or nonconvex problem is a bound, not an answer; report both sides of the bracket.
• Ignoring the domain of g. Prices where the infimum is minus infinity are not dual feasible; an unbounded relaxed problem means the multipliers are wrong, not the model.
• Fixed subgradient steps. The method oscillates around the optimum without converging; use diminishing or Polyak-style steps and track the best bound.
• Skipping the constraint qualification. KKT conditions can fail to hold at the optimum when Slater fails, as in the x² ≤ 0 example.
• Reading multipliers outside their range. A shadow price is a derivative; it is accurate only for small changes, before the set of tight constraints changes.

Trade-offs

What to do next

1. Derive the dual of the convex example by hand, then of a problem you care about; check Slater before trusting the gap to close.
2. Run the knapsack relaxation above, change the capacity, and watch the gap open and close; compare the bound with the fractional greedy solution from the knapsack article.
3. For an LP you already solve, read the dual values the solver reports and interpret them as prices; the simplex method explains where they come from.
4. Look for coupling constraints in your own scheduling or allocation problems; if dualizing them splits the problem, try dual decomposition.
5. Place these methods among their neighbours in the optimization landscape.