Monday, February 1, 2010

Newton's Method

The quadratic approximation method for finding a minimum of a function of one variable generated a sequence of second degree Lagrange polynomials, and used them to approximate where the minimum is located. It was implicitly assumed that near the minimum, the shape of the quadratics approximated the shape of the objective function [Graphics:Images/NewtonSearchMod_gr_1.gif]. The resulting sequence of minimums of the quadratics produced a sequence converging to the minimum of the objective function [Graphics:Images/NewtonSearchMod_gr_2.gif]. Newton's search method extends this process to functions of n independent variables: [Graphics:Images/NewtonSearchMod_gr_3.gif]. Starting at an initial point [Graphics:Images/NewtonSearchMod_gr_4.gif], a sequence of second-degree polynomials in n variables can be constructed recursively. If the objective function is well-behaved and the initial point is near the actual minimum, then the sequence of minimums of the quadratics will converge to the minimum of the objective function. The process will use both the first- and second-order partial derivatives of the objective function. Recall that the gradient method used only the first partial derivatives. It is to be expected that Newton's method will be more efficient than the gradient method.

Background

Now we turn to the minimization of a function [Graphics:Images/NewtonSearchMod_gr_5.gif] of n variables, where [Graphics:Images/NewtonSearchMod_gr_6.gif] and the partial derivatives of [Graphics:Images/NewtonSearchMod_gr_7.gif] are accessible. Although the Newton search method will turn out to have a familiar form. For illustration purposes we emphasize the two dimensional case when [Graphics:Images/NewtonSearchMod_gr_8.gif]. The extension to n dimensions is discussed in the hyperlink.

Assume that [Graphics:Images/NewtonSearchMod_gr_9.gif] is a function of two variables, [Graphics:Images/NewtonSearchMod_gr_10.gif], and has partial derivatives [Graphics:Images/NewtonSearchMod_gr_11.gif] and [Graphics:Images/NewtonSearchMod_gr_12.gif]. The gradient of [Graphics:Images/NewtonSearchMod_gr_13.gif], denoted by [Graphics:Images/NewtonSearchMod_gr_14.gif], is the vector function


[Graphics:Images/NewtonSearchMod_gr_15.gif].

Assume that [Graphics:Images/NewtonSearchMod_gr_16.gif] are functions of two variables, [Graphics:Images/NewtonSearchMod_gr_17.gif], their Jacobian matrix [Graphics:Images/NewtonSearchMod_gr_18.gif] is

[Graphics:Images/NewtonSearchMod_gr_19.gif].

Assume that [Graphics:Images/NewtonSearchMod_gr_20.gif] is a function of two variables, [Graphics:Images/NewtonSearchMod_gr_21.gif], and has partial derivatives up to the order two. The Hessian matrix [Graphics:Images/NewtonSearchMod_gr_22.gif] is defined as follows:

[Graphics:Images/NewtonSearchMod_gr_23.gif].

Lemma 1. For [Graphics:Images/NewtonSearchMod_gr_24.gif] the Hessian matrix [Graphics:Images/NewtonSearchMod_gr_25.gif] is the Jacobian matrix for the two functions [Graphics:Images/NewtonSearchMod_gr_26.gif], i. e.

[Graphics:Images/NewtonSearchMod_gr_27.gif].

Lemma 2. If the second order partial derivatives of [Graphics:Images/NewtonSearchMod_gr_28.gif] are continuous then the Hessian matrix [Graphics:Images/NewtonSearchMod_gr_29.gif] is symmetric.

No comments:

Post a Comment

Introductory Methods of Numerical Analysis