Quadratic and Cubic Methods

An approach for finding the minimum of 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 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 , a special condition must be met to ensure that there is a proper minimum in the given interval.

The function is unimodal on , if there exists a unique number such that

is decreasing on ,
and
is increasing on .

Minimization Using Derivatives

Suppose that is unimodal over and has a unique minimum at . Also, assume that is defined at all points in . Let the starting value lie in . If , then the minimum point p lies to the right of . If , then the minimum point p lies to the left of .

Our first task is to obtain three test values,

(1) ,
so that
(2) .

Suppose that ; then 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 in formula (1) (provided that ); if not, take , and so on.

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

Case (ii) If , then .
We need to check points that lie farther to the right. Double the step size and repeat the process.

Case (iii) If , we have jumped over p and h is too large.
We need to check values closer to . Reduce the step size by a factor of and repeat the process.

When , 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 , which is an approximation to p. The Lagrange polynomial based on the nodes in (1) is

(3),

where .

The derivative of is

(4).

Solving in the form yields

(5).

Multiply each term in (5) by and collect terms involving :

This last quantity is easily solved for :

.

The value is a better approximation to p than . Hence we can replace with and repeat the two processes outlined above to determine a new h and a new . Continue the iteration until the desired accuracy is achieved. In this algorithm the derivative of the objective function 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 and . 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 at two points. Assume that is unimodal and differentiable on , and has a unique minimum at . Let . Any good step size h can be used to start the iteration. The Mean Value Theorem could be used to obtain and if was just to the right of the minimum, then the slope might be twice which would mean that we do not know how much further to the right lies, so we can imagine that is close to and estimate h with the formula:

.

Thus . The cubic approximating polynomial is expanded in a Taylor series about (which is the abscissa of the minimum). At the minimum we have , and we write in the form:

(6),
and
(7).

The introduction of in the denominators of (6) and (7) will make further calculations less tiresome. It is required that , , , and . To find we define:

(8) ,

and we must go through several intermediate calculations before we end up with .

Use use (6) to obtain



Then use (8) to get



Then substitute and we have

(9)

Use use (7) to obtain





Then use (8) to get

Then substitute and we have

(10)

Finally, use (7) and write



Then use (8) to get

(11)

Now we will use the three nonlinear equations (9), 10), (11) listed below in (12). The order of determining the variables will be (the variable will be eliminated).

(12)

First, we will find which is accomplished by combining the equation in (12) as follows:



Straightforward simplification yields , therefore is given by

(13) .

Second, we will eliminate by combining the equation in (12) as follows, multiply the first equation by and add it to the third equation






which can be rearranged in the form



Now the quadratic equation can be used to solve for

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

Hence,

(14)

Therefore, the value of is found by substituting the calculated value of in (14) into the formula . To continue the iteration process, let and replace and with and , 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 , since .