Mathematics.

optimization theory

Duality Theory

Mathematical Optimization75 minDifficulty8 out of 10

You should know: linear programming, convex optimization

Overview

Duality theory associates to every optimization problem (the primal) a related problem (the dual) whose optimal value provides a bound on the primal. In linear programming, strong duality guarantees equality of primal and dual optimal values. In convex programming, strong duality holds under constraint qualifications such as Slater's condition. Duality is not merely a theoretical tool — it yields certificates of optimality, sensitivity analysis, and efficient decomposition algorithms.

Intuition

The dual problem asks: 'What is the best lower bound (for minimisation) I can guarantee using only linear combinations of the constraints?' Duality is a manifestation of minimax: swap the min and max over a Lagrangian, and you get the dual. When strong duality holds, the two problems have the same value, and the optimal dual variables (shadow prices) tell you how much the objective improves per unit relaxation of each constraint.

Formal Definition

Definition

Given the primal convex program, the Lagrangian dual is formed by relaxing constraints into the objective via dual variables (multipliers).

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+νT(Ax−b)L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \nu^T(Ax - b)
Lagrangian
g(λ,ν)=inf⁡x∈DL(x,λ,ν)g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu)
Dual function (always concave)
max⁡λ≥0, νg(λ,ν)≤min⁡xf0(x)(weak duality)\max_{\lambda \ge 0,\, \nu} g(\lambda, \nu) \le \min_{x} f_0(x) \quad \text{(weak duality)}
Weak duality gap
d∗=p∗  ⟺  strong duality holds (e.g., Slater’s condition satisfied)d^* = p^* \iff \text{strong duality holds (e.g., Slater's condition satisfied)}
Strong duality

Notation

NotationMeaning
L(x,λ,ν)L(x,\lambda,\nu)Lagrangian; λᵢ ≥ 0 are inequality multipliers, ν are equality multipliers
g(λ,ν)g(\lambda,\nu)Dual function — infimum of Lagrangian over x
p∗,  d∗p^*,\; d^*Primal and dual optimal values
p∗−d∗p^* - d^*Duality gap (≥ 0 always)

Properties

Weak duality

d∗≤p∗ always (dual optimal value never exceeds primal)d^* \le p^* \text{ always (dual optimal value never exceeds primal)}

Strong duality for LP

For LP: p∗=d∗ when both primal and dual are feasible\text{For LP: } p^* = d^* \text{ when both primal and dual are feasible}

Complementary slackness

λi∗fi(x∗)=0∀i\lambda_i^* f_i(x^*) = 0 \quad \forall i

Dual function is concave

g(λ,ν)=inf⁡xL(x,λ,ν) is concave regardless of convexity of primalg(\lambda, \nu) = \inf_x L(x,\lambda,\nu) \text{ is concave regardless of convexity of primal}

Worked Examples

  1. 1

    Form Lagrangian: L(x,λ,μ) = cᵀx - λᵀ(Ax-b) - μᵀx for λ,μ ≥ 0.

    L(x,λ,μ)=cTx−λT(Ax−b)−μTx=(c−ATλ−μ)Tx+bTλL(x,\lambda,\mu) = c^Tx - \lambda^T(Ax-b) - \mu^Tx = (c - A^T\lambda - \mu)^Tx + b^T\lambda
  2. 2

    Dual function: g(λ,μ) = infₓ L = bᵀλ if c - Aᵀλ - μ = 0, else -∞.

    g(λ,μ)={bTλif c−ATλ−μ=0−∞otherwiseg(\lambda,\mu) = \begin{cases} b^T\lambda & \text{if } c - A^T\lambda - \mu = 0 \\ -\infty & \text{otherwise} \end{cases}
  3. 3

    Eliminate μ = c - Aᵀλ ≥ 0 (μ ≥ 0 forces Aᵀλ ≤ c). Dual: max bᵀλ, Aᵀλ ≤ c, λ ≥ 0.

    max⁡λ≥0bTλs.t.ATλ≤c\max_{\lambda \ge 0} b^T\lambda \quad \text{s.t.} \quad A^T\lambda \le c

✓ Answer

The dual LP is: max bᵀλ subject to Aᵀλ ≤ c, λ ≥ 0 — a standard form LP.

Practice Problems

Hardproof writing

Prove weak duality: for any feasible primal x and feasible dual (λ,ν), g(λ,ν) ≤ f₀(x).

Common Mistakes

Common Mistake

Assuming strong duality always holds for convex programs

Strong duality requires a constraint qualification such as Slater's condition. Without it, a positive duality gap is possible even for convex programs.

Quiz

Complementary slackness states that at optimality:

Historical Background

LP duality was discovered simultaneously by Dantzig and von Neumann in 1947, with von Neumann recognising its connection to minimax theorems in game theory. Fenchel duality (1949) generalised LP duality to convex functions. Rockafellar's 1970 monograph unified these threads, establishing Lagrangian duality as the central framework.

  1. 1947

    Von Neumann and Dantzig discover LP duality from game-theoretic perspective

    John von Neumann, George Dantzig

  2. 1949

    Fenchel duality for convex functions

    Werner Fenchel

  3. 1970

    Rockafellar unifies duality in Convex Analysis

    R. Tyrrell Rockafellar

Summary

  • The Lagrangian dual relaxes constraints into the objective via multipliers λᵢ ≥ 0, ν.
  • Weak duality: d* ≤ p* always. Strong duality: d* = p* under constraint qualifications.
  • The dual function g is always concave, making the dual problem a concave maximisation.
  • Complementary slackness λᵢ*fᵢ(x*)=0 characterises primal-dual optimal pairs.

References

  1. BookBoyd, S. and Vandenberghe, L. — Convex Optimization (2004), Chapter 5. Free at https://web.stanford.edu/~boyd/cvxbook/
  2. WebsiteWikipedia — Duality (optimization)