Principles of Mathematics in Operations Research

Solutions 281

f(x*+h)^f(x*)+

1

-h

T

V

2

f(x*)h.

Suppose that V^2 /(x*) is not positive semi-definite. Then,

3«eln 9 vTV^2 f(x*)v < 0;

even for the remainder term, vTV^2 f(£)v < 0 if \\x* — £|| is small enough. If

we take h as being along v, we should have f(x*) > f(x* + h), Contradiction

to the local minimality of f(x*). Thus, V^2 /(x*) is positive semi-definite.

If we combine the first order necessary condition and the second order

necessary condition after deleting the term -semi-, we will arrive at the suffi-

ciency condition for x* being the strict local minimizer.

c) At every iteration, we will approximate f(x) by a quadratic function Q(p)

using the first three terms of its Taylor series about the point xk-\:

V/(xfc_i) + V^2 /(a*-i)rP * V/(xfc_! + p).

f(xk-i + p) « /(xfe-i) + V/(xfc_ 1 )rp + -pTV^2 f(xk^)p = Q(p);

and we will minimize Q as a function of p, then we will finally set xk =

Xk-l +Pk-

Let us take the derivative of Q:

dQ

dp

Since we expect 6 = V/(xfc_i + pk) « V/(xfc_i) + V^2 /(xfc_i)rpfc,

V^2 /(fc-i)rPfc = -V/(xfc_x) &pk = -[V^2 /(xft_ 1 )]-^1 V/(xfc_ 1 ).

This method of finding a root of a function is known as Newton's method,
which has a quadratic rate of convergence except in some degenerate cases.
Newton's method for finding V/(x) = 8 is simply to iterate as xk = xk-i —

[vvock-or'v/fo-i).

d) See Figure S.24 for the plot of the bivariate function, /(xi,x 2 ) = x\ +
2x\ + 24x^2 + x\ + 12x2, m tne question.

4xf + ®xi + 48xi

4x1 + 24x 2

v/(

v

2

/(

Let X(o) =^1

1

Xi

X 2

Xi

X2

)"

=^v/^1

1

)"[

12xf

)"

12xf + 12xi + 48 0

0 12x2 + 24^1 1™

58

28 , V

(^2) / 72 0
0 36

. Then,