<<

. 5
( 59 .)



>>

by

(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
G H
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,.

<<

. 5
( 59 .)



>>