<<

. 22
( 59 .)



>>

L 
#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

<<

. 22
( 59 .)



>>