1a, x 2 - and 1a, x 2 ; 1a, y2. Thus 1a, y2 - . From this and from (3) we

I I

get that 1a, y2 : . Thus, each y in D is in H?. Since D 3 C, it follows that H?

a a

is a supporting hyperplane to C that contains D. Since the separation of C and

D is proper and since D 3 H?, there is an x in C such that 1a, x 2 : . Thus

a

the supporting hyperplane is nontrivial.

The next theorem is stronger than Theorem 4.3 but is only valid in ¬nite

dimensions.

T 7.4. L et C be a compact convex subset of RL. T hen C is the convex

hull of its extreme points.

Proof. Let C denote the set of extreme points of C. By Theorem 4.2 the set

C

C " `. Since C 3 C and co(C ) 3 co(C) : C, to prove the theorem, we must

C C C

show that

C 3 co(C ). (4)

C

The proof of (4) proceeds by induction on the dimension k of C.

If k : 0, then C is a point, and if k : 1, then C is a closed line segment. Thus

(4) holds in these cases. Now suppose that (4) holds if dim C : k 9 1, where

1 - k - n.

Let dim C : k and let x + C. By Theorem 7.1, either x + ri(C) or x belongs

to the relative boundary of C. If x belongs to the relative boundary of C, then

by Theorem 7.3, there exists a supporting hyperplane to C that contains x. This

hyperplane will intersect [C] in a manifold H that is a hyperplane of

I\

dimension k 9 1 in [C] and that supports C at x. The set H 5 C is

I\

compact and convex and has dimension -k 9 1. By the inductive hypotheses

x is a convex combination of the extreme points of H 5 C. By Lemma 4.1

I\

the extreme points of H 5 C are extreme points of C. Thus x + co(C )

I\ C

whenever x is a relative boundary point of C.

CONVEX SETS IN RL

86

If x + ri(C), let L be a line in [C] through the point x. Then L 5ri(C) is

a line segment (y, z) whose end points y and z are in the relative boundary of

C. Since C is compact, y + C and z + C. Since x is a convex combination of y

and z and since y and z are in co(C ), it follows that x + co(C ), and (4) is

C C

established.

Convexity and Optimization in n . Leonard D. Berkovitz

Copyright 2002 John Wiley & Sons, Inc.

ISBN: 0-471-35281-0

III

CONVEX FUNCTIONS

1. DEFINITION AND ELEMENTARY PROPERTIES

The simplest class of functions are real-valued functions that are translates of

linear functions, or af¬ne functions, f de¬ned by the formula f (x):1a, x2 ; b.

One could consider the next class of functions in order of complexity to be the

translates of the functions y : #x#N, p . 1. In R : (x, y), where x + R, the

graph of y : #x# is the upper nappe of a right circular cone with vertex at the

origin and the graph of y : #x# is a paraboloid of revolution. The graphs of

such functions are axially symmetric about a line parallel to the y-axis.

Intuitively, it appears that all of the above functions have the property that the

set of points (x, y) in RL> that lie on or above the graph is a convex set. It is

therefore reasonable to consider the next level of functions to be the functions

with this property. Such functions are called convex functions. It turns out that

convex functions are important in optimization problems as well as in other

areas of mathematics. We shall de¬ne convex functions using a different

property and then show in Lemma 1.1 below that our de¬nition is equivalent

to the one suggested.

De¬nition 1.1. A real-valued function f de¬ned in a convex set C in RL is said

to be convex if for every x and x in C and every . 0, . 0, ; : 1,

f ( x ; x ) - f (x ) ; f (x ). (1)

The function f is said to be strictly convex if strict inequality holds in (1).

The geometric interpretation of this de¬nition is that a convex function is a

function such that if z and z are any two points in RL> on the graph of f,

then points of the line segment [z , z ] joining z and z lie on or above the

graph of f.

Figure 3.1 illustrates the de¬nition. Let C : (x , w), where x : x ; x ,

9 0, 9 0, ; : 1, be a point on the line segment joining the points

A : (x , f (x )) and B : (x , f (x )) on the graph of f. Let D : (x , w) and let

87

88 CONVEX FUNCTIONS

Figure 3.1.

E : (x , f (x )). Then

f (x ) 9 w #BD# #BE# f (x ) 9 f (x )

.

: : :

#x 9 x # #CD# #AE# #x 9 x #

From the extreme terms of these equalities we get that

w : f (x ) ; (1 9 ) f (x ) : f (x ) ; f (x ).

Thus (x , w) lies above or on the graph if and only if (1) holds.

Note that if the domain of f is not convex, then the left-hand side of (1)

need not be de¬ned. Therefore, when de¬ning convex functions, it only makes

sense to consider functions de¬ned on convex sets. Henceforth we shall not

repeat the term real-valued when considering convex functions; it shall be

tacitly assumed that f is real valued.

De¬nition 1.2. A function f de¬ned on a convex set C is said to be concave if

9f is convex.

De¬nition 1.3. Let f be a real-valued function de¬ned on a set A. The epigraph

of f, denoted by epi( f ), is the set

epi( f ) : +(x, y) : x + A, y + R, y . f (x),.

In Figure 3.2 the hatched areas represent the epigraphs of y : x, 91 -

x - 1, and y : x, 91 - x - 1.

The epigraph of a function is the set of points (x, y) in RL> that lie on or

above the graph of f.

DEFINITION AND ELEMENTARY PROPERTIES 89

Figure 3.2.

L 1.1. A function f de¬ned on a convex set C is convex if and only if epi( f )

is convex.

Proof. Suppose that epi( f ) is convex. Let x and x belong to C. Then

(x , f (x )) and (x , f (x )) belong to epi( f ). Since epi( f ) is convex, for any

( , )+P

(x , f (x )) ; (x , f (x )) : ( x ; x , f (x ) ; f (x ))

belongs to epi( f ). By the de¬nition of epi( f ),

f (x ) ; f (x ) . f ( x ; x ),

and so f is convex.

Now suppose f is convex. Let (x , y ) and (x , y ) be any two points in

epi( f ). Then y . f (x ) and y . f (x ). For any ( , ) in P let

(x , y) : (x , y ) ; (x , y ) : ( x ; x , y ; y ).

Since (x , y ) and (x , y ) are in epi( f ), and since f is convex, we have

y : y ; y . f (x ) ; f (x ) . f ( x ; x ) : f (x ).

Thus, (x , y) + epi( f ), and so epi( f ) is convex.

L 1.2. If f is a convex function de¬ned on a convex set C in RL, then for

any real the set +x : f (x) - , is either empty or convex.

We leave the proof of this lemma as an exercise for the reader.

The converse to this lemma is false, as can be seen from the function

f (x) : x.

90 CONVEX FUNCTIONS

L 1.3. L et + f , be a family of convex functions de¬ned on a convex set

?

C in RL and let there exist a real-valued function M with domain C such that, for

each , f (x) - M(x) for all x in C. T hen the function f de¬ned by f (x) :

?

sup+ f (x) : , is convex.

?

Proof. Since for each x in C f (x) - M(x) for all , it follows that

?

f (x) - M(x), and so f is real valued. Also epi( f ) : 7 epi( f ), so epi( f ), being

? ?

the intersection of convex sets, is convex. Therefore f is convex.

T 1.1 (J®®™ I®±µ¬©). L et f be a real-valued function de¬ned on

a convex set C in RL. T hen f is convex if and only if for every ¬nite set of points

x , . . . , x in C and every : ( , . . . , ) in P

I I I

f ( x ; % ; x ) - f (x ) ; % ; f (x ). (2)

II I I

Proof. If (2) holds for all positive integers k, then it holds for k : 2. But for

k : 2, the relation (2) is the de¬nition of convex function.

Now suppose that f is convex. We shall prove (2) by induction on k. For

k : 1 the relation is trivial. For k : 2 the relation follows from the de¬nition

of a convex function. Suppose that k 9 2 and that (2) has been established for

k 9 1. We shall show that (2) holds for k. If : 1, then there is nothing to

I

prove. If " 1, set : I\ . Then

G G

I

I\

G : 1,

9 0, ; : 1,

I

G

and we may write (compare the proof of Lemma II.2.6)

I I\

Gx;x

f x :f

GG G II

G G

I\

G x ; f (x )

-f

G I I

G

- f (x ) ; % ; f (x ) ; f (x ),

I\ I\ I I

where the ¬rst inequality follows from the convexity of f and the second

inequality follows from the inductive hypothesis.

The next lemma in conjunction with other criteria is sometimes useful in

determining whether a given function is convex.

L 1.4. L et f be a convex function de¬ned on a convex set C in RL. L et g

be a nondecreasing convex function de¬ned on an interval I in R. L et f (C) 3 I.

T hen the composite function g ° f de¬ned by (g ° f )(x) : g( f (x)) is convex on C.

DEFINITION AND ELEMENTARY PROPERTIES 91

We leave the proof as an exercise.

Let C be a convex set. Choose an x in C and a v in RL. Let

: + : + R, x ; v + C,.

Let l : sup+ : + , and let l : inf+ : + ,. Then l - 0 - l . If l " l ,

then since C is convex, x ; v + C for all in the open interval (l , l ). Note

that, depending on the structure of the set C, x ; v can belong to C for all

in [l , l ) or [l , l ] or (l , l ].

Let f be a convex function de¬ned on a convex set C. From the discussion

in the preceding paragraph it follows that for each x in C and each v in RL

there is an interval I 3 R that depends on x and v such that the function

( ; x, v) de¬ned by

( ; x, v) : f (x ; v) (3)

has I as its domain of de¬nition. The interval I always includes the origin and

can degenerate to the single point +0,; it can be open, half open, or closed. The

function ( ; x, v) gives the one-dimensional section of the function f through