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.