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