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.