3 Bracketing
This chapter presents a variety of bracketing methods for univariate functions,or functions involving a single variable. Bracketing is the process of identifying
an interval in which a local minimum lies and then successively shrinking theinterval. For many functions, derivative information can be helpful in directing
the search for an optimum, but, for some functions, this information may not be
available or might not exist. This chapter outlines a wide variety of approaches
that leverage different assumptions. Later chapters that consider multivariate
optimization will build upon the concepts introduced here.

3.1 Unimodality
Several of the algorithms presented in this chapter assume unimodality of theobjective function. A unimodal function f is one where there is a unique x ∗ , suchthat f is monotonically decreasing for x ≤ x ∗ and monotonically increasing forx ≥ x ∗ . It follows from this definition that the unique global minimum is at x ∗ ,and there are no other local minima.1
Given a unimodal function, we can bracket an interval [ a, c] containing the global
minimum if we can find three points a < b < c, such that f ( a) > f (b) < f (c).
Figure 3.1 shows an example.

3.2 Finding an Initial Bracket
When optimizing a function, we often start by first bracketing an interval containing a local minimum. We then successively reduce the size of the bracketedinterval to converge on the local minimum. A simple procedure (algorithm 3.1)
can be used to find an initial bracket. Starting at a given point, we take a step

It is perhaps more conventional todefine unimodal functions in the
opposite sense, such that there isa unique global maximum rather
than a minimum. However, in thistext, we try to minimize functions,and so we use the definition in thisparagraph.

1

36 c ha p te r 3. bra c ke ti n g

Figure 3.1. Three points shownbracketing a minimum.

ab cin the positive direction. The distance we take is a hyperparameter to this algorithm,2 but the algorithm provided defaults it to 1 × 10−2 . We then search in thedownhill direction to find a new point that exceeds the lowest point. With each
step, we expand the step size by some factor, which is another hyperparameterto this algorithm that is often set to 2. An example is shown in figure 3.2. Functions without local minima, such as exp( x ), cannot be bracketed and will cause
bracket_minimum to fail.
function bracket_minimum(f, x=0; s=1e-2, k=2.0)
a, ya = x, f(x)b, yb = a + s, f(a + s)
if yb > yaa, b = b, aya, yb = yb, ya
s = -send
while truec, yc = b + s, f(b + s)
if yc > yb
return a < c ? (a, c) : (c, a)
end
a, ya, b, yb = b, yb, c, yc
s *= kend
end

A hyperparameter is a parameterthat governs the function of an algorithm. It can be set by an expert
or tuned using an optimization algorithm. Many of the algorithms inthis text have hyperparameters. We
often provide default values suggested in the literature. The successof an algorithm can be sensitive tothe choice of hyperparameter.

2

Algorithm 3.1. An algorithm forbracketing an interval in which a
local minimum must exist. It takes
as input a univariate function f andstarting position x, which defaults
to 0. The starting step size s andthe expansion factor k can be specified. It returns a tuple containing
the new interval [ a, b].

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

y

3. 3. fi bon a c c i se a rc h 37

ab

ba
x

x

b a
x

3.3 Fibonacci Search
Suppose we have a unimodal f bracketed by the interval [ a, b]. Given a limiton the number of times we can query the objective function, Fibonacci search(algorithm 3.2) is guaranteed to maximally shrink the bracketed interval.
Suppose we can query f only twice. If we query f on the one-third and twothird points on the interval, then we are guaranteed to remove one-third of ourinterval, regardless of f , as shown in figure 3.3.
2

1

new interval if y1 < y2bax

Figure 3.2. An example of running bracket_minimum on a function. The method reverses direction between the first and second
iteration and then expands until
a minimum is bracketed in the
fourth iteration.

Figure 3.3. Our initial guess for two
queries will remove one-third of
the initial interval.

new interval if y1 > y2
We can guarantee a tighter bracket by moving our guesses toward the center.
In the limit as ǫ → 0, we are guaranteed to shrink our interval by a factor of two
as shown in figure 3.4.
Figure 3.4. The most we can guarantee to shrink our interval is byjust under a factor of two.

ǫ
new interval if y1 < y2
new interval if y1 > y2

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

38 c ha p te r 3. bra c ke ti n g

With three queries, we can shrink the interval by a factor of three. We firstquery f on the one-third and two-third points on the interval, discard one-third of
the interval, and then sample just next to the better sample as shown in figure 3.5.
Figure 3.5. With three queries wecan shrink the domain by a factorof three. The third query is madebased on the result of the first two
queries.

2

1
3

For n queries, the interval lengths are related to the Fibonacci sequence: 1, 1,
2, 3, 5, 8, and so forth. The first two terms are one, and the following terms arealways the sum of the previous two:1
if n ≤ 2
Fn =(3.1)
 Fn−1 + Fn−2 otherwise
Figure 3.6 shows the relationship between the intervals. Example 3.1 walks
through an application to a univariate function.

Figure 3.6. For n queries we are
guaranteed to shrink our interval
by a factor of Fn+1 . The length of every interval constructed during Fibonacci search can be expressed interms of the final interval times a Fibonacci number. If the final, smallest interval has length In , then thesecond smallest interval has length
In−1 = F3 In , the third smallest interval has length In−2 = F4 In , andso forth.

I1 = I2 + I3 = 8I5
I2 = I3 + I4 = 5I5
I3 = I4 + I5 = 3I5
I4 = 2I5
I5The Fibonacci sequence can be determined analytically using Binet’s formula:ϕ n − (1 − ϕ ) n
√
,
5

(3.2)

Fn
1 − s n +1
=ϕ
Fn−1
1 − sn

(3.3)

Fn =

√
where ϕ = (1 + 5)/2 ≈ 1.61803 is the golden ratio.
The ratio between successive values in the Fibonacci sequence is:where s = (1 −√5) / (1 +√5) ≈ −0.382.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 4 . g ol d e n se c ti on se a rc h 39

Algorithm 3.2. Fibonacci search
to be run on univariate function f, with bracketing interval[ a, b], for n > 1 function evaluations. It returns the new interval(a, b). The optional parameter ϵcontrols the lowest-level interval.
The golden ratio φ is defined inBase.MathConstants.jl.

function fibonacci_search(f, a, b, n; ϵ=0.01)
s = (1-√5)/(1+√5)
ρ = 1 / (φ*(1-s^(n+1))/(1-s^n))d = ρ*b + (1-ρ)*ayd = f(d)for i in 1 : n-1
if i == n-1c = ϵ*a + (1-ϵ)*delse
c = ρ*a + (1-ρ)*b
end
yc = f(c)if yc < ydb, d, yd = d, c, yc
else
a, b = b, cend
ρ = 1 / (φ*(1-s^(n-i+1))/(1-s^(n-i)))end
return a < b ? (a, b) : (b, a)end

3.4 Golden Section Search
If we take the limit for large n, we see that the ratio between successive values of
the Fibonacci sequence approaches the golden ratio:
Fn
= ϕ.
lim
n→∞ Fn−1(3.4)

Golden section search (algorithm 3.3) uses the golden ratio to approximate Fibonacci
search. Figure 3.7 shows the relationship between the intervals. Figures 3.8 and 3.9
compare Fibonacci search with golden section search on unimodal and nonunimodal functions, respectively.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

40 c ha p te r 3. bra c ke ti n g

Consider using Fibonacci search with five function evaluations to minimizef ( x ) = exp( x − 2) − x over the interval [ a, b] = [−2, 6]. The first two function
evaluations are made at FF56 and 1 − FF65 , along the length of the initial bracketinginterval:
F5f ( x (1) ) = f a + ( b − a ) 1 −= f (1) = −0.632
F6


F5
= f (3) = −0.282
f ( x (2) ) = f a + ( b − a )F6

Example 3.1. Using Fibonacci
search with five function evaluations to optimize a univariate function.

The evaluation at x (1) is lower, yielding the new interval [ a, b] = [−2, 3].
Two evaluations are needed for the next interval split:F
xleft = a + (b − a) 1 − 4 = 0
F5F4xright = a + (b − a) = 1
F5
A third function evaluation is thus made at xleft , as xright has already been
evaluated:f ( x (3) ) = f (0) = 0.135
The evaluation at x (1) is lower, yielding the new interval [ a, b] = [0, 3].
Two evaluations are needed for the next interval split:
F3
xleft = a + (b − a) 1 −=1
F4
F3
xright = a + (b − a) = 2
F4
A fourth functional evaluation is thus made at xright , as xleft has alreadybeen evaluated:f ( x (4) ) = f ( 2 ) = − 1

The new interval is [ a, b] = [1, 3]. A final evaluation is made just next tothe center of the interval at 2 + ǫ, and it is found to have a slightly higher
value than f (2). The final interval is [1, 2 + ǫ].

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 4 . g ol d e n se c ti on se a rc h 41

I1
I2 = I1 ϕ−1Figure 3.7. For n queries of a univariate function we are guaranteed
to shrink a bracketing interval by afactor of ϕn−1 .

I3 = I1 ϕ−2
I4 = I1 ϕ−3
I5 = I1 ϕ−4function golden_section_search(f, a, b, n)
ρ = φ-1
d = ρ * b + (1 - ρ)*ayd = f(d)for i = 1 : n-1
c = ρ*a + (1 - ρ)*b
yc = f(c)if yc < ydb, d, yd = d, c, yc
else
a, b = b, c
end
end
return a < b ? (a, b) : (b, a)
end

Algorithm 3.3. Golden section
search to be run on a univariate
function f, with bracketing interval [ a, b], for n > 1 function evaluations. It returns the new interval (a, b). Julia already has thegolden ratio φ defined. Guaranteeing convergence to within ǫ requires n = (b − a)/(ǫ ln ϕ) iterations.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

42 c ha p te r 3. bra c ke ti n gyFibonacci Search

x

x

x

x

x

y

Golden Section Search

x

x

x

x

x
Figure 3.8. Fibonacci and golden
section search on a unimodal function.

yFibonacci Search

x

x

x

x

x

x

x

y

Golden Section Search

x

x

x

Figure 3.9. Fibonacci and golden
section search on a nonunimodal
function. Search is not guaranteed
to find a global minimum.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 5 . q u a d ra ti c fi t se a rc h 43

3.5 Quadratic Fit Search
Quadratic fit search leverages our ability to analytically solve for the minimumof a quadratic function. Many local minima look quadratic when we zoom inclose enough. Quadratic fit search iteratively fits a quadratic function to threebracketing points, solves for the minimum, chooses a new set of bracketing points,
and repeats as shown in figure 3.10.
Given bracketing points a < b < c, we wish to find the coefficients p1 , p2 , andp3 for the quadratic function q that goes through ( a, y a ), (b, yb ), and (c, yc ):q ( x ) = p1 + p2 x + p3 x 2(3.5)

y a = p1 + p2 a + p3 a2(3.6)

y b = p1 + p2 b + p3 b2

(3.7)

2

(3.8)

y c = p1 + p2 c + p3 cyx
Figure 3.10. Quadratic fit search fitsa quadratic function to three bracketing points (black dots) and uses
the analytic minimum (blue dot)
to determine the next set of bracketing points.

In matrix form, we have
  
1
ya
  
 y b  = 1
yc
1

a
b
c

 
a2
p1
 
2
b   p2 c2
p3

We can solve for the coefficients through matrix inversion: −1    
1 a a2
ya
p1
  
  
2
 p2  = 1 b b   y b p3
1 c c2yc(3.9)(3.10)

Our quadratic function is then( x − b)( x − c)( x − a)( x − c)( x − a)( x − b)
+ yb
+ yc
( a − b)( a − c)(b − a)(b − c)(c − a)(c − b)
We can solve for the unique minimum by finding where the derivative is zero:q( x ) = y ax∗ =1 y a ( b2 − c2 ) + y b ( c2 − a2 ) + y c ( a2 − b2 )2y a (b − c) + yb (c − a) + yc ( a − b)(3.11)(3.12)

Quadratic fit search is typically faster than golden section search. It may needsafeguards for cases where the next point is very close to other points. A basic
implementation is provided in algorithm 3.4. Figure 3.11 shows several iterationsof the algorithm.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

44 c ha p te r 3. bra c ke ti n g

Algorithm 3.4. Quadratic fit search
to be run on univariate function f,with bracketing interval [ a, c] witha < b < c. The method will run for
n function evaluations. It returns
the new bracketing values as a tuple, (a, b, c).

yfunction quadratic_fit_search(f, a, b, c, n)ya, yb, yc = f(a), f(b), f(c)for i in 1:n-3
x = 0.5*(ya*(b^2-c^2)+yb*(c^2-a^2)+yc*(a^2-b^2)) /(ya*(b-c)+yb*(c-a)+yc*(a-b))yx = f(x)if x > b
if yx > yb
c, yc = x, yx
else
a, ya, b, yb = b, yb, x, yx
endelseif x < b
if yx > yb
a, ya = x, yx
else
c, yc, b, yb = b, yb, x, yx
end
end
end
return (a, b, c)
end

a

b

c
x

ab
x

c

a b
x

c

ab

c

x
Figure 3.11. Four iterations of thequadratic fit method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 6 . shu be rt-p i y a vski i me thod45

3.6 Shubert-Piyavskii Method
In contrast with previous methods in this chapter, the Shubert-Piyavskii method3
is a global optimization method over a domain [ a, b], meaning it is guaranteed toconverge on the global minimum of a function irrespective of any local minima
or whether the function is unimodal. A basic implementation is provided byalgorithm 3.5.
The Shubert-Piyavskii method requires that the function be Lipschitz continuous,
meaning that it is continuous and there is an upper bound on the magnitude ofits derivative. A function f is Lipschitz continuous on [ a, b] if there exists an ℓ > 0such that:4| f ( x ) − f (y)| ≤ ℓ| x − y| for all x, y ∈ [ a, b](3.13)

Intuitively, ℓ is as large as the largest unsigned instantaneous rate of change
the function attains on [ a, b]. Given a point ( x0 , f ( x0 )), we know that the lines
f ( x0 ) − ℓ( x − x0 ) for x > x0 and f ( x0 ) + ℓ( x − x0 ) for x < x0 form a lower boundof f .
The Shubert-Piyavskii method iteratively builds a tighter and tighter lower
bound on the function. Given a valid Lipschitz constant ℓ, the algorithm begins bysampling the midpoint, x (1) = ( a + b)/2. A sawtooth lower bound is constructedusing lines of slope ±ℓ from this point. These lines will always lie below f if ℓ isa valid Lipschitz constant as shown in figure 3.12.

y

f (x)
lower bound

S. Piyavskii, “An Algorithm for
Finding the Absolute Extremum
of a Function,” USSR Computational Mathematics and Mathematical Physics, vol. 12, no. 4, pp. 57–67,
1972. B. O. Shubert, “A Sequential
Method Seeking the Global Maximum of a Function,” SIAM Journal
on Numerical Analysis, vol. 9, no. 3,
pp. 379–388, 1972.
3

We can extend the definition of
Lipschitz continuity to multivariate functions, where x and y arevectors and the absolute value isreplaced by any vector norm.
4

Figure 3.12. The first iteration of the
Shubert-Piyavskii method.

ℓ
1

a

x (1)
x

b

Upper vertices in the sawtooth correspond to sampled points. Lower vertices
correspond to intersections between the Lipschitz lines originating from each© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

46 c ha p te r 3. bra c ke ti n gsampled point. Further iterations find the minimum point in the sawtooth, evaluate the function at that x value, and then use the result to update the sawtooth.
Figure 3.13 illustrates this process.
Figure 3.13. Updating the lower
bound involves sampling a new
point and intersecting the newlines with the existing sawtooth.

y

f (x)
lower bounda = x (2)

x (1)
x

x (4)

b = x (3)The algorithm is typically stopped when the difference in height between theminimum sawtooth value and the function evaluation at that point is less thana given tolerance ǫ. For the minimum peak ( x (n) , y(n) ) and function evaluationf ( x (n) ), we thus terminate if y(n) − f ( x (n) ) < ǫ.
The regions in which the minimum could lie can be computed using this update
information. For every peak, an uncertainty region can be computed according
to:


1
1
(3.14)
x (i) − (ymin − y(i) ), x (i) + (ymin − y(i) )ℓℓfor each sawtooth lower vertex ( x (i) , y(i) ) and the minimum sawtooth upper vertex( xmin , ymin ). A point will contribute an uncertainty region only if y(i) < ymin . The
minimum is located in one of these peak uncertainty regions.
The main drawback of the Shubert-Piyavskii method is that it requires knowing
a valid Lipschitz constant. Large Lipschitz constants will result in poor lower
bounds. Figure 3.14 shows several iterations of the Shubert-Piyavskii method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 6 . shu be rt-p i y a vski i me thod 47

struct Ptxyend
function _get_sp_intersection(A, B, l)t = ((A.y - B.y) - l*(A.x - B.x)) / 2l
return Pt(A.x + t, A.y - t*l)end
function shubert_piyavskii(f, a, b, l, ϵ, δ=0.01)
m = (a+b)/2
A, M, B = Pt(a, f(a)), Pt(m, f(m)), Pt(b, f(b))
pts = [A, _get_sp_intersection(A, M, l),M, _get_sp_intersection(M, B, l), B]
Δ = Infwhile Δ > ϵi = argmin([P.y for P in pts])
P = Pt(pts[i].x, f(pts[i].x))
Δ = P.y - pts[i].yAlgorithm 3.5. The ShubertPiyavskii method to be run on
univariate function f, with bracketing interval a < b and Lipschitz
constant l. The algorithm runs
until the update is less than thetolerance ϵ. Both the best point
and the set of uncertainty intervals
are returned. The uncertainty
intervals are returned as an arrayof (a,b) tuples. The parameter δ
is a tolerance used to merge theuncertainty intervals.

P_prev = _get_sp_intersection(pts[i-1], P, l)
P_next = _get_sp_intersection(P, pts[i+1], l)

end

end

deleteat!(pts, i)insert!(pts, i, P_next)
insert!(pts, i, P)
insert!(pts, i, P_prev)

intervals = []P_min = pts[2*(argmin([P.y for P in pts[1:2:end]])) - 1]
y_min = P_min.y
for i in 2:2:length(pts)if pts[i].y < y_min
dy = y_min - pts[i].yx_lo = max(a, pts[i].x - dy/l)x_hi = min(b, pts[i].x + dy/l)
if !isempty(intervals) && intervals[end][2] + δ ≥ x_lo
intervals[end] = (intervals[end][1], x_hi)
else
push!(intervals, (x_lo, x_hi))
end
end
end
return (P_min, intervals)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

48 c ha p te r 3. bra c ke ti n g

y

y

y

Figure 3.14. Nine iterations of the
Shubert-Piyavskii method proceeding left to right and top to bottom. The blue lines are uncertainty
regions in which the global minimum could lie.

x

x

x

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 7. bi se c ti on me thod 49

3.7

Bisection Method

The bisection method (algorithm 3.6) can be used to find roots of a function, or points
where the function is zero. Such root-finding methods can be used for optimization
by applying them to the derivative of the objective, locating where f ′ ( x ) = 0. In
general, we must ensure that the resulting points are indeed local minima.
The bisection method maintains a bracket [ a, b] in which at least one root is
known to exist. If f is continuous on [ a, b], and there is some y ∈ [ f ( a), f (b)], thenthe intermediate value theorem stipulates that there exists at least one x ∈ [ a, b], suchthat f ( x ) = y as shown in figure 3.15. It follows that a bracket [ a, b] is guaranteed
to contain a zero if f ( a) and f (b) have opposite signs.
The bisection method cuts the bracketed region in half with every iteration.
The midpoint ( a + b)/2 is evaluated, and the new bracket is formed from the
midpoint and whichever side that continues to bracket a zero. We can terminate
immediately if the midpoint evaluates to zero. Otherwise we can terminate after
a fixed number of iterations. Figure 3.16 shows four iterations of the bisection
method. This method is guaranteed to converge within ǫ of x ∗ within lg
iterations, where lg denotes the base 2 logarithm.

f (b)yf ( a)a xb

Figure 3.15. A horizontal line
drawn from any y ∈ [ f ( a), f (b)]must intersect the graph at leastonce.

|b− a|
ǫf′Figure 3.16. Four iterations of thebisection method. The horizontal
line corresponds to f ′ ( x ) = 0. Notethat multiple roots exist within theinitial bracket.
x

x

x

x

Root-finding algorithms like the bisection method require starting intervals[ a, b] on opposite sides of a zero. That is, sign( f ′ ( a)) 6= sign( f ′ (b)), or equivalently, f ′ ( a) f ′ (b) ≤ 0. Algorithm 3.7 provides a method for automatically determining such an interval. It starts with a guess interval [ a, b]. So long as theinterval is invalid, its width is increased by a constant factor. Doubling the interval size is a common choice. This method will not always succeed as shownin figure 3.17. Functions that have two nearby roots can be missed, causing theinterval to infinitely increase without termination.
The Brent-Dekker method is an extension of the bisection method. It is a rootfinding algorithm that combines elements of the secant method (section 6.2) andinverse quadratic interpolation. It has reliable and fast convergence properties, andf′xFigure 3.17. A bracketing method
initialized such that it straddles thetwo roots in this figure will expand
forever, never to find a sign change.
Also, if the initial interval is between the two roots, doubling theinterval can cause both ends of theinterval to simultaneously pass thetwo roots.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

50 c ha p te r 3. bra c ke ti n gfunction bisection(f′, a, b, ϵ)
if a > b; a,b = b,a; end # ensure a < bya, yb = f′(a), f′(b)if ya == 0; b = a; end
if yb == 0; a = b; end
while b - a > ϵx = (a+b)/2
y = f′(x)if y == 0a, b = x, x
elseif sign(y) == sign(ya)
a = x
else
b = x
end
end
end

return (a,b)

function bracket_sign_change(f′, a, b; k=2)
if a > b; a,b = b,a; end # ensure a < bcenter, half_width = (b+a)/2, (b-a)/2
while f′(a)*f′(b) > 0
half_width *= ka = center - half_widthb = center + half_width
end
end

Algorithm 3.6. The bisection algorithm, where f′ is the derivative of the univariate function weseek to optimize. We have a < bthat bracket a zero of f′. The interval width tolerance is ϵ. Callingbisection returns the new bracketed interval [ a, b] as a tuple.
The prime character ′ is not anapostrophe. Thus, f′ is a variablename rather than a transposed vector f. The symbol can be created bytyping \prime and hitting tab.

Algorithm 3.7. An algorithm forfinding an interval in which a signchange occurs. The inputs are thereal-valued function f′ defined on
the real numbers, and starting interval [ a, b]. It returns the new interval as a tuple by expanding theinterval width until there is a signchange between the function evaluated at the interval bounds. The
expansion factor k defaults to 2.

return (a,b)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

3. 8 . su mma ry 51

it is the univariate optimization algorithm of choice in many popular numerical
optimization packages.5

3.8 Summary• Many optimization methods shrink a bracketing interval, including Fibonacci
search, golden section search, and quadratic fit search.
• The Shubert-Piyavskii method outputs a set of bracketed intervals containing
the global minima, given the Lipschitz constant.

The details of this algorithm canbe found in R. P. Brent, Algorithms
for Minimization Without Derivatives.
Prentice Hall, 1973. The algorithm
is an extension of the work by
T. J. Dekker, “Finding a Zero by
Means of Successive Linear Interpolation,” in Constructive Aspects of
the Fundamental Theorem of Algebra,
B. Dejon and P. Henrici, eds., Interscience, 1969.
5• Root-finding methods like the bisection method can be used to find where thederivative of a function is zero.

3.9 Exercises
Exercise 3.1. Give an example of a problem when Fibonacci search is preferredover the bisection method.
Exercise 3.2. What is a drawback of the Shubert-Piyavskii method?
Exercise 3.3. Give an example of a nontrivial function where quadratic fit searchwould identify the minimum correctly once the function values at three distinct
points are available.
Exercise 3.4. Suppose we have f ( x ) = x2 /2 − x. Apply the bisection method tofind an interval containing the minimizer of f starting with the interval [0, 1000].
Execute three steps of the algorithm.
Exercise 3.5. Suppose we have a function f ( x ) = ( x + 2)2 on the interval [0, 1].
Is 2 a valid Lipschitz constant for f on that interval?
Exercise 3.6. Suppose we have a unimodal function defined on the interval [1, 32].
After three function evaluations of our choice, will we be able to narrow the
optimum to an interval of at most length 10? Why or why not?

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com