<<

. 29
( 59 .)



>>

 
We now take X to be an open set in RL. The next two theorems are the
n-dimensional generalizations of Theorems 2.1 and 2.2.

T 2.3. L et X be an open set in RL, let f be a real-valued function de¬ned
on X, and let x be a local minimizer. If f has ¬rst-order partial derivatives at

x , then

*f
(x ) : 0, i : 1, . . . , n. (5)
*x 
G
If f is of class C  on some open ball B(x , ) centered at x , then
 
* f
H(x ) : (x )
 *x *x 
HG
is positive semide¬nite.
Proof. Since X is open, there exists a 9 0 such that for each i : 1, . . . , n
the points

x ; te : (x , . . . , x , x ; t, x ,...,x )
 G    G\  G  G>  L
are in X whenever "t" : . Therefore for each i : 1, . . . , n the function
G
de¬ned by

(t) : f (x ; te ), "t" : ,
G  G
132 OPTIMIZATION PROBLEMS


is well de¬ned and has a local minimum at t : 0. Since the partial derivatives
of f exist at x , the chain rule implies that for each i : 1, . . . , n the derivative

(0) exists and is given by
G

*f
(0) : (x ).
G *x 
G

has a local minimum at t : 0, (0) : 0. Thus (5) holds.
Since each
G
G
Now suppose that f is of class C  on some open ball B(x , ). Then for

each unit vector u in RL the function ( ; u) de¬ned by

(t; u) : f (x ; tu), "t" : ,


is well de¬ned, is of class C  , and has a local minimum at t : 0. By Theorem
2.1, (0, u) : 0 and (0; u) . 0. By a straightforward calculation as in relation
(13) in Section 11 of Chapter I, we get

(t; u) : 1u, H(x ; tu)u2.


Setting t : 0, we get that 1u, H(x )u2 . 0. Since u is an arbitrary unit vector,

we get that H(x ) is positive semide¬nite.

In RL points c such that
f (c) : 0 are called critical points of f.

T 2.4. L et X be an open set in RL and let f be a real-valued function of
class C  on some ball B(x , ). If H(x ) is positive de¬nite and
f (x ) : 0, then
  
x is a strict local minimizer. If X is convex, f is of class C  on X, and H(x)

is positive semide¬nite for all x in X, then x is a minimizer for f. If H(x) is

positive de¬nite for all x in X, then x is a strict minimizer.

Proof. We shall only prove the local statement and leave the proof of the
last two to the reader.
If H(x ) is positive de¬nite at x , then it follows from the continuity of the
 
second partial derivatives of f and Lemma III.3.2 that there exists a 9 0 such
that H(x) is positive de¬nite for all x in B(x , ). Let x be any point in B(x , )
 
and let v : x 9 x . Then the function ( ; v) de¬ned by


(t; v) : f (x ; tv)


is well de¬ned and is C  on some real interval (91 9 , 1 ; ), where 9 0.
Moreover

(0; v) : f (x ), (1; v) : f (x). (6)

DIFFERENTIABLE UNCONSTRAINED PROBLEMS 133


By Taylor™s theorem, there exists a t in the interval (0, 1) such that

(1; v) : (0; v) ; (0; v) ;  (t ; v). (7)

Again, straightforward calculations as in relations (12) and (13) in Section 11
of Chapter I give

(t; v) : 1
f (x ; tv), v2,

(t; v) : 1v, H(x ; tv)v2, 91 9 : t : 1 ; .

If we set t : 0 in the ¬rst of these relations, we get that (0; v) : 1
f (x ), v2.

If we then set t : t in the second of these relations, use the hypothesis

f (x ) : 0, and substitute into equation (7), we get

(1; v) 9 (0; v) :  1v, H(x ; t v)v2.
 
From this relation, from (6), and from the fact that H(x) is positive de¬nite for
all x in B(x , ), we get that

f (x) 9 f (x ) :  1v, H(x ; t v)v2 9 0

 
for all x in B(x , ) Hence x is a strict local minimizer.
 
Remark 2.1. Theorems 2.1 and 2.3 suggest the well-known strategy of solving
unconstrained optimization problems by ¬rst ¬nding the critical points. Some
of these critical points can then be eliminated by considering the second
derivative or Hessian at these points. By then considering strengthened
conditions on the second derivative or the Hessian as in Theorems 2.2 and 2.4,
one can show in some cases that a critical point is indeed a local minimizer or
minimizer.

Exercise 2.1. Let X be a closed interval [a, b] in R and let f be a real-valued
function de¬ned on X. Show that if x : a is a local minimizer for f and if the
right-hand derivative f  (a) exists, then f  (a) . 0. Show that if x : b is a local
> >
minimizer and the left-hand derivative f  (b) exists, then f  (b) - 0.
\ \
Exercise 2.2. Find local minimizers, local maximizers, minimizers, and maxi-
mizers, if they exist, for the following functions. Exercise I.9.3 may be useful in
some cases:

x ) : x 9 4x ; 2x ; 7,
(a) f (x ,
 
  
x , x ) : 3x ; 2x ; 2x ; 2x x ; 2x x ; 2x x ,
(b) f (x ,
  
    
(c) f (x , x ) : x x ; 1/x ; 1/x , (x , x ) " (0, 0), and
     
(d) f (x , x ) : (x ; x )(x x ; 1).
    
134 OPTIMIZATION PROBLEMS


Exercise 2.3. Let

f (x , x ) : x ; x, g(x , x ) : x ; x.
   
 

Show that
f (0) :
g(0) : 0 and that both f and g have positive semide¬nite
Hessians at 0, but 0 is a local minimizer for g but for for f. This shows that
the condition of positive de¬niteness of H(x ) in Theorem 2.4 cannot be

replaced by positive semide¬niteness.

Exercise 2.4. Complete the proof of Theorem 2.4 by proving the last two
statements.

Exercise 2.5. Let

f (x, y) : x ; y 9 32y.

Minimize f on R. (Hint: See Exercise I.9.3.)

Exercise 2.6. (a) Show that for no value of a does the function

f (x, y) : x 9 3axy ; y

have a minimizer.
(b) For each value of a ¬nd local minimizers and local maximizers, if any
exist, of this function.

Exercise 2.7. Let f be de¬ned on R by

f (x, y) : x ; eW 9 3xeW.

Show that there is a unique point (x , y ) at which
f (x, y ) : 0 and that this
 
point is a local minimizer but not a minimizer.

Exercise 2.8 (Linear Regression). In the linear regression problem n points
(x , y ), (x , y ), . . . , (x , y ) are given in the xy-plane and it is required to ˜˜¬t™™
  LL
a straight line y : ax ; b to these points in such a way that the sum of the
squares of the vertical distances of the given points from the line is minimized.
That is, a and b are to be chosen so that

L
f (a, b) :  (ax ; b 9 y )
G G
G
DIFFERENTIABLE UNCONSTRAINED PROBLEMS 135


is minimized. The resulting line is called the linear regression line for the given
points.
Show that the coef¬cients a and b of the linear regression line are given by

nxy 9 L x y

G G G ,
b : y 9 ax,
  a:
n(x ) 9 L x

G G
where

1L 1L
x:
  x, y:
  y.
G G
n n
G G
Exercise 2.9 (Best Mean-Square Approximation by Orthogonal Functions). Let
, . . . , be continuous and not identically zero on an interval [a, b] and such
 L
that



@
(x) (x) dx : 0 if j " k.
H I
?
Given a piecewise continuous function f on [a, b] show that the values of
c , . . . , c that minimize
 L



@ L 
F(c) : f9  c dx
GG
? G
are given by the formulas

1 , f2
G
c: i : 1, . . . , n,
,
G 1, 2
GG
where


<<

. 29
( 59 .)



>>