where m(h) ; 0 as h ; 0, give (9) with (h) : 1h, M(h)h2.

C¬¬ 1 (T¬™ T). L et D be an open set in RL and let f be a

real-valued function de¬ned in D. If f is of class C in D, then for each x in D

and h such that x ; h is in D

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

f (x ; t h), h2, (16)

where 0 : t : 1. If f is of class C , then

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

f (x ), h2 ; 1h, H(x ; t h)h2, (17)

where 0 : t : 1.

Proof. Equation (16) follows from (14) and equation (17) from (15).

We now give a condition under which the existence of partial derivatives

does imply differentiability.

T 11.3. L et D be an open set in RL, let f be a function de¬ned on D with

range in RK, and let x be a point in D. If f is of class C on some open ball

B(x , r) centered at x , then f is differentiable at x .

Proof. Since each component function f , i : 1, . . . , m, is of class C , from

G

(8) of Theorem 11.2 we have that

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

f (x ), h2 ; (h),

G G G G

where (h)/#h# ; 0 as h ; 0.

G

Let (h) : ( (h), . . . , (h)). Then

K

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

f(x )h ; (h),

where (h)/#h# ; 0 as #h# ; 0. Therefore f is differentiable at x .

Convexity and Optimization in n . Leonard D. Berkovitz

Copyright 2002 John Wiley & Sons, Inc.

ISBN: 0-471-35281-0

II

CONVEX SETS IN RL

1. LINES AND HYPERPLANES IN RL

Convex sets and convex functions play an important role in many optimization

problems. The study of convex sets in RL, in turn, involves the notions of line

segments, lines, and hyperplanes in RL. We therefore begin with a discussion of

these objects.

In R and R the vector equation of a line and in R the vector equation of

a plane are obtained from geometric considerations. In RL we shall reverse this

process. We shall de¬ne a line to be the set of points satisfying an equation

which in vector notation is the same as that of a line in R or R. We shall

de¬ne a hyperplane in RL in similar fashion.

In R and R a vector equation of the line through two points x and x is

given by (see Figure 2.1)

x : x ; t(x 9 x ), 9- : t : -. (1)

The closed oriented line segment [x , x ] with orientation from initial point

x to terminal point x corresponds to values of t in [0, 1]. The positive ray

from x corresponds to values of t . 0, and the negative ray from x

corresponds to values of t - 0.

In RL we de¬ne the line through two points x and x to be the set of points

x in RL that satisfy (1). Thus:

De¬nition 1.1. The line in RL through two points x and x is de¬ned to be

the set of points x such that x : x ; t(x 9 x ), where t is any real number,

or in set notation

+x : x : x ; t(x 9 x ), 9- : t : -,. (2)

The set in (2) can also be written as

+x : x : (1 9 t)x ; tx , 9- : t : -,, (3)

30

LINES AND HYPERPLANES IN RL 31

Figure 2.1.

and, on setting : (1 9 t), : t,

+x : x : x ; x , ; : 1,. (4)

De¬nition 1.2. The closed line segment joining the points x and x is denoted

by [x , x ] and is de¬ned by

[x , x ] : +x : x : (1 9 t)x ; tx , 0 - t - 1,,

or equivalently,

[x , x ] : +x : x : x ; x , . 0, . 0, ; : 1,.

De¬nition 1.3. The open line segment joining the points x and x is denoted

by (x , x ) and is de¬ned by

(x , x ) : +x : x : (1 9 t)x ; tx , 0 : t : 1,,

or equivalently,

(x , x ) : +x : x : x ; x , 9 0, 9 0, ; : 1,.

The half-open segment which includes x but not x will be denoted by

[x , x ) and is obtained by restricting t to the half-open interval 0 - t : 1, or

equivalently by restricting and to satisfy 9 0, . 0, ; : 1. Similarly,

the half-open line segment which includes x but not x will be denoted by

(x , x ] and is obtained by restricting t to the half-open interval 0 : t - 1, or

equivalently by restricting and to satisfy . 0, 9 0, ; : 1.

CONVEX SETS IN RL

32

Figure 2.2.

Let y be a point in the open line segment (x , x ). Then y : x ; x ,

9 0, 9 0, ; : 1, and y 9 x : x 9 (1 9 )x : (x 9 x ). Similarly

y 9 x : (x 9 x ). Hence

#y 9 x #

: . (5)

#y 9 x #

This observation will be useful in the sequel.

In R a plane through the point x with normal a consists of all points x

such that x 9 x is orthogonal to a. Thus, the plane is the set de¬ned by (see

Figure 2.2)

+x : 1a, x 9 x 2 : 0,.

If a : (a , a , a ) and x : (x , x , x ), we can describe the plane as the set

of x : (x , x , x ) satisfying

a (x 9 x ) ; a (x 9 x ) ; a (x 9 x ) : 0

or

a x ;a x ;a x : ,

LINES AND HYPERPLANES IN RL 33

where : a x ; a x ; a x . These are the familiar forms of the equation

of a plane in R. In vector notation these equations can be written as

1a, x 9 x 2 : 0 or 1a, x2 : , (6)

where : 1a, x 2. Conversely, every equation of the form (6) is the equation

of a plane with normal vector a. To see this, let x be a point that satis¬es (6).

Then 1a, x 2 : , so if x is any other point satisfying (6), 1a, x2 : 1a, x 2.

Hence 1a, x 9 x 2 : 0 for all x satisfying (6). But 1a, x 9 x 2 : 0 is an

equation of the plane through x with normal a.

In RL we take (6) to de¬ne a hyperplane.

De¬nition 1.4. A hyperplane H? in RL is de¬ned to be the set of points that

a

satisfy the equation 1a, x2 : . Thus

H? : +x : 1a, x2 : ,.

a

The vector a is said to be a normal to the hyperplane.

As was the case in R, H? : +x : 1a, x2 : , can be written as

a

+x : 1a, x9x 2:0,

for any x satisfying 1a, x 2 : , or equivalently for any x in H?. Thus we may

a

say that an equation of the hyperplane in RL through the point x with normal

a is

1a, x 9 x 2 : 0. (7)

Note that in R a hyperplane is a line.

Recall that an (n 9 1)-dimensional subspace of RL can be represented as the

set of vectors x : (x , . . . , x ) whose coordinates satisfy a x ; % ; a x : 0

L LL

for some nonzero vector a : (a , . . . , a ). Thus, if : 0 and a " 0, then the

L

hyperplane H passes through the origin and is an (n 9 1)-dimensional

a

subspace of RL.

In Section 10 of Chapter I we saw that for a given linear functional L on

RL there exists a unique vector a such that L(x) : 1a, x2 for all x in RL. This

?

representation of linear functionals and the de¬nition of the hyperplane Ha

show that hyperplanes are level surfaces of linear functionals. This interpreta-

tion will prove to be very useful.

Let A be any set in RL and let x be any vector in RL. The set A ; x is

de¬ned to be

A ; x : +y : y : a ; x , a + A,

CONVEX SETS IN RL

34

and is called the translate of A by x .

L 1.1 For any a in RL and scalar , the hyperplane H? is the translate of

a

H, the hyperplane through the origin with normal a, by any vector x in H?.

a a

Proof. Fix an x in H?. Let x be an arbitrary point in H? and let u : x 9 x .

a a

Then

: 1a, x2 : 1a, u ; x 2 : 1a, u2 ; .

Thus 1a, u2 : 0 and so u + H. Since x : x ; u, we have shown that

a