Monday, February 1, 2010

Quadratic and Cubic Methods

An approach for finding the minimum of [Graphics:Images/QuadraticSearchMod_gr_1.gif] in a given interval is to evaluate the function many times and search for a local minimum. To reduce the number of function evaluations it is important to have a good strategy for determining where [Graphics:Images/QuadraticSearchMod_gr_2.gif] is to be evaluated. Two efficient bracketing methods are the golden ratio and Fibonacci searches. To use either bracketing method for finding the minimum of [Graphics:Images/QuadraticSearchMod_gr_3.gif], a special condition must be met to ensure that there is a proper minimum in the given interval.

The function [Graphics:Images/QuadraticSearchMod_gr_4.gif] is unimodal on [Graphics:Images/QuadraticSearchMod_gr_5.gif], if there exists a unique number [Graphics:Images/QuadraticSearchMod_gr_6.gif] such that

[Graphics:Images/QuadraticSearchMod_gr_7.gif] is decreasing on [Graphics:Images/QuadraticSearchMod_gr_8.gif],
and
[Graphics:Images/QuadraticSearchMod_gr_9.gif] is increasing on [Graphics:Images/QuadraticSearchMod_gr_10.gif].

Minimization Using Derivatives

Suppose that
[Graphics:Images/QuadraticSearchMod_gr_11.gif] is unimodal over [Graphics:Images/QuadraticSearchMod_gr_12.gif] and has a unique minimum at [Graphics:Images/QuadraticSearchMod_gr_13.gif]. Also, assume that [Graphics:Images/QuadraticSearchMod_gr_14.gif] is defined at all points in [Graphics:Images/QuadraticSearchMod_gr_15.gif]. Let the starting value [Graphics:Images/QuadraticSearchMod_gr_16.gif] lie in [Graphics:Images/QuadraticSearchMod_gr_17.gif]. If [Graphics:Images/QuadraticSearchMod_gr_18.gif] , then the minimum point p lies to the right of [Graphics:Images/QuadraticSearchMod_gr_19.gif]. If [Graphics:Images/QuadraticSearchMod_gr_20.gif] , then the minimum point p lies to the left of [Graphics:Images/QuadraticSearchMod_gr_21.gif].


Our first task is to obtain three test values,

(1)
[Graphics:Images/QuadraticSearchMod_gr_22.gif],
so that
(2)
[Graphics:Images/QuadraticSearchMod_gr_23.gif].

Suppose that [Graphics:Images/QuadraticSearchMod_gr_24.gif]; then [Graphics:Images/QuadraticSearchMod_gr_25.gif] and the step size h should be chosen positive. It is an easy task to find a value of h so that the three points in (1) satisfy (2). Start with [Graphics:Images/QuadraticSearchMod_gr_26.gif] in formula (1) (provided that [Graphics:Images/QuadraticSearchMod_gr_27.gif]); if not, take [Graphics:Images/QuadraticSearchMod_gr_28.gif], and so on.

Case (i) If (2) is satisfied we are done.

Case (ii) If [Graphics:Images/QuadraticSearchMod_gr_29.gif], then [Graphics:Images/QuadraticSearchMod_gr_30.gif].
We need to check points that lie farther to the right. Double the step size and repeat the process.

Case (iii) If [Graphics:Images/QuadraticSearchMod_gr_31.gif], we have jumped over p and h is too large.
We need to check values closer to
[Graphics:Images/QuadraticSearchMod_gr_32.gif]. Reduce the step size by a factor of [Graphics:Images/QuadraticSearchMod_gr_33.gif] and repeat the process.

When
[Graphics:Images/QuadraticSearchMod_gr_34.gif], the step size h should be chosen negative and then cases similar to (i), (ii), and (iii) can be used.

Quadratic Approximation to Find p

Finally, we have three points (1) that satisfy (2). We will use quadratic interpolation to find
[Graphics:Images/QuadraticSearchMod_gr_35.gif], which is an approximation to p. The Lagrange polynomial based on the nodes in (1) is

(3)[Graphics:Images/QuadraticSearchMod_gr_36.gif],


where [Graphics:Images/QuadraticSearchMod_gr_37.gif].

The derivative of [Graphics:Images/QuadraticSearchMod_gr_38.gif] is

(4)
[Graphics:Images/QuadraticSearchMod_gr_39.gif].

Solving [Graphics:Images/QuadraticSearchMod_gr_40.gif] in the form [Graphics:Images/QuadraticSearchMod_gr_41.gif] yields

(5)[Graphics:Images/QuadraticSearchMod_gr_42.gif].


Multiply each term in (5) by [Graphics:Images/QuadraticSearchMod_gr_43.gif] and collect terms involving [Graphics:Images/QuadraticSearchMod_gr_44.gif]:

[Graphics:Images/QuadraticSearchMod_gr_45.gif]

[Graphics:Images/QuadraticSearchMod_gr_46.gif]

[Graphics:Images/QuadraticSearchMod_gr_47.gif]

[Graphics:Images/QuadraticSearchMod_gr_48.gif]

This last quantity is easily solved for [Graphics:Images/QuadraticSearchMod_gr_49.gif]:

[Graphics:Images/QuadraticSearchMod_gr_50.gif].

The value [Graphics:Images/QuadraticSearchMod_gr_51.gif] is a better approximation to p than [Graphics:Images/QuadraticSearchMod_gr_52.gif]. Hence we can replace [Graphics:Images/QuadraticSearchMod_gr_53.gif] with [Graphics:Images/QuadraticSearchMod_gr_54.gif] and repeat the two processes outlined above to determine a new h and a new [Graphics:Images/QuadraticSearchMod_gr_55.gif]. Continue the iteration until the desired accuracy is achieved. In this algorithm the derivative of the objective function [Graphics:Images/QuadraticSearchMod_gr_56.gif] was used implicitly in (4) to locate the minimum of the interpolatory quadratic. The reader should note that the subroutine makes no explicit use of the derivative.

Cubic Approximation to Find p

We now consider an approach that utilizes functional evaluations of both [Graphics:Images/QuadraticSearchMod_gr_57.gif] and [Graphics:Images/QuadraticSearchMod_gr_58.gif]. An alternative approach that uses both functional and derivative evaluations explicitly is to find the minimum of a third-degree polynomial that interpolates the objective function [Graphics:Images/QuadraticSearchMod_gr_59.gif] at two points. Assume that [Graphics:Images/QuadraticSearchMod_gr_60.gif] is unimodal and differentiable on [Graphics:Images/QuadraticSearchMod_gr_61.gif], and has a unique minimum at [Graphics:Images/QuadraticSearchMod_gr_62.gif]. Let [Graphics:Images/QuadraticSearchMod_gr_63.gif]. Any good step size h can be used to start the iteration. The Mean Value Theorem could be used to obtain [Graphics:Images/QuadraticSearchMod_gr_64.gif] and if [Graphics:Images/QuadraticSearchMod_gr_65.gif] was just to the right of the minimum, then the slope [Graphics:Images/QuadraticSearchMod_gr_66.gif] might be twice [Graphics:Images/QuadraticSearchMod_gr_67.gif] which would mean that [Graphics:Images/QuadraticSearchMod_gr_68.gif] we do not know how much further to the right [Graphics:Images/QuadraticSearchMod_gr_69.gif] lies, so we can imagine that [Graphics:Images/QuadraticSearchMod_gr_70.gif] is close to [Graphics:Images/QuadraticSearchMod_gr_71.gif] and estimate h with the formula:

[Graphics:Images/QuadraticSearchMod_gr_72.gif].

Thus [Graphics:Images/QuadraticSearchMod_gr_73.gif]. The cubic approximating polynomial [Graphics:Images/QuadraticSearchMod_gr_74.gif] is expanded in a Taylor series about [Graphics:Images/QuadraticSearchMod_gr_75.gif] (which is the abscissa of the minimum). At the minimum we have [Graphics:Images/QuadraticSearchMod_gr_76.gif], and we write [Graphics:Images/QuadraticSearchMod_gr_77.gif] in the form:

(6)
[Graphics:Images/QuadraticSearchMod_gr_78.gif],
and
(7)[Graphics:Images/QuadraticSearchMod_gr_79.gif].

The introduction of [Graphics:Images/QuadraticSearchMod_gr_80.gif] in the denominators of (6) and (7) will make further calculations less tiresome. It is required that [Graphics:Images/QuadraticSearchMod_gr_81.gif], [Graphics:Images/QuadraticSearchMod_gr_82.gif], [Graphics:Images/QuadraticSearchMod_gr_83.gif], and [Graphics:Images/QuadraticSearchMod_gr_84.gif]. To find [Graphics:Images/QuadraticSearchMod_gr_85.gif] we define:

(8)
[Graphics:Images/QuadraticSearchMod_gr_86.gif],

and we must go through several intermediate calculations before we end up with [Graphics:Images/QuadraticSearchMod_gr_87.gif].

Use use (6) to obtain

[Graphics:Images/QuadraticSearchMod_gr_88.gif]

Then use (8) to get

[Graphics:Images/QuadraticSearchMod_gr_89.gif]

Then substitute [Graphics:Images/QuadraticSearchMod_gr_90.gif] and we have

(9)
[Graphics:Images/QuadraticSearchMod_gr_91.gif]

Use use (7) to obtain

[Graphics:Images/QuadraticSearchMod_gr_92.gif]

[Graphics:Images/QuadraticSearchMod_gr_93.gif]

Then use (8) to get

[Graphics:Images/QuadraticSearchMod_gr_94.gif]

Then substitute [Graphics:Images/QuadraticSearchMod_gr_95.gif] and we have

(10) [Graphics:Images/QuadraticSearchMod_gr_96.gif]

Finally, use (7) and write

[Graphics:Images/QuadraticSearchMod_gr_97.gif]

Then use (8) to get

(11) [Graphics:Images/QuadraticSearchMod_gr_98.gif]

Now we will use the three nonlinear equations (9), 10), (11) listed below in (12). The order of determining the variables will be [Graphics:Images/QuadraticSearchMod_gr_99.gif] (the variable [Graphics:Images/QuadraticSearchMod_gr_100.gif] will be eliminated).

[Graphics:Images/QuadraticSearchMod_gr_101.gif]
(12) [Graphics:Images/QuadraticSearchMod_gr_102.gif]
[Graphics:Images/QuadraticSearchMod_gr_103.gif]

First, we will find [Graphics:Images/QuadraticSearchMod_gr_104.gif] which is accomplished by combining the equation in (12) as follows:

[Graphics:Images/QuadraticSearchMod_gr_105.gif]

Straightforward simplification yields [Graphics:Images/QuadraticSearchMod_gr_106.gif], therefore [Graphics:Images/QuadraticSearchMod_gr_107.gif] is given by

(13) [Graphics:Images/QuadraticSearchMod_gr_108.gif].

Second, we will eliminate [Graphics:Images/QuadraticSearchMod_gr_109.gif] by combining the equation in (12) as follows, multiply the first equation by [Graphics:Images/QuadraticSearchMod_gr_110.gif] and add it to the third equation

[Graphics:Images/QuadraticSearchMod_gr_111.gif]
[Graphics:Images/QuadraticSearchMod_gr_112.gif]

[Graphics:Images/QuadraticSearchMod_gr_113.gif]

which can be rearranged in the form

[Graphics:Images/QuadraticSearchMod_gr_114.gif]

Now the quadratic equation can be used to solve for [Graphics:Images/QuadraticSearchMod_gr_115.gif]

[Graphics:Images/QuadraticSearchMod_gr_116.gif]

It will take a bit of effort to simplify this equation into its computationally preferred form.

[Graphics:Images/QuadraticSearchMod_gr_117.gif]

[Graphics:Images/QuadraticSearchMod_gr_118.gif]

[Graphics:Images/QuadraticSearchMod_gr_119.gif]
Hence,

(14) [Graphics:Images/QuadraticSearchMod_gr_120.gif]

Therefore, the value of [Graphics:Images/QuadraticSearchMod_gr_121.gif] is found by substituting the calculated value of [Graphics:Images/QuadraticSearchMod_gr_122.gif] in (14) into the formula [Graphics:Images/QuadraticSearchMod_gr_123.gif]. To continue the iteration process, let [Graphics:Images/QuadraticSearchMod_gr_124.gif] and replace [Graphics:Images/QuadraticSearchMod_gr_125.gif] and [Graphics:Images/QuadraticSearchMod_gr_126.gif] with [Graphics:Images/QuadraticSearchMod_gr_127.gif] and [Graphics:Images/QuadraticSearchMod_gr_128.gif], respectively, in formulas (12), (13), and (14). The algorithm outlined above is not a bracketing method. Thus determining stopping criteria becomes more problematic. One technique would be to require that [Graphics:Images/QuadraticSearchMod_gr_129.gif], since [Graphics:Images/QuadraticSearchMod_gr_130.gif].

No comments:

Post a Comment

Introductory Methods of Numerical Analysis