<<

. 21
( 59 .)



>>

the point x in the direction of v. The next lemma states that f is convex if and
only if all the nondegenerate one-dimensional functions ( ; x, v) are convex.

L 1.5. A function f de¬ned on a convex set C is convex if and only if for
each x in C and v in RL such that ( ; x, v) is de¬ned on a nondegenerate interval
I the function ( ; x, v) is convex on I.
Proof. Suppose that f is convex. Then for any , in I and ( , ) in P ,
 
; ; x, v) : f (x ; ( ; )v)
(
   
: f ( (x ; v) ; (x ; v))
 
!
?>@
- f(x ; v) ; f (x ; v)
 
!
D  
: ( ; x, v) ; ( ; x, v).
 
!
P
This proves the convexity of ( ; x, v).
Now suppose that for each x in C and v in RL such that I " +0,, ( ; x, v)
is convex. Let x and x be in C and let ( , ) be in P . Then
  
f ( x ; x ) : f ((1 9 )x ; x )
   
: f (x ; (x 9 x )) : ( ; x , x 9 x )
    
: ( · 0 ; · 1; x , x 9 x ). (4)
 
92 CONVEX FUNCTIONS


Since

( ; x , x 9 x ) : f (x ; (x 9 x ))
    
and since C is convex, ( ; x , x 9 x ) is de¬ned for 0 - - 1 and
 
(0; x , x 9 x ) : f (x ), (1; x , x 9 x ) : f (x ). (5)
     
From the convexity of ( ; x , x 9 x ) and (5) we get that the rightmost side
 
of (4) is less than or equal to

(0; x , x 9 x ) ; (1; x , x 9 x ) : f (x ) ; f (x ).
     
Hence f is convex.

Remark 1.1. An examination of the proof shows that f is strictly convex if and
only if, for each x and v, ( ; x, v) is strictly convex.

We now present some results for convex functions de¬ned on real intervals.
The ¬rst result is the so-called three-chord property.

T 1.2. L et g be a convex function de¬ned on an interval I : R. T hen if
x : y : z are three points in I,

g(y) 9 g(x) g(z) 9 g(x) g(z) 9 g(y)
- - (6)
.
y9x z9x z9y

If g is strictly convex, then strict inequality holds.

Figure 3.3 illustrates the theorem and shows why the conclusion of the
theorem is called the three-chord property.
Proof. Since x : y : z, there exists a 0 : t : 1 such that y : x ; t(z 9 x).
Since g is convex,

g(y) 9 g(x) : g((1 9 t)x ; tz) 9 g(x)
- (1 9 t)g(x) ; tg(z) 9 g(x)
: t(g(z) 9 g(x)). (7)

If in (7) we now divide through by t(z 9 x) 9 0 and note that y 9 x : t(z 9 x),
we get that

g(y) 9 g(x) g(z) 9 g(x)
- .
y9x z9x
DEFINITION AND ELEMENTARY PROPERTIES 93




Figure 3.3.



To obtain the second inequality, we write

g(z) 9 g(y) : g(z) 9 g(x ; t(z 9 x))

. g(z) 9 (1 9 t)g(x) 9 tg(z)

: (1 9 t)[g(z) 9 g(x)].

If we now divide through by z 9 y 9 0 and note that z 9 y : (1 9 t)(z 9 x),
we obtain the second inequality.

C¬¬ 1. For each c in I the slope function s( ; c) de¬ned by

g(w) 9 g(c)
s(w ; c) : w " c, w + I,
,
w9c

is an increasing function. If g is strictly convex, then s( ; c) is strictly increasing.

Proof. We must show that if w : w , then
 

s(w ; c) - s(w ; c). (8)
 

For two points w and w such that c : w : w , inequality (8) follows from
   
(6) by taking x : c, y : w , and z : w . For two points w and w such that
   
w : w : c, inequality (8) follows from (6) by taking z : c, x : w , and
  
y : w . Lastly, if w : c : w , the inequality (8) follows from (6) by taking
  
y : c, x : w , and z : w .
 
94 CONVEX FUNCTIONS


Let f be a real-valued function de¬ned on an interval I. If at a point c in I

f (c ; h) 9 f (c)
lim
h
F>
exists, then f is said to have a right-hand derivative at c whose value f  (c) is
>
the value of the above limit. Similarly, the left-hand derivative of f at c, denoted
by f  (c), is
\
f (c ; h) 9 f (c)
lim
h
F>\
provided the limit exists.

C¬¬ 2. At each point c in int(I) the right- and left-hand derivatives g (c)
>
and g (c) exist and g (c) - g (c). Moreover, g and g are increasing
\ \ > > \
functions.
Proof. In (6) take y : c. Then for x : c : z we have

g(x) 9 g(c) g(z) 9 g(c)
- .
x9c z9c

It follows from this relation, from Corollary 1, and from Exercise I.6.6. that
g (c) and g (c) exist and g (c) - g (c).
\ > \ >
Now let c : d be two points in int(I) and let h 9 0 be such that c ; h : d
and d 9 h 9 c. Then by Theorem 1.2

g(c ; h) 9 g(c) g(d) 9 g(c) g(d 9 h) 9 g(d)
- - .
h d9c 9h

If we now let h ; 0>, we get g (c) - g\(d). Combining this with g (x) - g (x)
> \ \ >
for any x in int(I), we get

g (c) - g (c) - g (d) - g (d),
\ > \ >
which gives the desired monotonicity properties.

Remark 1.2. If c is a left-hand end point of I and g is de¬ned at c, then from
the monotonicity of s( ; c) it follows that g (c) always exists if we permit the
>
value 9-.

The next corollary is an immediate consequence of Corollary 2 and is a
result that the reader encountered in elementary calculus.
DEFINITION AND ELEMENTARY PROPERTIES 95


C¬¬ 3. If g is convex and twice differentiable on I, then g is an increasing
function on I and g(x) . 0 for all x in I.

We can now return to functions de¬ned on RL.

De¬nition 1.4. Let f be a real-valued function de¬ned on a set S in RL. Let x
be a point in S and let v be a vector in RL such that x ; v belongs to S for
in some interval [0, l). Then f is said to have a directional derivative at x in the
direction v if

f (x ; v) 9 f (x)
lim
H>

exists. We denote the directional derivative by f (x ; v).

L 1.6. L et f be a convex function de¬ned on a convex set C and let x be a
point of C. If x is an interior point, then f (x ; v) exists for every v in RL. If x is
a boundary point and v is a vector in RL such that x ; v belongs to C for
suf¬ciently small 9 0, then f (x ; v) exists if we allow the value 9-.

Proof. If x is an interior point of C, then for each v in RL there exists a
: (v) such that for " " : the point x ; v is in C.
positive number
  
Hence the function ( ; x, v) of (3) is de¬ned for " " : . By Lemma 1.5,

( ; x, v) is convex, and so by Corollary 2 of Theorem 1.2,  (0; x, v) exists. But
>

( ; x, v) 9 (0; x, v) f (x ; v) 9 f (x)
: ,


and so f (x, v) exists and equals  (0; x, v). If x is a boundary point of C, the
>
assertion follows from similar arguments and Remark 1.1.

In the next lemma we record a useful inequality.

L 1.7. L et f be a convex function de¬ned on a convex set C. L et x and y be
points in C and let z : x ; t(y 9 x), 0 : t : 1. T hen

f (z) 9 f (x)
f (y) 9 f (x) . (9)
.
t

Proof. The function ( ; x, y 9 x) in (3) is de¬ned for 0 - t - 1, with
(1; x, y 9 x) : f (y), (0; x, y 9 x) : f (x) and (t; x, y 9 x) : f (z) for 0 :
96 CONVEX FUNCTIONS


t : 1. By Corollary 1 to Theorem 1.2,

(t ; x, y 9 x) 9 (0; x, y 9 x)
(1; x, y 9 x) 9 (0; x, y 9 x) . ,
t

which is the same as (9).
We note that (9) can also be established directly from the de¬nition of a
convex function.

We next show that a convex function is continuous on the interior of its
domain of de¬nition.

T 1.3. L et f be a convex function de¬ned on a convex set C in RL. If x is
an interior point of C, then f is continuous at x.

If x is not an interior point of C, then f need not be continuous at x, as
the following example shows. Let C : [91, 1] 3 R and let f (x) : x for
91 : x : 1 and f (91) : f (1) : 2. The function f is convex on [91, 1] since
epi( f ) is convex, but f is discontinuous at <1.
We now prove the theorem.
If x is an interior point of C, then there exists a 9 0 such that B(x, ) : C.
Let : /(n. Let C denote the cube with center at x and length of side equal
B
to 2 ; that is,

C : +y : "y 9 x " - , i : 1, . . . , n,.
B G G
Since

<<

. 21
( 59 .)



>>