2The method of Lagrange multipliers
IB Optimisation
2.4 Supporting hyperplanes and convexity
We use the fancy term “hyperplane” to denote planes in higher dimensions (in
an n-dimensional space, a hyperplane has n − 1 dimensions).
Definition
(Supporting hype rplane)
.
A hyperplane
α
:
R
m
→ R
is supporting
to φ at b if α intersects φ at b and φ(c) ≥ α(c) for all c.
x
φ
φ(b)
α
Theorem.
(
P
) satisfies strong duality iff
φ
(
c
) =
inf
x∈X(c)
f
(
x
) has a supporting
hyperplane at b.
Note that here we fix a b, and let φ be a function of c.
Proof.
(
⇐
) Suppose there is a supporting hyperplane. Then since the plane
passes through φ(b), it must be of the form
α(c) = φ(b) + λ
T
(c − b).
Since this is supporting, for all c ∈ R
m
,
φ(b) + λ
T
(c − b) ≤ φ(c),
or
φ(b) ≤ φ(c) − λ
T
(c − b),
This implies that
φ(b) ≤ inf
c∈R
m
(φ(c) − λ
T
(c − b))
= inf
c∈R
m
inf
x∈X(c)
(f(x) − λ
T
(h(x) − b))
(since φ(c) = inf
x∈X(c)
f(x) and h(x) = c for x ∈ X(c))
= inf
x∈X
L(x, λ).
(since
S
c∈R
m
X
(
c
) =
X
, which is true since for any
x ∈ X
, we have
x ∈ X
(
h
(
x
)))
= g(λ)
By weak duality, g(λ) ≤ φ(b). So φ(b) = g(λ). So strong duality holds.
(
⇒
). Assume now that we have strong duality. The there exists
λ
such that
for all c ∈ R
m
,
φ(b) = g(λ)
= inf
x∈X
L(x, λ)
≤ inf
x∈X(c)
L(x, λ)
= inf
x∈X(c)
(f(x) − λ
T
(h(x) − b))
= φ(c) − λ
T
(c − b)
So φ(b) + λ
T
(c − b) ≤ φ(c). So this defines a supporting hyperplane.
We are having some progress now. To show that Lagrange multipliers work,
we need to show that (
P
) satisfies strong duality. To show that (
P
) satisfies
strong duality, we need to show that it has a supporting hyperplane at
b
. How
can we show that there is a supporting hyperplane? A sufficient condition is
convexity.
Theorem
(Supporting hyperplane theorem)
.
Suppose that
φ
:
R
m
→ R
is
convex and
b ∈ R
m
lies in the interior of the set of points where
φ
is finite. Then
there exists a supporting hyperplane to φ at b.
Proof follows rather straightforwardly from the definition of convexity, and
is omitted.
This is some even better progress. However, the definition of
φ
is rather
convoluted. How can we show that it is convex? We have the following helpful
theorem:
Theorem. Let
φ(b) = inf
x∈X
{f(x) : h(x) ≤ b}
If X, f, h are convex, then so is φ (assuming feasibility and boundedness).
Proof.
Consider
b
1
, b
2
∈ R
m
such that
φ
(
b
1
) and
φ
(
b
2
) are defined. Let
δ ∈
[0
,
1]
and define
b
=
δb
1
+(1
−δ
)
b
2
. We want to show that
φ
(
b
)
≤ δφ
(
b
1
)+(1
−δ
)
φ
(
b
2
).
Consider
x
1
∈ X
(
b
1
),
x
2
∈ X
(
b
2
), and let
x
=
δx
1
+ (1
− δ
)
x
2
. By convexity
of X, x ∈ X.
By convexity of h,
h(x) = h(δx
1
+ (1 − δ)x
2
)
≤ δh(x
1
) + (1 − δ)h(x
2
)
≤ δb
1
+ (1 − δ)b
2
= b
So x ∈ X(b). Since φ(x) is an optimal solution, by convexity of f,
φ(b) ≤ f(x)
= f(δx
1
+ (1 − δ)x
2
)
≤ δf(x
1
) + (1 − δ)f(x
2
)
This holds for any
x
1
∈ X
(
b
1
) and
x
2
∈ X
(
b
2
). So by taking infimum of the
right hand side,
φ(b) ≤ δφ(b
1
) + (1 − δ)φ(b
2
).
So φ is convex.
h
(
x
) =
b
is equivalent to
h
(
x
)
≤ b
and
−h
(
x
)
≤ −b
. So the result holds for
problems with equality constraints if both
h
and
−h
are convex, i.e. if
h
(
x
) is
linear.
So
Theorem.
If a linear program is feasible and bounded, then it satisfies strong
duality.