3Solutions of linear programs

IB Optimisation

3.3 Extreme points and optimal solutions

Recall that we previously showed in our 2D example that the optimal solution

lies on an extreme point, i.e. is a basic feasible solution. This is also true in

general.

Theorem.

If (

P

) is feasible and b ounded, then there exists an optimal solution

that is a basic feasible solution.

Proof.

Let

x

be optimal of (

P

). If

x

has at most non-zero entries, it is a basic

feasible solution, and we are done.

Now suppose

x

has

r > m

non-zero entries. Since it is not an extreme point,

we have y 6= z ∈ X(b), δ ∈ (0, 1) such that

x = δy + (1 − δ)z.

We will show there exists an optimal solution strictly fewer than

r

non-zero

entries. Then the result follows by induction.

By optimality of x, we have c

T

x ≥ c

T

y and c

T

x ≥ c

T

z.

Since

c

T

x

=

δc

T

y

+ (1

− δ

)

c

T

z

, we must have that

c

T

x

=

c

T

y

=

c

T

z

, i.e.

y

and z are also optimal.

Since

y ≥

0 and

z ≥

0,

x

=

δy

+ (1

− δ

)

z

implies that

y

i

=

z

i

= 0 whenever

x

i

= 0.

So the non-zero entries of

y

and

z

is a subset of the non-zero entries of

x

. So

y

and

z

have at most

r

non-zero entries, which must occur in rows where

x

is

also non-zero.

If

y

or

z

has strictly fewer than

r

non-zero entries, then we are done. Other-

wise, for any

ˆ

δ (not necessarily in (0, 1)), let

x

ˆ

δ

=

ˆ

δy + (1 −

ˆ

δ)z = z +

ˆ

δ(y − z).

Observe that x

ˆ

δ

is optimal for every

ˆ

δ ∈ R.

Moreover,

y − z 6

= 0, and all non-zero entries of

y − z

occur in rows where

x

is non-zero as well. We can thus choose

ˆ

δ ∈ R

such that

x

ˆ

δ

≥

0 and

x

ˆ

δ

has

strictly fewer than r non-zero entries.

Intuitively, this is what we do when we “slide along the line” if

c

is orthogonal

to one of the boundary lines.

This result in fact holds more generally for the maximum of a convex function

f over a compact (i.e. closed and bounded) convex set X.

In that case, we can write any point x ∈ X as a convex combination

x =

k

X

i=1

δ

i

x

i

of extreme points x

k

∈ X, where δ ∈ R

k

≥0

and

P

k

i=1

δ

i

= 1.

Then, by convexity of f,

f(x) ≤

k

X

i=1

δ

i

f(x

i

) ≤ max

i

f(x

i

)

So any point in the interior cannot be better than the extreme points.