86
T. Basu et al.
g(λ) := min
β∈B
(β, λ).
(3.7)
Note that
max
λ≥0
g(λ) = max
λ≥0
min
β∈B
(β, λ) ≤ max
λ≥0
min
β∈B
h(β)≤0
(β, λ)
(3.8)
≤ max
λ≥0
min
β∈B
h(β)≤0
f (β) = f
∗ .
(3.9)
This inequality holds in general. Strong duality tells us that, under certain conditions, the inequality becomes an equality [2, §5.2.3].
Theorem 3.1 (Strong Duality) If f and h are convex functions, and h(β) < 0 for
at least one β ∈ B, then
max
λ≥0
g(λ) = min
β∈B
h(β)≤0
f (β) = f
∗
(3.10)
So, under strong duality, to minimize f (β) over β subject to h(β) ≤ 0, we can also
instead maximize the Lagrange dual function over λ ≥ 0. In that case, the Karush–
Kuhn–Tucker conditions provide necessary and sufficient conditions for optimality.
Definition 3.1 (Subgradient) For any function F on B, we say that v ∈ R p is a
subgradient of F at β whenever
F (β
) − F (β) ≥ v
T (β
− β)
(3.11)
for all β
∈ B. The set of all subgradients of F at β is denoted by ∂F (β).
Theorem 3.2 (Karush–Kuhn–Tucker) If f and h are convex functions, and
h(β) < 0 for at least one β ∈ B, then f (β) = f ∗ if
0 ∈ ∂f (β) + λ∂h(β)
(3.12)
λh(β) = 0
(3.13)
h(β) ≤ 0
(3.14)
λ ≥ 0
(3.15)
So, Eq. (3.12) is just a fancy way of writing that β is a global minimum of
f + λh, for a fixed value of λ. Equation (3.12) is called the stationarity condition.
Equation (3.13) is called the complementary slackness condition and implies that
either λ = 0 or h(β) = 0. The inequality h(β) ≤ 0 is called primal feasibility, and
the inequality λ ≥ 0 is called dual feasibility.