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