Page 399 - A Course in Linear Algebra with Applications

10.2: The Geometry of Linear Programming 3 8 3

2
It is easy to visualize the situation in R : for example,
consider the shaded regions shown.

The interior of the left hand figure is clearly convex, but the
interior of the right hand one is not.
The following property of convex sets is almost obvious.

Lemma 10.2.1
n
The intersection of a collection of convex subsets of R is
either empty or convex.
Proof
n
Let {Si | i G } be a set of convex subsets of R and assume
/
that S — f] Si is not empty. If S has only one element, then
iei
it is obviously convex. So assume X\ and X2 are distinct
points of S and let 0 < t < 1. Now Xi and X 2 belong to Si
for all i, as must tX\ + (1 — t)X 2 since Si is convex. Hence
tX\ + (1 — t)X 2 G S and S is convex.

Our interest in convex sets is motivated by the following
fundamental result.
Theorem 10.2.2
The set of all feasible solutions of a linear programming prob-
lem is either empty or convex.