Chapter 7

Univariate Minimization
Recall from Calculus that when you are set the problem of determining a minimum of a continuously
differentiable function f on a closed interval [a, b] first you determine the derivative function f ! . Then
you find all the critical values x in [a, b] where f ! (x) = 0, say x1 , x2 , . . . , xp . Finally, you determine
the global minimum minx[a,b] f (x) = min{f (a), f (x1 ), f (x2 ), . . . , f (xp ), f (b)}. There is no need
to check whether the critical values x1 , x2 , . . . , xp correspond to local minima as we determine the
global minimum by enumeration. This approach suggests that we may find the extrema of f (x) by
computing the zeros of f ! (x) and well return to this approach at the end of this chapter.
Example 7.0.11. To find the minimum of the continuously differentiable function f (x) = ex sin(x)
on the closed interval [0, 1.5], first we compute the derivative f ! (x) = ex ( sin(x) + cos(x)).
Next, we find the critical values x where f ! (x) = 0. Since ex is never zero, we must have
sin(x) + cos(x) = 0; that is, we need the values x such that tan(x) = 1 since cos(x) "= 0 on
[0, 1.5]. On [0, 1.5] this equation is satisfied at just one point x = 4 . Now,
!
!"
"
min f (0), f
, f (1.5) = min(0, 0.322396941945, 0.222571216108) = 0.322396941945
4
is the global minimum located at x =

4.

In computational practice it is usually infeasible to find a global minimum, unless we know

in advance how many local extrema f (x) has. So here we concentrate on finding just one local
extremum, a local minimum. Also we start with methods which use only values f (x) in finding the
local minimum then move to methods which also use values f ! (x).
We consider how to determine the location xm of a minimum of the function f on the interval
[a, b]. We say that [a, b] is a bracket for the minimum of f if xm is in [a, b]. Throughout,
we assume that the function f is Ushaped on the interval [a, b] ; i.e., it is continuous, strictly
decreasing on [a, xm ), and strictly increasing on (xm , b]. When the function f has a continuous
derivative, then for f to be Ushaped it is sufficient that the derivative f ! be negative on [a, xm )
and positive on (xm , b]. When the function f has a continuous second derivative, then for f to be
Ushaped it is sufficient that f be concave up on the interval [a, b] and f ! (xm ) = 0.
Let the interval [a, b] be a bracket for the minimum of a Ushaped function f . The basic process
used to refine such a bracket, i.e., to make it shorter, uses search points c and d where a < c < d < b.
Given such search points, it follows that (see Fig. 7.1)
1. if f (c) f (d), then [a, d] is a bracket for the minimum, and
2. if f (c) f (d), then [c, b] is a bracket for the minimum.
To prove that 1 is true, suppose that both f (c) f (d) and xm > d. Now xm > d implies that both
of the points c and d lie to the left of the point xm where the function f is strictly decreasing, so
f (c) > f (d). But this contradicts the supposition that f (c) f (d), so both of f (c) f (d) and
xm > d cannot be true. Therefore, if f (c) f (d) is true, then xm > d must be false, i.e., the point
199

200

CHAPTER 7. UNIVARIATE MINIMIZATION

f(c) f(d)

f(c) f(d)

xaxis

xaxis

Figure 7.1: Illustration of bracket refining to find a minimum of a function. The plot on the left
illustrates that if f (c) f (d), then [a, d] is a bracket for the minimum. The plot on the right
illustrates that if f (c) f (d), then [c, b] is a bracket for the minimum.
xm lies in the interval [a, d]. So, the statement in Part 1 is true. The proof of 2 is similar; see
Problem 7.0.2.
Unlike when refining a bracket for a root, refining a bracket for the minimum generally requires
the function to be evaluated at two distinct points inside the bracket. To understand why, let
[a, b] be a bracket for the minimum of the Ushaped function f , and let c be some point in the
open interval (a, b). There is no decision rule that compares the values f (a), f (b) and f (c) and
determines correctly which of the intervals, either [a, c] or [c, b], is a bracket for the minimum. Pick
three values va , vb and vc for which vc < min(va , vb ) and plot the points (a, va ), (b, vb ) and (c, vc ).
Consider Fig. 7.2, which shows the graphs of the values of two Ushaped functions f1 (x) and f2 (x)
that pass through these three points with the minimum of f1 (x) located to the right of the point
c and the minimum of f2 (x) located to the left of c. Observe that va , vb and vc are the common
values assumed by these two functions at the points a, b and c, respectively. If the decision rule
compares the values va , vb and vc and declares the interval [c, b] to be the refined bracket, then this
would be correct for the Ushaped function f1 but incorrect for the Ushaped function f2 . On the
other hand, if the decision rule compares the values va , vb and vc and declares the interval [a, c] to
be the refined bracket, then it would be correct for the Ushaped function f2 but incorrect for the
Ushaped function f1 . The conclusion is that, generally, a decision rule that refines a bracket for
the minimum of a Ushaped function f must evaluate the function at more than one distinct points
in the open interval (a, b).
Problem 7.0.1. Show that x =
of f (x).

is a local minimum of f (x) = ex sin(x). Find a local maximum

Problem 7.0.2. Prove the statement presented in Part 2. Hint: Suppose that both f (c) f (d)
and xm < c are true. Describe the contradiction obtained from this supposition. Conclude that if
f (c) f (d) is true, then xm < c must be false; i.e., the point xm lies in the interval [c, b].
Problem 7.0.3. Let f (x) be a Ushaped function defined on the interval [a, b]. For every choice of
the point c (a, b), show that f (c) < max(f (a), f (b)). Hint: Show that the function f cannot be
Ushaped on the interval [a, b] if there is a value of c (a, b) for which f (c) max(f (a), f (b)).
Problem 7.0.4. Let the function f be Ushaped on the interval [a, b], and let c be some point in
the open interval (a, b) for which f (c) min(f (a), f (b)). If f (c) f (a), then show that the interval
[a, c] is a bracket for the minimum. Similarly, if f (c) f (b), then show that the interval [c, b] is a
bracket for the minimum.
Problem 7.0.5. Pick three values va , vb and vc such that vc < min(va , vb ) and plot the points
(a, va ), (c, vc ) and (b, vb ). Sketch the graph of two piecewise linear (V-shaped) functions that pass

201

7.1. SEARCH METHODS NOT INVOLVING DERIVATIVES

(a, v )

(b, v )

(a, v )

(b, v )

y = f1 (x)

y = f2 (x)

(c, vc )

(c, vc )

xaxis

xaxis

Figure 7.2: The plots in this figure illustrate that if the function is evaluated at only one point, c,
in the interval [a, b], then it may not be possible to determine whether the minimum is to the left
or to the right of c.
through these three points and yet assume their minimum value at points on opposite sides of the
point c. Argue why these piecewise linear functions are Ushaped functions.

7.1

Search Methods not Involving Derivatives

Here, we describe methods which only use values f (x) in the search for the location of its local
minimum by reducing the length of a bracket on the location. The first method makes no use of
the absolute size of the function in determining the iterates. The second uses interpolation formulas
which implicitly incorporate the functions size.

7.1.1

Golden Section Search

The golden section search for the minimum of a Ushaped function f is analogous to the bisection
method for finding a root of f (x). Golden section is characterized by how the search points c and
d are chosen. If [a, b] is a bracket for the minimum of the function f , then its associated golden
section search points c and d are
c a + r(b a)
d b r(b a)
where

3 5
r
0.382 . . .
2
Because r < 1, c is the golden section search point nearest the endpoint a and we say that a and c
are associated. Similarly, we say that the points d and b are associated. Observe that the endpoints
of each of the possible refined brackets, [a, d] or [c, b], consist of one golden section search point and
the endpoint associated with the other golden section search point.
The name golden section search is derived from the fact that the length of the original bracket
divided by the length of either possible refined bracket is

1+ 5
1
=
1.618,
1r
2

a value known in antiquity as the golden section constant.

202

CHAPTER 7. UNIVARIATE MINIMIZATION

Bracket, [ai , bi ]
Original Bracket
Left Refinement
Right Refinement

[0, 1]
[0, 0.618]
[0.382, 1]

Left
Endpoint
ai
0
0
0.382

Left
GSSP
ci
0.382
0.236
0.618

Right
GSSP
di
0.618
0.382
0.764

Right
Endpoint
bi
1
0.618
1

Table 7.1: Endpoints and golden section search points (GSSP). The left refinement case is illustrated
in the left part of Fig. 7.3, and the right refinement is illustrated in the right part of Fig. 7.3

Left Refinement
a0

a1

c1

c0

d0

d1

b1

Right Refinement
b0

a0

c0

d0

a1

c1

b0

d1

b1

Figure 7.3: The figure illustrates the two possibilities for refining a bracket in the golden section
search method. Notice that only one new point needs to be computed for each refinement.
Choosing c and d to be the golden section search points has two advantages. First, each refinement
step of golden section search reduces the length of the bracket by a factor of 1 r 0.618. Second,
the two golden section search points for the original bracket occur in the refined bracket one as an
endpoint and the other as an associated golden section search point. This is illustrated in Table
7.1 and Fig. 7.3 for a bracket and its two possible refinements. Note how the golden section search
points of the original bracket appear in the refined bracket. One is an endpoint and the other is that
endpoints associated golden section search point. As a consequence, the value f (x) at the golden
section search point common to both the original and refined brackets can be reused in the next
refinement step!
Fig. 7.4 displays a pseudocode for golden section search; it assumes that the initial points a
and b as well the function f (x) are provided. At the top of the while-loop the only points known
are the endpoints a, b and the golden section search point c associated with a. For refinement, the
code computes the golden section search point d associated with b, via the technique in Problem
7.1.3, then the if-statement identifies the refined bracket. This refined bracket consists of the interval
between the golden section search point with the largest value of f (x) and the endpoint associated
with the other golden section search point. The body of the if-statement applies the label c to the
golden section search point that has the largest value f (x), f c to its associated function value, a to
the endpoint associated with c, and b to the other endpoint. Note that the computation of the point
d and the refinement of the bracket work equally well whether a < b or a > b. This pseudocode for
golden section search incurs a startup cost of one function evaluation, and then a cost of one function
evaluation for each refinement step. Generally, in costing the algorithm the startup cost is either
ignored or is amortized over the cost of all the function evaluations used in the later refinement
steps. So, each step of golden section search for the minimum reduces the length of the bracket for
the minimum by a factor of about 0.618 at a cost of about one function evaluation. Error detection
should be included in an algorithm for golden section search. For example, if it turns out that
f (c) max(f (a), f (b)), then it should be reported that the function f is not Ushaped.

7.1. SEARCH METHODS NOT INVOLVING DERIVATIVES

203

r = (3 5)/2
c = a + r(b a); f c = f (c)
if f c f a or f c f b then Stop - f not U-shaped
while termination criteria not satisfied do
d = c + r(b c); f d = f (d)
if f d f a or f d f b then Stop - f not U-shaped
if f c f d then
b = a; a = d
else
a = c; c = d; f c = f d
endif
end while
Figure 7.4: Pseudocode Golden Section Search

What termination criteria should be used? Suppose the point x lies in a bracket [a, b] for the
minimum of f (x), so |x xm | |b a|. Common practice is to stop the search when this bracket
is sufficiently short that
#
"
|b a|
L

where " is the working precision machine epsilon and L is a positive constant. This termination
criterion can be justified as follows. Rearrange this inequality so that it reads
L(b a)2 "
The left hand side of this inequality provides an upper bound on the absolute relative error in
accepting f (x) as the value of f (xm ) while the right hand side provides an upper bound on the
absolute relative error in the computed value F (x) of f (x). So, this termination criterion states that
the search be stopped when the difference between the values f (x) and f (xm ) could be attributed
to rounding error in the computed value of the value f (xm ).
There are two reasons why the value F (x) differs from the value f (xm ). The first reason is that
f (x) is computed using floating point arithmetic. So, the best we can expect is that F (x) is the
rounded value of f (x) from which it follows that
$
$
$ F (x) f (x) $
$
$"
$
$
f (x)

The second reason is that the point x differs from xm . If f has two continuous derivatives, then
since f ! (xm ) = 0, Taylors series states that as x xm ,
f (x) f (xm ) +

f !! (xm )
(x xm )2 = f (xm ) (1 + )
2

where
=

f !! (xm )
(x xm )2
2f (xm )

So, the relative error in accepting the value f (x) as an approximation of f (xm ) satisfies the bound
$
$
$ f (x) f (xm ) $
$ ! ||
$
$
$
f (xm )
Recall that |x xm | |b a|, so

$ !!
$
$ f (xm ) $
$
$ (b a)2 = L(b a)2
|| $
2f (xm ) $

204

CHAPTER 7. UNIVARIATE MINIMIZATION

where we have identified

$ !!
$
$ f (xm ) $
$
$
L=$
2f (xm ) $

In terms of the values and ", the proposed termination criterion becomes || ". In words, the
error in accepting the value f (x) as the value of f (xm ) is no larger than an amount that could be
attributed to the rounding error in the computed value of f (xm ).
This termination criterion also has an important consequence. If we switch from single to double
precision arithmetic, we should expect to determine xm only to about 4 additional decimal digits of

accuracy. This follows because "SP 104 and "DP 108 , so the switch in precision causes the
square root of the working precision machine epsilon to be reduced by only a factor of 104 .
Example 7.1.1. We find a local minimum of f (x) = ex sin(x) on the interval [0, 1.5] using
golden section search. We terminate when the bracket is smaller than 105 . We implemented the
pseudocode in Figure 7.4 and terminated when the bracket was smaller than 105 ; results are in
Table 7.2. Observe the irregular behavior of the error, somewhat reminiscent of the behavior of the
error for the bisection method in root finding.
iterate
0.000000
1.500000
0.572949
0.927051
1.145898
0.791796
0.708204
0.843459
0.759867
0.811529
0.779600
0.772063
0.784259
0.787138
0.782479
0.785358
0.786038
0.784938
0.785618
0.785198
0.785457
0.785297
0.785396

f (iterate)
0.000000
-0.222571
-0.305676
-0.316517
-0.289667
-0.322384
-0.320375
-0.321352
-0.322183
-0.322181
-0.322386
-0.322339
-0.322397
-0.322396
-0.322394
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397

error
-0.785398
0.714602
-0.212449
0.141653
0.360500
0.006398
-0.077194
0.058061
-0.025531
0.026131
-0.005798
-0.013336
-0.001140
0.001739
-0.002919
-0.000040
0.000640
-0.000460
0.000220
-0.000200
0.000059
-0.000101
-0.000002

Table 7.2: Golden section iterates, function values and errors in iterates

Problem 7.1.1. Show that the length of each of the two possible refined brackets, [a, d] and [c, b], is
(1 r)(b a). What is the numerical value of 1 r?
Problem 7.1.2. Consider the formulas for the golden section search points c and d. Show that if
we swap the values a and b, then the values c and d are swapped too, i.e., the formula for c after
the swap is the same as the formula for d before the swap, and vice versa. Remark: The conclusion
is that, regardless of whether a < b or b < a, the formula for c determines the golden section search
point associated with a, and the formula for d determines the golden section search point associated
with b.

7.1. SEARCH METHODS NOT INVOLVING DERIVATIVES

205

Problem 7.1.3. Let the points a and b be given, and let c and d be their associated golden section
search points. Show that
d = c + r(b c)

Computing the point d this way has the advantage that d surely lies between c and b.

Problem 7.1.4. Show that r is a root of the quadratic equation r2 3r + 1 = 0. Algebraically

rearrange this equation to show that (a) (1 r)2 = r, (b) r(2 r) = 1 r, and (c) 1 2r = r(1 r).
Problem 7.1.5. Given the initial bracket for the minimum is [0, 1], show explicitly the computation
of the remaining numbers in Table 7.1.
Problem 7.1.6. Construct a table similar to Table 7.1 for a general initial bracket [a, b].
Problem 7.1.7. Modify the pseudocode for golden section search so it reports that f (x) is not
Ushaped if f (c) max(f (a), f (b)).

7.1.2

Quadratic Interpolation Search

For brevity, we use the phrase quadratic search to describe the search for the minimum of a U
shaped function f using quadratic interpolation. This is analogous to the method of false position
for finding a root because both methods maintain a bracket and both approximate the function f
by an interpolating polynomial.
What distinguishes quadratic search for the minimum from golden section search is how the
search points c and d are chosen. We assume that an initial bracket [a, b] for the minimum of the
function f (x) is given. We start by choosing a point c in the open interval (a, b). Each quadratic
search iteration starts by checking the inequality f (c) < min(f (a), f (b)); if it is not satisfied an
error is reported. Next, d is determined as the point in the open interval (a, b) where the quadratic
polynomial that interpolates the data (c, f (c)), (a, f (a)) and (b, f (b)) assumes its minimum value;
if d = c an error is reported. Then, the points (c, f (c)) and (d, f (d)) are swapped, if necessary,
so that c < d. Finally, the bracket is refined as usual; if the search points are c and d, one
becomes an endpoint of the refined bracket and the other is (re-)labelled c. We report an error if
f (c) min(f (a), f (b))
Lets demonstrate that the point d lies between the midpoints of the intervals [a, c] and [c, b], and
so lies in the open interval (a, b). To start, let P2 (x) be the quadratic polynomial that interpolates
the data (c, f (c)), (a, f (a)) and (b, f (b)). With the data so ordered, the Newton form of P2 is
P2 (x) = g0 + (x c)g1 + (x c)(x a)g2
where the coefficients g0 , g1 and g2 are chosen so that P2 (c) = f (c), P2 (a) = f (a) and P2 (b) = f (b).
The solution of these equations is
g0
g1

g2

= f (c)
f (c) f (a)
=
ca
%
&
f (b) f (c)
g1
bc
=
ba

Because f (c) < min(f (a), f (b)), it is easy to show that g1 < 0 and g2 > 0. Consequently, the
quadratic polynomial P2 is concave up and achieves its least value at the point
d

a+c
g1

2
2g2

a+c
. Similarly, if the Newton form
2
of the same interpolating polynomial P2 (x) is constructed but with the data ordered as (c, f (c)),
where P ! (d) = 0. Because g1 < 0 and g2 > 0, it follows that d >

206

CHAPTER 7. UNIVARIATE MINIMIZATION

f a = f (a); f b = f (b)
c = 0.5(a + b); f c = f (c)
if f c f a or f c f b then Stop - f not U-shaped
while termination criteria not satisfied do
g1 = (f c f a)/(c a)
g2 = [(f b f c)/(b c) g1](b a)
d = 0.5[(a + c) g1/g2]; f d = f (d)
if f d f a or f d f b then Stop - f not U-shaped
if c > d then
!Swap c and d, and f c and f d
temp = c; c = d; d = temp
temp = f c; f c = f d; f d = temp
endif
if f c f d then
b = d; f b = f d
else
a = c; f a = f c
c = d; f c = f d
endif
end while
Figure 7.5: Pseudocode Quadratic Search

(b, f (b)) and (a, f (a)), then it is easy to show that d <

c+b
. Therefore, the point d lies between
2

the midpoints of the intervals [a, c] and [c, b].

Generally, quadratic search for the minimum works well. However, for some functions it converges
very slowly. In these cases, a pattern develops where successive iterations reset the same endpoint,
either a or b, to a nearby point thereby causing the length of the bracket to be only minimally refined.
This pattern may be broken by keeping track of the assignments and, when necessary, inserting a
special step. For example, a special step might replace the point d with the midpoint of one of the
two intervals [a, c] and [c, b].
Example 7.1.2. We find a local minimum of f (x) = ex sin(x) on the interval [a, b] = [0, 1.5]
using quadratic interpolation search, starting arbitrarily with c = 0.5(a + b) = 0.75. We terminate
the iteration when the bracket is smaller than 105 . We implemented the pseudocode in Figure 7.5
and terminated when the bracket was smaller than 105 ; results are in Table 7.3. Observe that the
error, that is the distance between the point c and the answer becomes small quickly but that the
bracket takes longer to reduce in length to the required size, hence the last few iterates in the table.
Problem 7.1.8. Develop a pseudocode that implements quadratic search for the minimum of f .
Assume the user has provided an initial bracket [a, b] and the name of the subprogram that computes
values f (x). In your startup code, include a sensible choice of the initial value of c. Report all errors
immediately; that is, do not try any remedies.
Problem 7.1.9. Let f be a Ushaped function on the interval [a, b] and let c be a point in (a, b)
for which f (c) < min(f (a), f (b)). Let the quadratic polynomial P2 (x) interpolate f (x) at the points
x = a, x = c and x = b, so that P2 (c) < min(P2 (a), P2 (b)). Without calculating the quadratic P2 (x),
argue why P2 (x) is concave up and why the location d of its minimum lies in (a, b).
Problem 7.1.10. Suppose that f is a Ushaped function on the interval [a, b] and c is a point
in (a, b) for which f (c) < min(f (a), f (b)). Let P2 be the quadratic polynomial that interpolates
to the data (a, f (a)), (c, f (c)) and (b, f (b)). Use the Mean Value Theorem (see Problem 6.0.3) to
demonstrate that there is a point u (a, c) for which P2! (u) < 0, and a point v (c, b) for which

207

7.2. SEARCHES USING THE DERIVATIVE

iterate
0.000000
1.500000
0.750000
0.948066
0.811887
0.786261
0.785712
0.785412
0.785402
0.785398
0.785398
0.785398
0.785398

f (iterate)
0.000000
-0.222571
-0.321983
-0.314754
-0.322175
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397
-0.322397

error
-0.785398
0.714602
-0.035398
0.162668
0.026489
0.000862
0.000314
0.000014
0.000004
0.000000
0.000000
0.000000
-0.000000

Table 7.3: Quadratic interpolation search iterates, function values and errors in iterates

P2! (v) > 0. Use the Intermediate Value Theorem (see Problem 6.0.1) to conclude there is a point d
between the points u and v for which P2! (d) = 0.
Problem 7.1.11. Show that the interpolation conditions in Problem 7.1.10 lead to the solution
listed for the coefficients g0 , g1 and g2 . Argue why the condition f (c) < min(f (a), f (b)) implies that
both g1 < 0 and g2 > 0.
Problem 7.1.12. Compute the derivative P2! and determine the value d for which P2 *(d) = 0. Hint:
The derivative P2! (x) is a linear function of x.
Problem 7.1.13. Compute the interpolating quadratic polynomial P2 , but this time with the data
ordered (c, f (c)), (b, f (b)) and (a, f (a)). For this data, the Newton form of this polynomial is
P2 (x) = h0 + (x c)h1 + (x c)(x b)h2
From the interpolating conditions, derive formulas for the coefficients h1 , h2 and h3 . Argue why
f (c) < min(f (a), f (b)) implies that both h1 > 0 and h2 > 0. Argue why h2 = g2 . Determine the
c+b
value d for which P2! (d) = 0, and argue why d <
. Hint: The quadratic interpolating polynomial
2
for this data is unique, regardless of how the data is ordered. So, the power series coefficients of the
quadratic P2 (x) are unique. How are the coefficients g2 and h2 in this form related to the coefficient
of x2 of the Newton form of P2 (x)?
Problem 7.1.14. Consider the Ushaped function
f (x) =

1
x(1 x)2

on [a, b] = [0.01, 0.99]. Using c = 0.02 as the initial value, carry out three iterations of quadratic
search for the minimum. What is the value of xm for this function, and how is it related to the
values c and d computed by each iteration? Remark: The bracket endpoint b remains frozen in this
example. The behavior here is similar to that false position for finding a root.

7.2

Searches using the Derivative

Suppose that we can compute values of both the function f and its derivative f ! at any point x.
There follow descriptions of two algorithms that incorporate information from both f and f ! in the
search for location of the local minimum of f . The first extends the method of the previous section
whereas the second uses techniques from root finding.

208

7.2.1

CHAPTER 7. UNIVARIATE MINIMIZATION

Cubic Interpolation Search

For brevity, we use the phrase cubic search to describe the search for the minimum of a Ushaped
function f using cubic interpolation. Let f be Ushaped on [a, b]. We suppose that f ! (a)f ! (b) < 0,
for otherwise f has an endpoint extremum. Because f is Ushaped, it follows that f ! (a) < 0 and
f ! (b) > 0.
The key computation performed by cubic search is the construction of the cubic Hermite polynomial P3 that interpolates values f (x) and f ! (x) at the endpoints a and b; that is,
P3 (a) = f (a), P3! (a) = f ! (a), P3 (b) = f (b), P3! (b) = f ! (b)
This interpolating polynomial was introduced in Problem 4.1.21. If t (x a)/h with h b a,
then
P3 (x) = f (a)(t) + f (b)(1 t) + hf ! (a)(t) hf ! (b)(1 t)

where the cubic polynomials (s) = (1 + 2s)(1 s)2 and (s) = s(1 s)2 .
Note that P3! (x) = 0 is a quadratic equation that has at most two roots; remember the coefficient
of x2 may be zero. Since P3! (a) = f ! (a) < 0 and P3! (b) = f ! (b) > 0, by the Intermediate Value
Theorem one root c lies in the open interval (a, b) and the other root, if it exists, must lie outside
[a, b]. The root c (a, b) corresponds to a local minimum value of the function P3 (x).
The cubic search assumes that an initial bracket [a, b] for the minimum of the function f is
given. At startup we determine the values f (a), f ! (a), f (b) and f ! (b) and check that f ! (a) < 0 and
f ! (b) > 0; an error is reported if these inequalities are not satisfied. The cubic search iteration begins
by computing the location c of the unique minimum of the cubic Hermite interpolant P3 (x) that
interpolates f (x) and f ! (x) at the endpoints a and b. If f ! (c) = 0, then the cubic search stops because
the point c is also the location of the minimum of the function f . Also, if f (c) max(f (a), f (b)),
then one should report an error because the function f is not Ushaped. If f ! (c) < 0, then the
cubic search moves the endpoint a to the point c by re-labelling c as a, and re-labelling f (c) as
f (a). Similarly, if f ! (c) > 0, then the cubic search moves the endpoint b to the point c. The process
continues until the bracket on the location of the minimum is reduced to a length less than a user
error tolerance.
Problem 7.2.1. Suppose f is a Ushaped function on [a, b] with f ! (a)f ! (b) 0. Show that f has
an endpoint extremum.
Problem 7.2.2. Suppose f is a Ushaped function on [a, b] with f ! (a)f ! (b) < 0. Show that f ! (a) < 0
and f ! (b) > 0.
Problem 7.2.3. Let f be a Ushaped function on [a, b] with f ! (a) < 0 and f ! (b) > 0. Let P3 (x) be
the cubic Hermite polynomial that interpolates values f (x) and f ! (x) at the endpoints a and b. In
the Newton form, we can write its derivative
P3! (x) = g0 + (x a)g1 + (x a)(x b)g2
Show that the derivative interpolation conditions imply that g0 < 0 and g1 > 0. Assume that g2 "= 0.
Observe that the roots of P3! (x) = 0 are located at the points where the straight line y = g0 + (x a)g1
intersects the parabola y = (x a)(x b)g2 . Sketch this line and this parabola and show that,
regardless of the value of the coefficient g2 , the line and the parabola always intersect at two distinct
points. Show that only one of these intersection points lies in (a, b).
Problem 7.2.4. Let f be a Ushaped function on [a, b] with f ! (a) < 0 and f ! (b) > 0. Let P3 (x) be
the cubic Hermite polynomial that interpolates values f (x) and f ! (x) at the endpoints a and b. By
counting turning points, show that P3 (x) has a unique minimum located at a point c in (a, b).
Problem 7.2.5. Let f be a Ushaped function on [a, b] with f ! (a) < 0 and f ! (b) > 0. Let the
function Q(x) = P3! (x) where P3 (x) is the cubic Hermite polynomial that interpolates values f (x)
and f ! (x) at the endpoints a and b. Note that Q(x) is a quadratic with Q! (a) < 0 and Q! (b) > 0.

209

7.2. SEARCHES USING THE DERIVATIVE

Use the Intermediate Value Theorem (see Problem 6.0.1) to show that there is a point c (a, b)
where Q(c) = 0.
Use the Mean Value Theorem (see Problem 6.0.3) to show that there is a point u (a, c) where
Q! (u) > 0. Use the Mean Value Theorem again to show that there is a point v (c, b) where
Q! (v) > 0.
Use the fact that Q! (x) is a linear polynomial, and the facts established above, to show that
Q! (c) > 0.
Conclude that the cubic polynomial P3 (x) has a unique minimum located at a point c (a, b).

Problem 7.2.6. Consider the cubic Hermite polynomial P3 (x) that interpolates values f (x) and
f ! (x) at the endpoints a and b. Assume that f ! (a) < 0 and f ! (b) > 0. Show that
1. The derivative
where
= 3 [f ! (a) + f ! (b)] 6

Q(x)

dP3
(x) = t2 2t +
dx

f (b) f (a)
,
h

= 2f ! (a) + f ! (b) 3

f (b) f (a)
,
h

= f ! (a)

2. The discriminant of the quadratic polynomial Q(x) is

'
(2
f (b) f (a)
2 = f ! (a) + f ! (b) 3
f ! (a)f ! (b)
h
3. The discriminant is positive. Note, the roots of the quadratic are distinct real numbers when
the discriminant is positive.
)
4. The local minimum of P3 (x) is located at the point + 2 .

Problem 7.2.7. Develop a pseudocode that implements the cubic interpolant search for the minimum
of the function f . Assume the user has provided an initial bracket [a, b] and the names of the
subprograms that compute values f (x) and f ! (x).

7.2.2

Secant Search

Let the function f be Ushaped on [a, b]. We suppose that f ! (a)f ! (b) < 0, for otherwise f (x) has
an endpoint extremum. Because f is Ushaped, it follows that f ! (a) < 0 and f ! (b) > 0.
The secant search is based on using the method of false position for finding a root of f ! (x).
Specifically, it chooses the point c as the x-intercept of the secant line through the points (a, f ! (a))
and (b, f ! (b)); that is,
f ! (a)
c = a (b a) !
f (b) f ! (a)
The secant search then moves one endpoint, a or b, to the point c as in the cubic search. Note that
the secant search does not use values f (x) in choosing the new bracket.
Because the secant search is the method of false position for finding a root of f ! (x), it suffers
from the same problems as the method of false position, see Section 6.4.2. In particular, the secant
search is likely to get stuck, i.e., one end of the bracket remains unchanged at each iteration, and a
special step (such as bisection) is needed to break this pattern.
Problem 7.2.8. Let f be a Ushaped function on [a, b] with f ! (a) < 0 and f ! (b) > 0. By drawing
a sketch of the values f ! (x) on [a, b], argue geometrically that the x-intercept, c, of the secant line
through the points (a, f ! (a)) and (b, f ! (b)) must lie in (a, b). Obtain the same result, but this time
using the algebraic formula for the point c to prove that it must lie in (a, b).
Problem 7.2.9. Write an algorithm which keeps track of the assignments which continually reset
an endpoint. Use a special step to break this pattern. Demonstrate pictorially how your method
works. Find a function f for which this continual resetting phenomenon occurs.

210

CHAPTER 7. UNIVARIATE MINIMIZATION

7.3

Matlab Notes

Using the basic techniques developed for iterative methods in Section 6.7, it is not difficult to write
Matlab implementations of the optimization methods discussed in this chapter. We therefore leave
these as exercises.
Problem 7.3.1. Write a Matlab function m-file that implements the golden section search method,
and use it to find a local minimum of f (x) = ex sin(x) on the interval [0, 3]. Start with the bracket
[1, 2] and iterate until the length of the bracket is less than 102 .
Problem 7.3.2. Write a Matlab function m-file that implements the quadratic interpolation search
for the minimum, with the midpoint of [a, b] as the initial point c. Report all applicable errors. Now
consider using this to find a minimum of the function
f (x) =

x4 + 1
x2 2x + 1

on [a, b] = [10, 10]. Is this function Ushaped on the interval [10, 10]?
Problem 7.3.3. Consider the Ushaped function
*
1x
f (x) =
x 0.8

if x 0.9
otherwise

on [a, b] = [0, 1]. Use quadratic interpolation search for the minimum starting with the midpoint of
[a, b] as the initial point c. Report all applicable errors. Note that it may be easier to use a function
m-file to implement f (x), rather than an anonymous function, for this particular problem.
Problem 7.3.4. Use the quadratic interpolation search to find a local minimum of f (x) = ex
sin(x) on the interval [0, 1]. Start with the bracket [1, 2] and iterate until the length of the bracket is
less than 102 .
Matlabs main built-in method for finding a local minimum of a function of one variable is
fminbnd, which implements a combination of golden section and quadratic interpolation search.
The basic usage is
x = fminbnd(fun, x1, x2)
where, as usual, fun can be an inline or anonymous function, or a handle to a function m-file, and
[x1, x2] is an initial bracket of the minimum.
Example 7.3.1. To find the minimum of f (x) = ex sin(x) on the interval [0, 1.5], we can use
the Matlab statement:
>> x = fminbnd(@(x) -exp(-x).*sin(x), 0, 1.5)
The computed result is x 0.7854, which is an approximation of

4.

Example 7.3.2. Recall that max{f (x)} = min{f (x)}. Thus, if we want to find the maximum of
1
on the interval [0, 6], we can use the Matlab statement:
f (x) = 2
x 6x + 8
>> x = fminbnd(@(x) -1./(x.*x-6*x+10), 0, 6)

which computes x = 3. It is not difficult to confirm that (3, f (3)) is the maximum of f (x) on the
interval [0, 6].

211

7.3. MATLAB NOTES

It is important to keep in mind that if the f (x) is not U shaped, then fminbnd does not guarantee
to find a global minimum on an interval, as illustrated in the following example.
Example 7.3.3. Consider the function f (x) = x cos(7x) on the interval [4, 4]. A plot of f (x) is
shown in Fig. 7.6. Notice that the minimum is located approximately at the point (3.6109, 4.6006).
If we compute
>> x = fminbnd(@(x) x-cos(7*x), -4, 4)
the result is x 0.9181. Although this is a local minimum, it is not the global minimum of f (x)
on the interval [4, 4]. If instead, we compute
>> x = fminbnd(@(x) x-cos(7*x), -4, 3)
the result is x 3.6109, which is the global minimum. Interestingly, though, if we further refine
the initial interval and compute
>> x = fminbnd(@(x) x-cos(7*x), -4, 2)
the result is x 2.7133, another local minimum.
5

g(x) = x cos(7x)
Local min, x 0.9181
Local min, x 2.7133
Local min, x 3.6109

5
4

Figure 7.6: Plot of the function used in Example 7.3.3: g(x) = x cos(7x) on the interval [4, 4].
Problem 7.3.5. Use fminbnd to compute a minimum of f (x) = x cos(7x) with initial intervals
[4, z], with z = 4, 3, 2, 1, 0, 1, 2, 3. What does fminbnd compute in each case?
Problem 7.3.6. Use fminbnd to find all local minima of f (x) = x2 cos(4x). What starting
interval did you use in each case? Hint: You might want to first plot the function, and use it to
determine appropriate starting intervals.

As with fzero (see Section 6.7.4), it is possible to reset certain default parameters used by
fminbnd (such as stopping tolerance and maximum number of iterations), and it is possible to
obtain more information on exactly what is done during the computation of the minimum (such as
number of iterations and number of function evaluations) by using the calling syntax

212

CHAPTER 7. UNIVARIATE MINIMIZATION

[x, fval, exitflag, output] = fminbnd(fun, x1, x2, options)

where
x is the computed approximation of the local minimizer in the interval [x1, x2].
fval is the function value f (xmin ).
exitflag provides information about what condition caused fminbnd to terminate; see doc
fminbnd for more information.
output is a structure array that contains information such as which algorithms were used (e.g.,
golden section search or parabolic interpolation), number of function evaluations and number
of iterations.
options is an input parameter that can be used, for example, to reset the stopping tolerance,
and to request that results of each iteration be displayed in the command window. The options
are set using the built-in Matlab function optimset.
The following example illustrate how to use options and output.
1
. It is not difficult to show that f (x) has
x(1 x)2
1
a local minimizer x = 3 . Suppose we execute the Matlab commands:

Example 7.3.4. Consider the function f (x) =

>> options = optimset(TolX, 1e-15, Display, iter);

>> [x, fval, exitflag, output] = fminbnd(@(x) 1./(x.*(1-x).^2), 0.001, 0.999, options);
Because we used optimset to set the options field to display the iterations, the following information
is displayed in the command window:
Func-count
1
2
3
4
5
6
7
8
9
10
11
12
13

x
0.382202
0.617798
0.236596
0.334568
0.336492
0.333257
0.333332
0.333333
0.333333
0.333333
0.333333
0.333333
0.333333

f(x)
6.8551
11.0807
7.25244
6.75007
6.75045
6.75
6.75
6.75
6.75
6.75
6.75
6.75
6.75

Procedure
initial
golden
golden
parabolic
parabolic
parabolic
parabolic
parabolic
parabolic
parabolic
parabolic
golden
parabolic

Optimization terminated:
the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-15
which shows that some iterations perform a golden section search, while others perform a quadratic
interpolation search (the table uses golden to refer to golden section search, and parabolic to refer
to quadratic interpolation search). We also see that a total of 13 function evaluations are needed to
compute the minimizer. This can also be seen by displaying output, which provides the following
information:
iterations:
funcCount:
algorithm:
message:

12
13
golden section search, parabolic interpolation
[1x111 char]

7.3. MATLAB NOTES

213

The message can be viewed by simply entering the following command:

>> output.message

Problem 7.3.7. Use fminbnd to find a minimum of f (x) = ex sin(x). Start with the bracket
[1, 2]. How many iterations used a golden section search, and how many used a parabolic interpolation
search? Use the default TolX. Do the results change if TolX is changed to 1015 ?
Problem 7.3.8. Use fminbnd to find a minimum of f (x) = |x 7|. Start with the bracket [6, 8].
How many iterations used a golden section search, and how many used a parabolic interpolation
search? Use the default TolX. Do the results change if TolX is changed to 1015 ?
Problem 7.3.9. Repeat Problem 7.3.5, and report on how many iterations used a golden section
search, and how many used a parabolic interpolation search. Do the result change if TolX is changed
to 1015 ?
Problem 7.3.10. Repeat Problem 7.3.6, and report on how many iterations used a golden section
search, and how many used a parabolic interpolation search. Do the result change if TolX is changed
to 1015 ?