44.02.01 · optimization-control / 02-convex-duality-kkt

Lagrangian Duality, Weak and Strong Duality, and Slater's Condition

shipped3 tiersLean: none

Anchor (Master): Bertsekas 2009 Convex Optimization Theory (Athena Scientific) §4.1-§4.3, §5.3; Rockafellar 1970 Convex Analysis (Princeton) §28-§30; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §5.3-§5.5, §5.9

Intuition Beginner

Many real problems ask you to make something as small as possible while obeying rules. Minimize the cost of a bridge, but the bridge must hold a certain load. Minimize fuel, but arrive on time. The rules are constraints, and they make the problem harder: you cannot just walk downhill, because downhill might break a rule.

Lagrangian duality is a way to convert hard rules into prices. Instead of forbidding a rule violation outright, you charge a fee for breaking it. If you exceed the load limit by a little, you pay a penalty proportional to the overage. The fee per unit of violation is called a multiplier or a price. Once rules are priced, the constrained problem becomes an unconstrained one: just minimize cost plus fees.

Here is the clever part. For any fixed set of prices, you can solve the cheap unconstrained version and get a number. That number is always a lower bound on the true best cost of the original problem. Why? Because the original problem obeys the rules, so it pays no fees, while the priced version is free to bend the rules whenever bending saves more than the fee. A more permissive problem can only do better, so its best value sits at or below the real best value.

So every choice of prices hands you a guarantee: "the true answer is no smaller than this." It is natural to ask for the best such guarantee — the prices that push the lower bound as high as possible. That search is the dual problem. Solving it tells you how close you are to the real optimum, and often, for well-behaved problems, the best guarantee exactly equals the true cost.

Visual Beginner

Figure: a horizontal axis showing the cost of a constrained problem. The true best feasible cost sits at a value marked p-star. Below it, a sequence of dual lower bounds creep upward as the prices are tuned, each one a valid floor. The highest dual bound is marked d-star. When the two coincide, the gap closes; when d-star sits strictly below p-star, the leftover distance is the duality gap.

   dual lower bounds (one per price choice)        primal best
        |        |          |        |                  |
  ------+--------+----------+--------+--------|---------+------->  cost
        b1       b2         b3      d*  <-gap->         p*

   every dual value bi <= p*   (weak duality: floors below the true best)
   d* = best floor = highest guarantee
   gap = p* - d*    (zero for nice convex problems: strong duality)

Worked example Beginner

Minimize $f (x) = x^{2}$ over a single variable, subject to the rule $x \geq 1$ . The honest answer is plain: the smallest square allowed is at $x = 1$ , giving cost $1$ . We now recover that $1$ as a best price and see the lower-bound mechanism work.

Step 1. Price the rule. Rewrite the rule as $1 - x \leq 0$ and charge a fee $λ \geq 0$ per unit of violation. The priced cost is $L (x, λ) = x^{2} + λ (1 - x)$ .

Step 2. Minimize the priced cost over $x$ . For fixed $λ$ , the cheapest $x$ sets the slope to zero: the slope is $2 x - λ$ , so $x = λ /2$ . Plugging back, the best priced value is

g (λ) = (\frac{λ}{2})^{2} + λ (1 - \frac{λ}{2}) = \frac{λ ^{2}}{4} + λ - \frac{λ ^{2}}{2} = λ - \frac{λ ^{2}}{4} .

Step 3. This is a lower bound for every price. Try $λ = 1$ : $g (1) = 1 - \frac{1}{4} = 0.75$ , which is below the true cost $1$ . Try $λ = 3$ : $g (3) = 3 - \frac{9}{4} = 0.75$ again, still below $1$ . Each price gives a valid floor.

Step 4. Pick the best price. Maximize $g (λ) = λ - \frac{λ ^{2}}{4}$ over $λ \geq 0$ . Its slope is $1 - \frac{λ}{2}$ , zero at $λ = 2$ , where $g (2) = 2 - 1 = 1$ .

What this tells us. The best dual value is $1$ , exactly the true constrained cost. The gap is zero: the price $λ = 2$ buys a guarantee that cannot be improved, and that guarantee is the right answer.

Check your understanding Beginner

Formal definition Intermediate+

Consider the standard-form optimization problem over $x \in R^{n}$ , with domain $D = dom f_{0} \cap ⋂_{i} dom f_{i}$ assumed nonempty,

p^{⋆} = x in f f_{0} (x) subject to f_{i} (x) \leq 0 (i = 1, \dots, m), h_{j} (x) = 0 (j = 1, \dots, p),

with optimal value $p^{⋆}$ (taken as $+ \infty$ if infeasible). No convexity is assumed yet.

Definition (Lagrangian). The Lagrangian $L : R^{n} \times R^{m} \times R^{p} \to R$ is

L (x, λ, ν) = f_{0} (x) + i = 1 \sum m λ_{i} f_{i} (x) + j = 1 \sum p ν_{j} h_{j} (x),

where $λ_{i}$ are the inequality multipliers and $ν_{j}$ the equality multipliers (the dual variables). The vector $λ$ is required nonnegative, $ν$ free.

Definition (dual function). The Lagrange dual function $g : R^{m} \times R^{p} \to [- \infty, + \infty)$ is the pointwise infimum of the Lagrangian over $x$ ,

g (λ, ν) = x \in D in f L (x, λ, ν) = x \in D in f (f_{0} (x) + \sum_{i} λ_{i} f_{i} (x) + \sum_{j} ν_{j} h_{j} (x)) .

For each fixed $x$ , the map $(λ, ν) \mapsto L (x, λ, ν)$ is affine, hence concave; an infimum of affine functions is concave ^{[Boyd & Vandenberghe §5.1.2]}. So $g$ is concave and upper-semicontinuous on $R^{m} \times R^{p}$ no matter how nonconvex the primal data $f_{0}, f_{i}, h_{j}$ are. The dual function may take the value $- \infty$ ; its effective domain is $dom g = {(λ, ν) : g (λ, ν) > - \infty}$ .

Definition (dual problem). A pair $(λ, ν)$ is dual feasible if $λ ⪰ 0$ (componentwise) and $(λ, ν) \in dom g$ . The Lagrange dual problem is the concave maximization

d^{⋆} = λ ⪰ 0, ν sup g (λ, ν),

a convex optimization problem (maximizing a concave function over a convex set) regardless of the primal. Its optimal value is $d^{⋆}$ . The number $p^{⋆} - d^{⋆} \geq 0$ is the duality gap; strong duality is the statement $p^{⋆} = d^{⋆}$ .

Definition (perturbation / value function). The perturbed problem parameterizes the right-hand sides,

p (u, w) = x in f {f_{0} (x) : f_{i} (x) \leq u_{i}, h_{j} (x) = w_{j}},

so $p^{⋆} = p (0, 0)$ . The optimal value function $p$ packages all perturbations; its epigraph is the closure of the value set (or constraint-image set)

A = {(u, w, t) \in R^{m} \times R^{p} \times R : \exists x \in D, f_{i} (x) \leq u_{i}, h_{j} (x) = w_{j}, f_{0} (x) \leq t} .

When $f_{0}, f_{1}, \dots, f_{m}$ are convex and the $h_{j}$ affine, $p$ is convex and $A$ is a convex set; this is the structural hypothesis under which strong duality becomes available.

Counterexamples to common slips

A nonzero duality gap is normal off the convex case. The nonconvex problem of minimizing $x_{1} x_{2}$ subject to a quadratic equality can have $p^{⋆}$ strictly above $d^{⋆}$ ; weak duality still holds, but the dual recovers only a loose bound. Strong duality is a theorem about convex problems with a qualification, not a universal law.
Convexity alone does not force a zero gap. The convex problem $in f {e^{- x} : x^{2} / y \leq 0, y > 0}$ has $p^{⋆} = 1$ but $d^{⋆} = 0$ : the feasible set has empty relative interior in the relevant sense, so Slater's condition fails and the gap is positive even though every function in sight is convex.
The dual function is concave even when the primal is wild. $g$ is an infimum of affine functions of $(λ, ν)$ for any primal data; do not expect concavity of $g$ to certify anything about the primal. It is the value $d^{⋆}$ , not the shape of $g$ , that interacts with primal convexity.

Key theorem with proof Intermediate+

The two pillars are weak duality, which is unconditional, and strong duality under Slater's constraint qualification, which rests on separating a point from the convex value set — the finite-dimensional shadow of the geometric Hahn-Banach theorem of 02.11.02.

Theorem (weak and strong Lagrangian duality).

(i) (Weak duality.) For the standard-form problem, $d^{⋆} \leq p^{⋆}$ . In particular $g (λ, ν) \leq p^{⋆}$ for every dual-feasible $(λ, ν)$ .

(ii) (Strong duality under Slater.) Suppose the problem is convex: $f_{0}, f_{1}, \dots, f_{m}$ are convex, the equality maps are affine $h_{j} (x) = a_{j}^{⊤} x - b_{j}$ , and $dom f_{0}$ has nonempty interior. Suppose Slater's condition holds: there exists a strictly feasible point $\tilde{x} \in relint D$ with $f_{i} (\tilde{x}) < 0$ for all $i$ and $h_{j} (\tilde{x}) = 0$ for all $j$ . If $p^{⋆}$ is finite, then $d^{⋆} = p^{⋆}$ and the dual optimum is attained by some $(λ^{⋆}, ν^{⋆})$ with $λ^{⋆} ⪰ 0$ .

Proof of (i). Let $\overset{x}{ˉ}$ be any primal-feasible point: $f_{i} (\overset{x}{ˉ}) \leq 0$ and $h_{j} (\overset{x}{ˉ}) = 0$ . For dual-feasible $(λ, ν)$ with $λ ⪰ 0$ , each term $λ_{i} f_{i} (\overset{x}{ˉ}) \leq 0$ and each $ν_{j} h_{j} (\overset{x}{ˉ}) = 0$ , so

L (\overset{x}{ˉ}, λ, ν) = f_{0} (\overset{x}{ˉ}) + i \sum λ_{i} f_{i} (\overset{x}{ˉ}) + j \sum ν_{j} h_{j} (\overset{x}{ˉ}) \leq f_{0} (\overset{x}{ˉ}) .

Taking the infimum of the left side over all $x \in D$ only decreases it, so $g (λ, ν) = in f_{x} L (x, λ, ν) \leq L (\overset{x}{ˉ}, λ, ν) \leq f_{0} (\overset{x}{ˉ})$ . Minimizing the right side over feasible $\overset{x}{ˉ}$ gives $g (λ, ν) \leq p^{⋆}$ . Taking the supremum over dual-feasible $(λ, ν)$ yields $d^{⋆} \leq p^{⋆}$ . $□$

Proof of (ii). Treat the inequality constraints; the affine equalities are carried along by an identical separating-functional bookkeeping and are suppressed for readability (they contribute the free multipliers $ν^{⋆}$ ). Define the value set

A = {(u, t) \in R^{m} \times R : \exists x \in D, f_{i} (x) \leq u_{i} (\forall i), f_{0} (x) \leq t} .

Because $f_{0}, f_{i}$ are convex and the conditions defining $A$ are " $\leq$ " inequalities in jointly convex data, $A$ is a convex subset of $R^{m + 1}$ (if $(u, t), (u^{'}, t^{'}) \in A$ via $x, x^{'}$ , then $θ x + (1 - θ) x^{'}$ witnesses the convex combination by convexity of each $f_{i}$ and $f_{0}$ ; this is the convex-operation calculus of 44.01.01). By definition $(0, p^{⋆}) \in cl A$ and no point $(0, t)$ with $t < p^{⋆}$ lies in $A$ .

The point $(0, p^{⋆})$ is not in the interior of $A$ from below: ${(0, t) : t < p^{⋆}} \cap A = \emptyset$ . By the supporting/separating-hyperplane theorem for convex sets — the finite-dimensional case of the geometric Hahn-Banach result of 02.11.02, here requiring no choice principle — there is a nonzero $(μ, β) \in R^{m} \times R$ with

μ^{⊤} u + β t \geq β p^{⋆} for all (u, t) \in A .

Since $t$ can be increased without bound inside $A$ (raise the objective slack), $β \geq 0$ ; since each $u_{i}$ can be increased without bound (loosen a constraint), $μ ⪰ 0$ . Suppose $β = 0$ . Then $μ^{⊤} u \geq 0$ on $A$ with $μ ⪰ 0$ , $μ \neq = 0$ ; evaluating at the Slater point, $(f_{1} (\tilde{x}), \dots, f_{m} (\tilde{x}), f_{0} (\tilde{x})) \in A$ gives $\sum_{i} μ_{i} f_{i} (\tilde{x}) \geq 0$ , but $f_{i} (\tilde{x}) < 0$ and $μ_{i} \geq 0$ force $\sum_{i} μ_{i} f_{i} (\tilde{x}) < 0$ unless $μ = 0$ — a contradiction. Hence $β > 0$ ; rescale so $β = 1$ and set $λ^{⋆} = μ ⪰ 0$ .

The separating inequality reads $\sum_{i} λ_{i}^{⋆} u_{i} + t \geq p^{⋆}$ for all $(u, t) \in A$ . Applying it to the witness point $(f_{1} (x), \dots, f_{m} (x), f_{0} (x))$ of any $x \in D$ ,

f_{0} (x) + i \sum λ_{i}^{⋆} f_{i} (x) \geq p^{⋆} for all x \in D,

which is exactly $L (x, λ^{⋆}) \geq p^{⋆}$ . Taking the infimum over $x$ , $g (λ^{⋆}) \geq p^{⋆}$ . Weak duality gives the reverse $g (λ^{⋆}) \leq d^{⋆} \leq p^{⋆}$ , so $g (λ^{⋆}) = d^{⋆} = p^{⋆}$ and $(λ^{⋆}, ν^{⋆})$ attains the dual optimum. $□$

Bridge. This theorem builds toward the optimality conditions of 44.02.02 and appears again in every primal-dual algorithm and certificate of optimality. This is exactly the geometric content that generalises the elementary penalty intuition: the multipliers $λ^{⋆}$ are the slopes of the supporting hyperplane to the value set at $(0, p^{⋆})$ , so the dual problem is the search for that supporting hyperplane, and Slater's condition is what guarantees the support is non-vertical ( $β > 0$ ). The foundational reason strong duality can fail is a vertical supporting hyperplane, which Slater rules out by placing a strictly feasible point in the relative interior. Putting these together, weak duality is dual to the feasibility side and is unconditional, while strong duality is the separation theorem of 02.11.02 applied to the convex value set assembled by the operation calculus of 44.01.01; the multiplier $λ^{⋆}$ is the price that closes the gap, and it reappears as the KKT multiplier of 44.02.02.

Exercises Intermediate+

Exercise 1 (easy, symbolic).

Show directly from the definitions that the dual function $g (λ, ν)$ is concave in $(λ, ν)$ , with no assumption on the primal data.

Hint

For each fixed $x$ , what kind of function is $(λ, ν) \mapsto L (x, λ, ν)$ ? Then use that an infimum of such functions is concave.

Answer

Fix $x$ . Then $L (x, λ, ν) = f_{0} (x) + \sum_{i} λ_{i} f_{i} (x) + \sum_{j} ν_{j} h_{j} (x)$ is affine in $(λ, ν)$ , hence concave (and convex). For $θ \in [0, 1]$ , $L (x, θ (λ_{1}, ν_{1}) + (1 - θ) (λ_{2}, ν_{2})) = θ L (x, λ_{1}, ν_{1}) + (1 - θ) L (x, λ_{2}, ν_{2}) \geq θ g (λ_{1}, ν_{1}) + (1 - θ) g (λ_{2}, ν_{2})$ since $L (x, \cdot) \geq g (\cdot)$ pointwise. Taking the infimum over $x$ of the left side preserves the inequality, giving $g (θ (\cdot) + (1 - θ) (\cdot)) \geq θ g + (1 - θ) g$ . So $g$ is concave; equivalently it is a pointwise infimum of affine functions, which the operation calculus of 44.01.01 classifies as concave.

Exercise 4 (medium, symbolic).

For the minimum-norm problem $min ∥ x ∥$ subject to $A x = b$ (any norm $∥ \cdot ∥$ ), show the dual is $max b^{⊤} ν$ subject to $∥ A^{⊤} ν ∥_{*} \leq 1$ , where $∥ \cdot ∥_{*}$ is the dual norm.

Hint

$g (ν) = in f_{x} (∥ x ∥ + ν^{⊤} (A x - b)) = - b^{⊤} ν + in f_{x} (∥ x ∥ + (A^{⊤} ν)^{⊤} x)$ . The inner infimum is $0$ or $- \infty$ depending on $∥ A^{⊤} ν ∥_{*}$ .

Answer

Write $y = A^{⊤} ν$ . The inner term is $in f_{x} (∥ x ∥ + y^{⊤} x)$ . If $∥ y ∥_{*} \leq 1$ then $y^{⊤} x \geq - ∥ y ∥_{*} ∥ x ∥ \geq - ∥ x ∥$ , so $∥ x ∥ + y^{⊤} x \geq 0$ with equality at $x = 0$ ; the infimum is $0$ . If $∥ y ∥_{*} > 1$ , choose $x$ with $∥ x ∥ = 1$ and $y^{⊤} x = - ∥ y ∥_{*} < - 1$ , then scale $x \to t x$ : $∥ t x ∥ + y^{⊤} (t x) = t (1 - ∥ y ∥_{*}) \to - \infty$ . Hence $g (ν) = - b^{⊤} ν$ if $∥ A^{⊤} ν ∥_{*} \leq 1$ and $- \infty$ otherwise; the dual is $max - b^{⊤} ν$ s.t. $∥ A^{⊤} ν ∥_{*} \leq 1$ , equivalently $max b^{⊤} ν$ s.t. $∥ A^{⊤} ν ∥_{*} \leq 1$ after sign flip. The dual norm appears precisely because the conjugate of a norm is the indicator of the dual unit ball.

Exercise 5 (medium, symbolic).

State the max-min inequality $sup_{λ ⪰ 0, ν} in f_{x} L \leq in f_{x} sup_{λ ⪰ 0, ν} L$ and identify both sides with $d^{⋆}$ and $p^{⋆}$ .

Hint

For the right side, evaluate $sup_{λ ⪰ 0, ν} L (x, λ, ν)$ for a fixed $x$ , splitting on whether $x$ is feasible.

Answer

The max-min inequality $sup_{y} in f_{x} ϕ (x, y) \leq in f_{x} sup_{y} ϕ (x, y)$ holds for any $ϕ$ . Take $ϕ = L$ with $y = (λ, ν)$ , $λ ⪰ 0$ . The left side is $sup_{λ ⪰ 0, ν} g (λ, ν) = d^{⋆}$ . For the right side, fix $x$ : if $x$ is infeasible (some $f_{i} (x) > 0$ or $h_{j} (x) \neq = 0$ ) then driving $λ_{i} \to \infty$ or $ν_{j} \to \pm \infty$ makes $sup_{λ, ν} L = + \infty$ ; if $x$ is feasible the best choice is $λ = 0$ on inactive constraints, giving $sup L = f_{0} (x)$ . So $in f_{x} sup_{λ ⪰ 0, ν} L = in f_{x feasible} f_{0} (x) = p^{⋆}$ . The inequality is weak duality $d^{⋆} \leq p^{⋆}$ ; equality is strong duality, and a point where the order of $sup$ and $in f$ may be swapped is a saddle point.

Exercise 6 (hard, symbolic).

Prove that if $(x^{⋆}, λ^{⋆}, ν^{⋆})$ is a saddle point of $L$ — i.e. $L (x^{⋆}, λ, ν) \leq L (x^{⋆}, λ^{⋆}, ν^{⋆}) \leq L (x, λ^{⋆}, ν^{⋆})$ for all $x$ and all $λ ⪰ 0, ν$ — then $x^{⋆}$ is primal optimal, $(λ^{⋆}, ν^{⋆})$ is dual optimal, and the duality gap is zero.

Hint

The left saddle inequality forces primal feasibility and complementary slackness; the right one says $x^{⋆}$ minimizes $L (\cdot, λ^{⋆}, ν^{⋆})$ , hence achieves $g (λ^{⋆}, ν^{⋆})$ .

Answer

From $L (x^{⋆}, λ, ν) \leq L (x^{⋆}, λ^{⋆}, ν^{⋆})$ for all $λ ⪰ 0, ν$ : writing it out, $\sum_{i} (λ_{i} - λ_{i}^{⋆}) f_{i} (x^{⋆}) + \sum_{j} (ν_{j} - ν_{j}^{⋆}) h_{j} (x^{⋆}) \leq 0$ for all admissible $λ, ν$ . Free $ν_{j}$ forces $h_{j} (x^{⋆}) = 0$ ; letting $λ_{i} \to \infty$ forces $f_{i} (x^{⋆}) \leq 0$ , so $x^{⋆}$ is feasible; and setting $λ = 0$ gives $- \sum_{i} λ_{i}^{⋆} f_{i} (x^{⋆}) \leq 0$ , i.e. $\sum_{i} λ_{i}^{⋆} f_{i} (x^{⋆}) \geq 0$ , while $λ_{i}^{⋆} \geq 0$ and $f_{i} (x^{⋆}) \leq 0$ give $\leq 0$ ; hence $\sum_{i} λ_{i}^{⋆} f_{i} (x^{⋆}) = 0$ (complementary slackness). The right inequality says $x^{⋆}$ minimizes $L (\cdot, λ^{⋆}, ν^{⋆})$ , so $g (λ^{⋆}, ν^{⋆}) = L (x^{⋆}, λ^{⋆}, ν^{⋆}) = f_{0} (x^{⋆})$ using feasibility and slackness. Thus $f_{0} (x^{⋆}) = g (λ^{⋆}, ν^{⋆}) \leq d^{⋆} \leq p^{⋆} \leq f_{0} (x^{⋆})$ , forcing equality throughout: zero gap, both optimal.

Exercise 7 (hard, symbolic).

Exhibit a convex problem with a strictly positive duality gap and explain which hypothesis of the strong-duality theorem fails.

Hint

Use a problem whose single inequality constraint cannot be made strictly negative anywhere feasible, so no Slater point exists.

Answer

Minimize $f_{0} (x, y) = e^{- x}$ over ${(x, y) : y > 0}$ subject to $f_{1} (x, y) = x^{2} / y \leq 0$ . Since $x^{2} / y \geq 0$ on the domain, feasibility forces $x = 0$ , giving $p^{⋆} = e^{0} = 1$ . The Lagrangian is $L = e^{- x} + λ x^{2} / y$ ; for $λ \geq 0$ , $in f_{x, y > 0} L = 0$ (let $y \to \infty$ so the penalty vanishes and $x \to + \infty$ so $e^{- x} \to 0$ ), so $g (λ) = 0$ for all $λ \geq 0$ and $d^{⋆} = 0 < 1 = p^{⋆}$ . The gap is $1$ . Slater fails: there is no feasible point with $x^{2} / y < 0$ strictly, because $x^{2} / y$ is never negative; the value set $A$ has a vertical supporting hyperplane at $(0, p^{⋆})$ , the $β = 0$ case the proof excludes only under Slater.

Exercise 8 (hard, symbolic).

Show that when strong duality holds and the dual optimum $(λ^{⋆}, ν^{⋆})$ is attained, the optimal multiplier $λ^{⋆}$ equals (minus) the sensitivity of $p^{⋆}$ to relaxing the corresponding constraint, i.e. $λ_{i}^{⋆} = - \partial p^{⋆} / \partial u_{i}$ when $p$ is differentiable at $0$ .

Hint

Use the global lower bound $p (u) \geq p^{⋆} - \sum_{i} λ_{i}^{⋆} u_{i}$ from the supporting hyperplane to the value set, then read off the gradient.

Answer

Strong duality with attained $λ^{⋆}$ means the hyperplane with slopes $(λ^{⋆}, 1)$ supports $A$ at $(0, p^{⋆})$ : for every perturbation $u$ , $p (u) = in f {f_{0} (x) : f_{i} (x) \leq u_{i}} \geq p^{⋆} - \sum_{i} λ_{i}^{⋆} u_{i}$ . Indeed for any $x$ feasible to the $u$ -problem, $f_{0} (x) \geq g (λ^{⋆}) - \sum_{i} λ_{i}^{⋆} (f_{i} (x) - u_{i}) \geq p^{⋆} - \sum_{i} λ_{i}^{⋆} u_{i}$ using $f_{i} (x) \leq u_{i}$ and $λ_{i}^{⋆} \geq 0$ . So $p (u) - p (0) \geq - \sum_{i} λ_{i}^{⋆} u_{i}$ with equality at $u = 0$ ; if $p$ is differentiable at $0$ , this tangent lower bound forces $\nabla p (0) = - λ^{⋆}$ , i.e. $\partial p^{⋆} / \partial u_{i} = - λ_{i}^{⋆}$ . The multiplier is the marginal price of the constraint: a large $λ_{i}^{⋆}$ means relaxing constraint $i$ buys a large improvement.

Advanced results Master

The perturbation function and conjugate duality

The Lagrangian dual is one instance of a general construction. Embed the primal in a family of perturbed problems with value function $p (u, w)$ , convex when the data are convex and the equalities affine. The dual function is, up to sign, the conjugate of $p$ evaluated on the multipliers: $g (λ, ν) = - p^{*} (- λ, - ν)$ restricted to $λ ⪰ 0$ , where $p^{*}$ is the Legendre-Fenchel conjugate of 37.07.03. Weak duality is then the Fenchel-Young inequality $p (0, 0) \geq - p^{*} (- λ, - ν)$ , and strong duality is the statement that $p$ is closed at the origin, $p^{**} (0, 0) = p (0, 0)$ , biconjugation specialized to the perturbation function. This is the Rockafellar conjugate-duality picture ^{[Rockafellar §29-§30]}: the duality gap is exactly the discrepancy between $p$ and its lower convex closure at $0$ , and it vanishes whenever $p$ is lower-semicontinuous there. Slater's condition is one sufficient regularity guaranteeing that closure, by forcing $0$ into the relative interior of $dom p$ , where a convex function is automatically continuous.

Min-common / max-crossing duality

Bertsekas isolates the geometric kernel as the min common / max crossing (MC/MC) framework ^{[Bertsekas §4.1-§4.2]}. Given a set $M \subseteq R^{m + 1}$ , the min common value is $w^{⋆} = in f {t : (0, t) \in M}$ and the max crossing value is $q^{⋆} = sup_{μ} q (μ)$ where $q (μ) = in f_{(u, t) \in M} {t + μ^{⊤} u}$ is the highest intercept of a nonvertical hyperplane crossing the axis below $M$ . Always $q^{⋆} \leq w^{⋆}$ (weak duality). Equality (strong duality) holds under the MC/MC conditions: $M$ is convex (or has a convex "upper" envelope), $w^{⋆}$ is finite, and the set does not admit a vertical supporting hyperplane at the axis — a condition met when $(0, w^{⋆})$ lies in the relative interior of the projection ${u : (u, t) \in M some t}$ . Specializing $M = A$ recovers Lagrangian duality verbatim: $w^{⋆} = p^{⋆}$ , $q^{⋆} = d^{⋆}$ , and the multiplier $μ = λ^{⋆}$ is the crossing-hyperplane slope. The framework also produces the dual existence and the absence of a gap as separate conclusions controlled by separate hypotheses, clarifying that a finite dual value and an attained dual optimum are distinct guarantees.

Constraint qualifications beyond Slater

Slater's interior-point condition is sufficient but not necessary. For problems with affine inequality constraints, strong duality and multiplier existence hold with no interior hypothesis at all (the polyhedral case, where Farkas' lemma 44.02.04 supplies the multipliers unconditionally). For mixed affine and nonlinear inequalities, the refined Slater condition requires strict feasibility only of the nonlinear constraints, the affine ones merely feasible. At the differentiable level the relevant qualifications — linear independence of active gradients (LICQ), the Mangasarian-Fromovitz condition (MFCQ), and Abadie's condition — guarantee KKT multiplier existence and connect to the dual attainment proved here; MFCQ is the local pointwise analogue of Slater. The hierarchy LICQ $\Rightarrow$ MFCQ $\Rightarrow$ Abadie orders these by strength, and each guarantees that the value function admits a non-vertical support, the single geometric fact underlying every constraint qualification.

Saddle points, the minimax theorem, and zero-sum games

Strong duality with attained primal and dual optima is equivalent to the existence of a saddle point of the Lagrangian over $R^{n} \times (R_{+}^{m} \times R^{p})$ . This is the optimization face of von Neumann's minimax theorem: the Lagrangian defines a two-player zero-sum game in which the primal player chooses $x$ to minimize and the dual player chooses prices $(λ, ν)$ to maximize, and strong duality is precisely the statement that the game has a value, $in f_{x} sup_{λ, ν} L = sup_{λ, ν} in f_{x} L$ . Sion's generalization weakens von Neumann's bilinearity to quasiconvex-quasiconcave continuity on one compact factor, and is the abstract minimax theorem from which Lagrangian strong duality, matrix-game value existence, and the LP duality theorem all descend.

Synthesis. The dual function is exactly the lower envelope of the Lagrangian read price-by-price, and the central insight of this unit is that the dual problem is the search for the best non-vertical supporting hyperplane to the convex value set $A$ at $(0, p^{⋆})$ . The foundational reason strong duality can fail is a vertical support, and Slater's condition generalises the elementary requirement of an interior feasible point into exactly the qualification that excludes verticality by placing $0$ in the relative interior of $dom p$ . Putting these together, weak duality is dual to primal feasibility and is unconditional, the perturbation function $p$ packages every relaxation into one convex object whose biconjugation closes the gap, and the multiplier $λ^{⋆}$ is simultaneously the supporting slope, the marginal sensitivity $- \nabla p (0)$ , and the price that the saddle-point game converges to. This is exactly the same separation engine of 02.11.02 that powers Farkas' lemma 44.02.04 in the polyhedral case and the conjugate duality of 37.07.03 in the perturbational case; the bridge is the value set $A$ , the single convex object through which feasibility, optimality, sensitivity, and the KKT conditions of 44.02.02 are one theory, and it appears again in the conic and semidefinite duality where $A$ lives over a self-dual cone.

Full proof set Master

Proposition 1 (the dual function is concave and upper-semicontinuous, unconditionally). For any functions $f_{0}, f_{i}, h_{j}$ , the dual function $g (λ, ν) = in f_{x \in D} L (x, λ, ν)$ is concave and upper-semicontinuous on $R^{m} \times R^{p}$ .

Proof. For each fixed $x \in D$ , the map $ℓ_{x} (λ, ν) = f_{0} (x) + \sum_{i} λ_{i} f_{i} (x) + \sum_{j} ν_{j} h_{j} (x)$ is affine, hence concave and continuous. Then $g = in f_{x \in D} ℓ_{x}$ is a pointwise infimum of a family of concave functions. The hypograph $hyp g = {(λ, ν, s) : s \leq g (λ, ν)}$ equals $⋂_{x \in D} hyp ℓ_{x}$ , an intersection of the closed convex hypographs of the affine $ℓ_{x}$ ; an intersection of closed convex sets is closed and convex (the convex-operation calculus of 44.01.01). A function whose hypograph is closed and convex is concave and upper-semicontinuous. $□$

Proposition 2 (weak duality, general form). Let $p^{⋆}$ be the primal optimal value and $d^{⋆}$ the dual optimal value. Then $d^{⋆} \leq p^{⋆}$ , and for any primal-feasible $\overset{x}{ˉ}$ and dual-feasible $(λ, ν)$ the gap is bounded below by $f_{0} (\overset{x}{ˉ}) - g (λ, ν) \geq 0$ .

Proof. For feasible $\overset{x}{ˉ}$ (so $f_{i} (\overset{x}{ˉ}) \leq 0$ , $h_{j} (\overset{x}{ˉ}) = 0$ ) and $λ ⪰ 0$ , $g (λ, ν) \leq L (\overset{x}{ˉ}, λ, ν) = f_{0} (\overset{x}{ˉ}) + \sum_{i} λ_{i} f_{i} (\overset{x}{ˉ}) + \sum_{j} ν_{j} h_{j} (\overset{x}{ˉ}) \leq f_{0} (\overset{x}{ˉ})$ , the last step because $λ_{i} f_{i} (\overset{x}{ˉ}) \leq 0$ and $ν_{j} h_{j} (\overset{x}{ˉ}) = 0$ . So every dual value lies below every primal feasible value; taking $sup$ over dual-feasible $(λ, ν)$ and $in f$ over feasible $\overset{x}{ˉ}$ yields $d^{⋆} \leq p^{⋆}$ . The displayed difference $f_{0} (\overset{x}{ˉ}) - g (λ, ν) \geq 0$ is the duality gap of the pair, an a-posteriori certificate: if it is zero, $\overset{x}{ˉ}$ and $(λ, ν)$ are both optimal. $□$

Proposition 3 (Slater $\Rightarrow$ zero gap and dual attainment). Under the convexity and Slater hypotheses of the Key theorem with $p^{⋆}$ finite, $d^{⋆} = p^{⋆}$ and the dual optimum is attained.

Proof. This is part (ii) of the Key theorem; the steps are: (a) the value set $A = {(u, t) : \exists x \in D, f_{i} (x) \leq u_{i}, f_{0} (x) \leq t}$ is convex by joint convexity of the $f_{i}, f_{0}$ ; (b) $(0, t) \in / A$ for $t < p^{⋆}$ , so $(0, p^{⋆})$ is a boundary point not strictly below which $A$ reaches; (c) the supporting-hyperplane theorem (finite-dimensional 02.11.02) gives a nonzero $(μ, β) ⪰ 0$ supporting $A$ at $(0, p^{⋆})$ ; (d) Slater excludes $β = 0$ , because a vertical support evaluated at the strictly feasible $\tilde{x}$ would require $\sum_{i} μ_{i} f_{i} (\tilde{x}) \geq 0$ with $f_{i} (\tilde{x}) < 0$ , forcing $μ = 0$ against $(μ, β) \neq = 0$ ; (e) normalizing $β = 1$ , $λ^{⋆} = μ$ gives $L (x, λ^{⋆}) \geq p^{⋆}$ for all $x$ , so $g (λ^{⋆}) \geq p^{⋆} \geq d^{⋆} \geq g (λ^{⋆})$ , equality throughout. $□$

Proposition 4 (saddle point $⟺$ optimal primal-dual pair with zero gap). A triple $(x^{⋆}, λ^{⋆}, ν^{⋆})$ with $λ^{⋆} ⪰ 0$ is a saddle point of $L$ if and only if $x^{⋆}$ is primal optimal, $(λ^{⋆}, ν^{⋆})$ is dual optimal, and $p^{⋆} = d^{⋆}$ .

Proof. ( $\Rightarrow$ ) Exercise 6 establishes that a saddle point forces feasibility, complementary slackness, $g (λ^{⋆}, ν^{⋆}) = f_{0} (x^{⋆})$ , and hence $p^{⋆} = d^{⋆}$ with both optimal. ( $\Leftarrow$ ) Suppose $x^{⋆}$ primal optimal, $(λ^{⋆}, ν^{⋆})$ dual optimal, $p^{⋆} = d^{⋆}$ . Then $f_{0} (x^{⋆}) = p^{⋆} = d^{⋆} = g (λ^{⋆}, ν^{⋆}) = in f_{x} L (x, λ^{⋆}, ν^{⋆}) \leq L (x^{⋆}, λ^{⋆}, ν^{⋆}) = f_{0} (x^{⋆}) + \sum_{i} λ_{i}^{⋆} f_{i} (x^{⋆}) \leq f_{0} (x^{⋆})$ , the last step by $λ_{i}^{⋆} \geq 0$ , $f_{i} (x^{⋆}) \leq 0$ . Equality throughout gives $\sum_{i} λ_{i}^{⋆} f_{i} (x^{⋆}) = 0$ and $x^{⋆} \in ar g min_{x} L (x, λ^{⋆}, ν^{⋆})$ , i.e. the right saddle inequality $L (x^{⋆}, \cdot) \leq L (x, \cdot)$ . The left inequality $L (x^{⋆}, λ, ν) \leq L (x^{⋆}, λ^{⋆}, ν^{⋆})$ holds because $x^{⋆}$ feasible makes $\sum_{i} λ_{i} f_{i} (x^{⋆}) \leq 0 = \sum_{i} λ_{i}^{⋆} f_{i} (x^{⋆})$ and $\sum_{j} ν_{j} h_{j} (x^{⋆}) = 0$ for all $λ ⪰ 0, ν$ . So $(x^{⋆}, λ^{⋆}, ν^{⋆})$ is a saddle point. $□$

Connections Master

The Karush-Kuhn-Tucker conditions of 44.02.02 are the differential form of the saddle-point characterization proved here: stationarity $\nabla_{x} L = 0$ , primal and dual feasibility, and complementary slackness $λ_{i}^{⋆} f_{i} (x^{⋆}) = 0$ are exactly the conditions extracted in Proposition 4, and under Slater they are necessary and sufficient for optimality. This unit supplies the existence of the multiplier $λ^{⋆}$ that the KKT system asserts.
Farkas' lemma and the theorems of the alternative 44.02.04 are the polyhedral specialization of strong duality: when all constraints are affine, the value set $A$ is a polyhedron whose closedness is unconditional, so the separating hyperplane exists without any Slater hypothesis, and Farkas supplies the LP dual multipliers directly. The same geometric Hahn-Banach separation of 02.11.02 underlies both, polyhedral closedness replacing the interior-point qualification.
Fenchel and conjugate duality 37.07.03 is the perturbational reformulation: the dual function is the conjugate of the value function, $g (λ, ν) = - p^{*} (- λ, - ν)$ , weak duality is Fenchel-Young, and strong duality is biconjugation $p^{**} (0) = p (0)$ . The Legendre-Fenchel machinery built there is the analytic engine that this unit deploys geometrically through the value set.
The convex-operation calculus and supporting-hyperplane structure of 44.01.01 is the immediate prerequisite: convexity of the value set $A$ follows from joint convexity of the constraint and objective functions, and the epigraph/supporting-hyperplane apparatus is what makes the dual function concave and the separation argument available. Strong duality is convex analysis applied to one specially assembled convex set.

Historical & philosophical context Master

The method of multipliers descends from Lagrange's Mécanique analytique (1788), where multipliers enforced equality constraints in mechanics, but the inequality theory and its duality are a twentieth-century creation. The decisive paper is Harold Kuhn and Albert Tucker's Nonlinear Programming ^{[Kuhn & Tucker 1951]} (Proceedings of the Second Berkeley Symposium, 1951, 481-492), which stated the first-order conditions for inequality-constrained optima and connected them to a constraint qualification; the same conditions had appeared in William Karush's unpublished 1939 Chicago master's thesis, the reason the conditions now carry all three names. Morton Slater's 1950 Cowles Commission discussion paper ^{[Slater 1950]} isolated the strict-feasibility interior condition that bears his name as the hypothesis closing the duality gap for convex programs, distinguishing it from the regularity assumptions Kuhn and Tucker had used.

The reorganization of all this around convex analysis is due to R. Tyrrell Rockafellar, whose Convex Analysis ^{[Rockafellar §28-§30]} (Princeton, 1970) recast Lagrangian duality as conjugate duality of the perturbation function, unifying it with Fenchel's 1949 conjugate-function theory and with the saddle-point and minimax results that trace to von Neumann's 1928 minimax theorem for zero-sum games. Dimitri Bertsekas later distilled the geometric content into the min-common/max-crossing framework ^{[Bertsekas §4.1]}, separating the finiteness of the dual value from its attainment and from the absence of a gap, and Boyd and Vandenberghe codified the operational form for practitioners, where the dual problem and Slater's condition became standard tools of convex modeling.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{bertsekas2009convex,
  author    = {Bertsekas, Dimitri P.},
  title     = {Convex Optimization Theory},
  publisher = {Athena Scientific},
  year      = {2009}
}

@book{rockafellar1970convex,
  author    = {Rockafellar, R. Tyrrell},
  title     = {Convex Analysis},
  series    = {Princeton Mathematical Series},
  number    = {28},
  publisher = {Princeton University Press},
  year      = {1970}
}

@inproceedings{kuhn1951nonlinear,
  author    = {Kuhn, Harold W. and Tucker, Albert W.},
  title     = {Nonlinear Programming},
  booktitle = {Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability},
  pages     = {481--492},
  publisher = {University of California Press},
  year      = {1951}
}

@techreport{slater1950lagrange,
  author      = {Slater, Morton},
  title       = {Lagrange Multipliers Revisited},
  institution = {Cowles Commission for Research in Economics},
  number      = {Mathematics 403},
  year        = {1950}
}

@article{vonneumann1928theorie,
  author  = {von Neumann, John},
  title   = {Zur Theorie der Gesellschaftsspiele},
  journal = {Mathematische Annalen},
  volume  = {100},
  pages   = {295--320},
  year    = {1928}
}

Prerequisites

44.01.01
02.11.02

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §5.1-§5.2 — the penalty/price picture of constraints
intermediate: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) Ch. 5; Bertsekas 2009 Convex Optimization Theory (Athena Scientific) §4.2, §5.3
master: Bertsekas 2009 Convex Optimization Theory (Athena Scientific) §4.1-§4.3, §5.3; Rockafellar 1970 Convex Analysis (Princeton) §28-§30; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §5.3-§5.5, §5.9

References

Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §5.1 the Lagrange dual function; §5.2 the Lagrange dual problem; §5.2.3 weak/strong duality; §5.3.2 Slater's condition; §5.4 saddle-point/game interpretation; §5.9 perturbation and sensitivity
Bertsekas, D. P. — Convex Optimization Theory (Athena Scientific, 2009) · §4.1-§4.2 min common / max crossing duality; §4.3 strong duality and the MC/MC framework; §5.3 the dual problem and the duality gap
Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §28 Lagrange multipliers and ordinary convex programs; §29 bifunctions; §30 perturbation, conjugate duality, and the optimal value function
Slater, M. — Lagrange Multipliers Revisited · Cowles Commission Discussion Paper, Mathematics 403 (1950); reprinted in Giorgi & Kjeldsen (eds.), Traces and Emergence of Nonlinear Programming (Birkhäuser, 2014)
Kuhn, H. W. & Tucker, A. W. — Nonlinear Programming · Proc. Second Berkeley Symposium on Mathematical Statistics and Probability (1951), 481-492

Estimated time

beginner: 18m
intermediate: 45m
master: 80m