2The method of Lagrange multipliers
IB Optimisation
2.3 Lagrange duality
Consider the problem
minimize f(x) subject to h(x) = b, x ∈ X.
Denote this as P .
The Lagrangian is
L(x, λ) = f(x) − λ
T
(h(x) − b).
Define the dual function g : R
m
→ R as
g(λ) = inf
x∈X
L(x, λ).
ie, we fix λ, and see how small we can get L to be. As before, let
Y = {λ ∈ R
n
: g(λ) > −∞}.
Then we have
Theorem (Weak duality). If x ∈ X(b) (i.e. x satisfies both the functional and
regional constraints) and λ ∈ Y , then
g(λ) ≤ f(x).
In particular,
sup
λ∈Y
g(λ) ≤ inf
x∈X(b)
f(x).
Proof.
g(λ) = inf
x
0
∈X
L(x
0
, λ)
≤ L(x, λ)
= f(x) − λ
T
(h(x) − b)
= f(x).
This suggests that we can solve a dual problem - instead of minimizing
f
,
we can maximize
g
subject to
λ ∈ Y
. Denote this problem as (
D
). The original
problem (P ) is called primal.
Definition (Strong duality). (P ) and (D) are said to satisfy strong duality if
sup
λ∈Y
g(λ) = inf
x∈X(b)
f(x).
It turns out that problems satisfying strong duality are exactly those for
which the method of Lagrange multipliers work.
Example. Again consider the problem to minimize x
1
− x
2
− 2x
3
subject to
x
1
+ x
2
+ x
3
= 5
x
2
1
+ x
2
2
= 4
We saw that
Y = {λ ∈ R
2
: λ
1
= −2, λ
2
< 0}
and
x
∗
(λ) =
3
2λ
2
,
1
2λ
2
, 5 −
4
2λ
2
.
The dual function is
g(λ) = inf
x∈X
L(x, λ) = L(x
∗
(λ), λ) =
10
4λ
2
+ 4λ
2
− 10.
The dual is the problem to
maximize
10
4λ
2
+ 4λ
2
− 10 subject to λ
2
< 0.
The maximum is attained for
λ
2
= −
r
5
8
After calculating the values of
g
and
f
, we can see that the primal and dual do
have the same optimal value.
Right now, what we’ve got isn’t helpful, because we won’t know if our problem
satisfies strong duality!