(x) : #x# : max+"x ", . . . , "x ",.

L

The corresponding distance is de¬ned by

(x, y) : #x 9 y# : max+"x 9 y ", . . . , "x 9 y ",.

L L

Since a norm determines the family of open sets and since the family of open

sets determines convergence, the question arises, ˜˜Given two norms, and ,

do they determine the same family of open sets?™™ The answer, which is not

dif¬cult to show, is, ˜˜If there exist positive constants m and M such that for all

x in RL,

m (x) - (x) - M (x), (1)

then a set is open under the norm if and only if it is open under the norm

that satisfy (1) are said to be equivalent norms.

.™™ Two norms and

An extremely important fact is that in RL all norms are equivalent. For a

proof see Fleming [1977]. In optimization theory, and in other areas, it may

happen that the analysis of a problem or the development of a computational

algorithm is more convenient in one norm than in another. The equivalence of

the norms guarantees that the convergence of an algorithm is intrinsic, that is,

is independent of the norm.

Let A , . . . , A be m sets with A 3 RLG, i : 1, . . . , m. By the cartesian product

K G

of these sets, denoted by

K

“ A or A ; A ; % ; A ,

G K

G

we mean the set A in RL >L‚>LK consisting of all possible points in RL >>LK

obtained by taking the ¬rst n components from a point in A , the next n

components from a point in A , the next n components from a point in A ,

EQUIVALENT NORMS AND CARTESIAN PRODUCTS 17

and so forth, until the last n components, which are obtained by taking a

K

point in A . For example, RL can be considered to be the cartesian product of

K

R taken n times with itself:

RL : R;R;%;R.

L

If A is the set in R consisting of points on the circumference of the circle with

center at the origin and radius 1 and if A : [0, 1] in R, then A ; A is the

set in R that is the lateral surface of a cylinder of height 1 whose base is the

closed disk in the (x , x ) plane with center at the origin and radius equal to 1.

Let X : RL ; % ; RL K. Let x be a vector in X. Then x : (x , . . . , x ),

K

where x : (x , . . . , x ), i : 1, . . . , m. If for vectors x and y in X and scalars

GG GLG

G

+ R we de¬ne

(x ; y) : (x ; y , . . . , x ; y ), x:( x ,.. ., x )

K K K

and let n : n ; n ; % ; n , then X can be identi¬ed with the usual vector

K

space RL. The euclidean norm in X would then be given by

K LG

#x# : [#x # ; % ; #x #] : (x ) (2)

.

K GH

G H

On the other hand, in keeping with the de¬nition used in more general

contexts, the norm on X is de¬ned by

K

#x# : #x #, (3)

L G

G

where #x # is the euclidean norm of x in RL G, de¬ned by #x # : 1x , x 2 :

G G G GG

[ LG (x )]. Since all norms on RL are equivalent, the norm de¬ned by (3)

H GH

is equivalent to the euclidean norm de¬ned by (2).

The following lemma is an immediate consequence of the de¬nition of #·# .

L

L 8.1. A sequence x : (x , . . . , x ) of points in X converges to a point

I I IK

x : (x , . . . , x ) of X in the metric determined by #·# if and only if for each

K L

i : 1, . . . , m the sequence +x , converges to x in the euclidean norm on RL G.

IG G

The next theorem can be proved by using Lemma 8.1 and Theorem 7.1 and

by selecting appropriate subsequences.

T 8.1. L et A , . . . , A be m sets with A : RL G and let each A be compact,

K G G

i : 1, . . . , m. T hen K A is compact in RL, where n : n ; n ; % ; n .

G G K

18 TOPICS IN REAL ANALYSIS

Exercise 8.1. (a) In R sketch the set B (0, 1) : +x : #x# : 1,.

(b) Show that # # is a norm [i.e., that it satis¬es (1)”(3) and (5) of Sec-

tion 2].

(c) Can you draw a sketch in R that would indicate that a set is open under

the metric d(x, y) : #x 9 y# if and only if it is open under the metric (x, y) :

#x 9 y# ?

(d) Is it true that #x ; y# : #x# ; #y# if and only if y : x, 9 0?

Exercise 8.2. (a) Show that the function #·# de¬ned by (3) is a norm on X;

L

that is #·# satis¬es (1)”(3) and (5) of Section 2.

L

(b) If X : R : R ; R, sketch the set B (0, 1) : +x : #x# - 1,.

L L

Exercise 8.3. Without using the fact that all norms in RL are equivalent, show

that #·# and #·# de¬ned by (2) and (3), respectively, are equivalent norms

L

on X.

Exercise 8.4. Show that the following functions are continuous:

(a) f : RL ; RL ; RL, where f (x, y) : (x ; y) (addition is continuous);

(b) f : R ; RL ; RL, where f ( , x) : x (scalar multiplication is continu-

ous); and

(c) f : RL ; RL ; R, where f (x, y) : 1x, y2 (scalar product is continuous).

Exercise 8.5. Prove Theorem 8.1.

Exercise 8.6. Show that if Q is a positive-de¬nite real symmetric matrix, then

(x) : 1x, Qx2 de¬nes a norm on RL. Hint: Look at Section 1.

9. FUNDAMENTAL EXISTENCE THEOREM

The basic problem in optimization theory is as follows: Given a set S (not

necessarily in RL) and a real-valued function f de¬ned on S, does there exist

an element s in S such that f (s ) - f (s) for all s in S, and if so ¬nd it. The

* *

problem as stated is a minimization problem. The point s is said to be a

*

minimizer for f, or to minimize f. We also say that ˜˜f attains a minimum on S

at s ™™ The problem of ˜˜maximizing f over S,™™ or ¬nding an s* in S such that

*

f (s*) . f (s) for all s, can be reduced to the problem of minimizing the function

9 f over S. To see this, observe that if 9 f (s*) - 9 f (s) for all s in S, then

f (s*) . f (s) for all s in S, and conversely.

The ¬rst question that we address is, ˜˜Does a minimizer exist?™™ To point

out some of the dif¬culties here, we look at some very simple examples in R.

FUNDAMENTAL EXISTENCE THEOREM 19

Let S : +x : x . 1, and let f (x) : 1/x. It is clear that inf+ f (x) : x . 1, : 0, yet

there is no x + S such that f (x ) : 0. Thus a minimizer does not exist, or f

* *

does not attain its minimum on S. As a second example, let S : [1, 2) and let

f (x) : 1/x. Now, inf( f (x) : 1 - x : 2, : , yet for no x in S do we have

*

f (x ) : , Of course, if we modify the last example by taking

*

S : [1, 2] : +x : 1 - x - 2,, then x : 2 is the minimizer. For future reference,

*

note that if S : (1, 2] : +x : 1 : x - 2,, then x : 2 is still the minimizer.

*

We now state and prove the fundamental existence theorem for minimiz-

ation of functions with domains in RL.

T 9.1. L et S be a compact set in RL and let f be a real-valued continuous

function de¬ned in S. T he f attains a maximum and a minimum on S.

Before taking up the proof, we point out that the theorem gives a suf¬cient

condition for the existence of a maximizer and minimizer. It is not a necessary

condition, as the example in R, S : (1, 2], f (x) : 1/x, shows. In more

advanced courses the reader may encounter the notions of upper semicontinu-

ity and lower semicontinuity and learn that continuity can be replaced by

upper semicontinuity to ensure the existence of maximizers and that continuity

can be replaced by lower semicontinuity to ensure the existence of minimizers.

Finally, the reader should study the proof of this theorem very carefully and

be sure to understand it. The proof of the theorem in RL is the model for the

proofs of the existence of minimizers in more general contexts than RL.

Proof. If f is continuous on S, then so is 9 f. If 9 f attains a minimum on

S, then f attains a maximum on S. Thus we need only prove that f attains a

minimum.

We ¬rst prove that the set of values that f assumes on S is bounded below,

that is, that the set R : +y : y : f (x), x + S, is bounded below. To show this,

we suppose that R were not bounded below. Then for each positive integer k

there would exist a point x in S such that f (x ) : 9k. Since S is compact, the

I I

sequence +x , of points in S has a subsequence +x , that converges to a point

IH

I

x in S. The continuity of f implies that lim f (x ) : f (x ). Thus, by the

H IH

* *

de¬nition of limit (taking : 1) we have that there exists a positive integer K

such that, for j 9 K, f (x ) 9 f (x ) 9 1. This contradicts the de¬ning property

IH *

of +x ,, namely that, for each k, f (x ) : 9k.

I I

Since the set R is bounded below, it has an in¬mum, say L . Therefore, by

de¬nition of in¬mum, for each positive integer k there exists a point x in S

I

such that

1

L - f (x ) : L ; . (1)

I k

Since S is compact, the sequence +x , has a subsequence +x , that converges

IH

I

20 TOPICS IN REAL ANALYSIS

to a point x in S. The continuity of f implies that lim f (x ) : f (x ).

H I

* *

Therefore, if we replace k by k in (1) and let j ; -, we get that L - Hf (x ) - L .

H *

Hence

f (x ) : L - f (x) for all x + S.

*

This proves the theorem.

If the reader understands the proof of Theorem 9.1 and understands the use

of compactness, he or she should have no trouble in proving the following

theorem. Actually, Theorem 9.1 is a corollary of Theorem 9.2.

T 9.2. L et S be a compact subset of RL and let f : ( f , . . . , f ) be a

K

continuous function de¬ned on S with range in RK. T hen the set

f(S) Y R Y +y : y : f (x), x + S,

is compact.

In mathematical jargon this result is stated as follows: The continuous image

of a compact set is compact.

Exercise 9.1. Prove Theorem 9.2.

Exercise 9.2. Let A be a real n ; n symmetric matrix with entries a and let

GH

Q(x) be the quadratic form

L

Q(x) : xRAx : 1x, Ax2 : a x x .

GH G H

GH

Show that there exists a constant M 9 0 such that, for all x, Q(x) - M#x#.

Show that if Q(x) 9 0 for all x " 0, then there exists a constant m 9 0 such

that, for all x, Q(x) . m#x#. Hint: First show that the conclusion is true for

x + S(0, 1) Y +x : #x# : 1,.