Principles of Mathematics in Operations Research

94 7 Convex Sets

/3xi, X2 (xi ^ X2) G X 3 x = (1 - a)xi + ax2, 0 < a < 1.

Proposition 7.1.4 v4nj/ extreme point is on boundary of the set.

Proof. Let £0 be any interior point of X. Then 3e > 0 B every point in this e

neighborhood of so is in this set. Let x\ / XQ be a point in this e neighborhood.

Consider

X2 = ~X\ + 2x 0 , \x 2 ~ X 0 \ = \X\ - XQ\

then X2 is in e neighborhood. Furthermore, XQ = \{x% + X2); hence, xo is not

an extreme point. •

Remark 7.1.5 Not all boundary points of a convex set are necessarily ex-

treme points. Some boundary points may lie between two other boundary

points.

Proposition 7.1.6 Convex sets in R™ satisfy the following relations.

i. If X is a convex set and /3 £ R, the set (3X = {y : y = j3x, x G X} is

convex,

ii. If X and Y are convex sets, then the set X + Y = {z : z = x + y,x £

X,y EY} is convex.

Hi. The intersection of any collection of convex sets is convex.

o

©

(iii)

Fig. 7.2. Proof of Proposition 7.1.6

Proof. Obvious from Figure 7.2. •

Another important concept is to form the smallest convex set containing

a given set.

Definition 7.1.7 Let S C i". The convex hull of S is the set which is the

intersection of all convex sets containing S.

Definition 7.1.8 A cone C is a set such that ifxGC, then ax G C, Va €
R+. A cone which is also convex is known as convex cone. See Figure 7.3.