#y 9 x# : "x 9 y " ,

G G

G

it follows that if "x 9y "- /(n for each i, then #y9x# - . Thus C 3 B(x, ).

GG B

On the other hand, if #y 9 x# - , then we cannot have "y 9 x " 9 for any

H H

index j in set 1, . . . , n. Hence B(x, ) 3 C .

B

The ¬rst step in the proof is to show that f is bounded above on B(x, ). It

is easier to show that f is bounded above on the larger set C than to work

B

directly with B(x, ). Let C denote the set of 2L vertices of C . By Exercise

BC B

II.4.7(a), the set C is the set of extreme points of C . By Theorem II.4.3,

BC B

C : co(C ). But C is compact, so by Lemma II.2.7, co(C ) is compact.

B BC BC BC

Hence

C : co(C ) : co(C ).

B BC BC

[We could also conclude this directly from Exercise II.4.7 (b).] Thus, for each

DEFINITION AND ELEMENTARY PROPERTIES 97

y in C , there exists a p in P such that

B L

L

y: p v ,

GG

G

where the v are the vertices of C .

G B

Let

M : max+ f (v) : v + C ,.

BC

Then by the convexity of f and Theorem 1.1 (Jensen™s inequality), for each y

in C

B

L L

f (y) - p f (v ) - p M : M.

GG G

G G

Thus, since B(x, ) 3 C ,

B

f (y) - M for y in B(x, ). (10)

Let z " x be an arbitrary point in B(x, ), and consider the line determined

by x and z. This line will intersect the surface of B(x, ) at two points, x ; u

and x 9 u, where u : t(z 9 x) for some t 9 1 and #u# : . See Figure 3.4.

We shall use the bound on f and the convexity of f to estimate

" f (z) 9 f (x)"

in terms of #z 9 x# and thus prove the continuity of f at x. To this end, we

Figure 3.4.

98 CONVEX FUNCTIONS

¬rst express z as a convex combination of x and x ; u. Thus

z : (1 9 )x ; (x ; u) : x ; u, 0 : : 1. (11)

Therefore, : #z 9 x# \. We next express x as a convex combination of z

and x 9 u. Thus

x : (1 9 t)(x 9 u) ; tz, 0 : t : 1.

Recalling relation (1) in Section 1 of Chapter II and using the relation :

#z 9 x# \, we see that

t(1 9 t)\ : #z 9 x#\ : \,

and so t : (1 ; )\. Therefore,

1

x: z; (x 9 u). (12)

1; 1;

Since f is convex, we have, using (10), (11), and (12),

f (z) - (1 9 ) f (x) ; f (x ; u) - (1 9 ) f (x) ; M,

1 1

f (x) - f (z) ; f (x 9 u) - f (z) ; M.

1; 1; 1; 1;

From these inequalities we get

9 [M 9 f (x)] - f (z) 9 f (x) - [M 9 f (x)].

Hence, for z + B(x, )

" f (z) 9 f (x)" - \[M 9 f (x)]#z 9 x#, (13)

from which the continuity of f at x follows.

Remark 1.3. A function f de¬ned on a set D in RK with range in RK is said to

be L ipschitz continuous on D if there exists a constant K 9 0 such that

#f(x) 9 f (y)# - K#y 9 x#

for all x, y in D. Since a real-valued continuous function de¬ned on a compact

set is bounded above and below, relation (13) implies that a convex function

de¬ned on an open convex set C is Lipschitz continuous on every compact

subset contained in C.

DEFINITION AND ELEMENTARY PROPERTIES 99

Remark 1.4. The proof of Theorem 1.3 can easily be modi¬ed to show that if

f is convex on a convex set C, then f is continuous on ri(C).

In Section 11 of Chapter I we saw that the existence of partial derivatives

at a point does not imply differentiability. For convex functions, however, the

existence of partial derivatives at a point does imply differentiability.

T 1.4. L et f be a convex function de¬ned on a convex set C. If the partial

derivatives of f with respect to each variable exist at an interior point x of C, then

f is differentiable at x.

Proof. De¬ne the function on RL by

L *f

(h) : f (x ; h) 9 f (x) 9 (x)h .

H

*x

H H

To prove that f is differentiable at x, we must show that

(h)

; 0 as #h# ; 0. (14)

#h#

Let

f (x ; nh e ) 9 f (x) *f

GG

: 9 (x).

G nh *x

G G

Since f is convex and a linear function is concave and convex, the function

is convex. Thus

L nh e 1L

G G - (nh e )

(h) :

GG

n n

G G

L L L

: h - " " "h " - " " #h# (15)

GG GG G

G G G

for i : 1, . . . , n. The existence of the partial derivatives implies that each of the

; 0 as #h# ; 0. Also,

G

h ; (9h) (h) ; (9h)

0 : (0) : - .

2 2

Hence

L

" " #h#,

(h) . 9 (9h) . 9 (16)

G

G

100 CONVEX FUNCTIONS

where, for each i : 1, . . . , n, ; 0 as #h# ; 0. We now obtain (14) from (15)

G

and (16).

Exercise 1.1. Show that if f and g are convex functions de¬ned on a convex

set C, then for any 9 0, 9 0, the function f ; g is convex.

Exercise 1.2. Let + f , be a sequence of convex functions de¬ned on a convex

L

set C. Show that if f (x) : lim f (x) exists for all x + C, then f is convex.

L L

Exercise 1.3. Prove Lemma 1.2.

Exercise 1.4. Prove Lemma 1.4.

Exercise 1.5. Let I : [a, b] be a real interval and let C be a convex set in RL.

Let f : (t, x) ; f (t, x) be a real-valued function de¬ned on I ; C that is

continuous on I for each ¬xed x in C and is convex on C for each ¬xed t in I.

Show that

@

F(x) : f (t, x) dt

?

is de¬ned for each x in C and that F is convex on C.

Exercise 1.6. (a) Show that any norm on RL is convex on RL.

(b) Let S be a nonempty convex set, and let # · # denote the euclidean norm

in RL. Let f be the distance function to S de¬ned by

f (y) : inf+#y 9 x# : x + S,.

Show that f is convex on RL.

(c) Show that f is Lipschitz continuous on compact subsets of RL.

Exercise 1.7. Let f be a convex function de¬ned on RL. Let x be a ¬xed point

in RL. Show that the function d(·) : RL ; R de¬ned by d(v) : f (x ; v) is (a)

positively homogeneous [i.e., for 9 0, d( v) : d(v)] and (b) convex.

Exercise 1.8. Let g be a concave function de¬ned on RL. Let S : +x : g(x) 9 0,

be nonempty.

(a) Show that S is convex.

(b) Show that if f (x) : 1/g(x) for x in S, then f is convex on S.

DEFINITION AND ELEMENTARY PROPERTIES 101

Exercise 1.9. Let C be a convex cone (see Exercise II.2.10 for the de¬nition).

A real-valued function g de¬ned on C is said to be a gauge function on C if

(a) g( x) : g(x) for all x in C and . 0 and

(b) g(x ; y) - g(x) ; g(y) for all x, y in C.

Show that g is convex.

Exercise 1.10. Let C be a convex set. The support function s of C is the

real-valued function de¬ned by

s(u) : sup+1u, x2 : x + C,

for all u such that the supremum is ¬nite.

(a) Show that if the domain D of s is nonempty, then D is in a convex cone.

(b) Show that s is a gauge function on D.

Exercise 1.11. Let C be a compact convex set with 0 + int(C). The Minkowski

distance function p determined by C is de¬ned by

p(x) : inf+ : . 0, x + C,.

Show that p is a gauge function.

Exercise 1.12. Let C be a compact convex set and let s be its support function.

Show that the following statements hold:

(a) The domain of s is RL.

(b) For each u " 0 there exists a point xu in C such that s(u) : 1u, xu2.

(c) The hyperplane Hu : +x : 1u, x2 : s(u), supports C at xu .

(d) The distance from Hu to 0 is equal to s(u/#u#).

Exercise 1.13. Let C be a nonempty closed convex set C " RL. Let s be the

support function of C with nonempty domain D. Show that

C : +x : 1u, x2 - s(u) for all u in D,.

Hint: An alternate de¬nition of C is

C : 7 +x : 1u, x2 - s(u), u ¬xed in D,,

u+D

and see Exercise II.4.6.

102 CONVEX FUNCTIONS