<<

. 20
( 59 .)



>>

I I
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

<<

. 20
( 59 .)



>>