Skip to content

Lesson 38: One-Dimensional Minimisation: Bracketing and Elimination

38.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Explain why every multivariable method needs a one-dimensional line search.
  2. Bracket a minimum by unrestricted search with an accelerated step.
  3. Apply exhaustive, dichotomous and interval-halving search, and state each one's reduction ratio.
  4. Compare the methods by function evaluations required for a given accuracy.
  5. Explain why interval halving needs \(3\) evaluations for the first stage but only \(2\) thereafter.

38.2 Why One Dimension Matters

Every multivariable algorithm in Lesson 42 has the same skeleton:

\[\mathbf{x}_{k+1}=\mathbf{x}_{k}+\alpha_k\,\mathbf{d}_k\]

— pick a direction \(\mathbf{d}_k\), then choose a step length \(\alpha_k\) by minimising

\[\phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{d}_k)\]

which is a function of the single variable \(\alpha\). This inner problem is the line search, and it is where most of the computing time in non-linear optimisation is actually spent. Fast, reliable one-dimensional methods are therefore the foundation of the whole subject.

The two phases

Phase Purpose Methods
Bracketing find an interval \([a,b]\) known to contain the minimum unrestricted search with accelerated step
Refinement shrink that interval to the required accuracy exhaustive, dichotomous, interval halving (this lesson); Fibonacci (L39); golden section (L40); interpolation (L41)

Every refinement method assumes unimodality on \([a,b]\) (Lesson 36). Bracketing is what earns the right to make that assumption.

Two families of method

  • Elimination (direct) methods use only function values. Robust; work on non-smooth and tabulated functions; convergence is linear.
  • Interpolation (gradient) methods use derivatives or fitted polynomials. Much faster near the optimum, but need smoothness and can fail far from it (Lesson 41).

38.3 Bracketing: Unrestricted Search with Accelerated Step

Algorithm. Choose a start \(x_0\) and step \(s>0\).

  1. Evaluate \(f(x_0)\) and \(f(x_0+s)\). If \(f\) increased, reverse the direction of \(s\).
  2. Repeatedly take \(x_{k+1}=x_k+s\) and double \(s\) each time, while \(f\) keeps falling.
  3. Stop at the first increase. The minimum is bracketed by the last three points visited.

Doubling ("accelerating") is what makes the method efficient: a minimum \(1000\) steps away is reached in about \(10\) evaluations rather than \(1000\).

38.4 Three Elimination Methods

Throughout, \(L_0=b-a\) is the initial interval and \(n\) the number of function evaluations — the proper measure of cost, since evaluating \(f\) usually dominates all other work.

Divide \([a,b]\) into \(n+1\) equal parts and evaluate \(f\) at the \(n\) interior points. The minimum lies between the neighbours of the smallest value.

\[\boxed{\ \frac{L_n}{L_0}=\frac{2}{n+1}\ }\]

Simple and completely parallelisable, but the worst method sequentially: the reduction is only linear in \(n\), whereas the methods below are exponential.

Place two points a tiny distance \(\delta\) apart, straddling the midpoint:

\[x_1=\frac{a+b}{2}-\frac{\delta}{2},\qquad x_2=\frac{a+b}{2}+\frac{\delta}{2}\]

Comparing \(f(x_1)\) and \(f(x_2)\) eliminates almost exactly half the interval. Repeating with \(n\) evaluations (\(n/2\) pairs):

\[\boxed{\ L_n=\frac{L_0}{2^{n/2}}+\delta\left(1-\frac{1}{2^{n/2}}\right)\ }\]

The \(\delta\) term is the price of the method: it cannot reduce the interval below \(\delta\), no matter how many evaluations are spent. Choosing \(\delta\) too small makes \(f(x_1)\) and \(f(x_2)\) numerically indistinguishable; too large and accuracy is lost. Both points are discarded at every stage — the method never reuses a function value, which is exactly the waste that Lessons 39–40 eliminate.

Evaluate at the midpoint \(x_m\) and the two quarter-points \(x_1=a+L/4\), \(x_2=b-L/4\).

Decision rule.

  • If \(f(x_1)<f(x_m)\): the minimum is in \([a,x_m]\) — discard the right half; \(x_1\) becomes the new midpoint.
  • Else if \(f(x_2)<f(x_m)\): the minimum is in \([x_m,b]\) — discard the left half; \(x_2\) becomes the new midpoint.
  • Else the minimum is in \([x_1,x_2]\) — discard both outer quarters; \(x_m\) stays the midpoint.

Each stage halves the interval:

\[\boxed{\ \frac{L_n}{L_0}=\left(\frac12\right)^{(n-1)/2}\ }\]

Why the exponent is \((n-1)/2\). The first stage costs \(3\) evaluations, but in every case the surviving interval inherits a usable midpoint, so each later stage costs only \(2\) more. With \(n\) evaluations there are \((n-1)/2\) halvings. Reusing computed values is the single idea that separates good line searches from bad ones, and it is developed to its logical conclusion in Lessons 39–40.

38.5 Solved Problems

Throughout §4 the test function is

\[f(x)=x^{2}+\frac{54}{x},\qquad x>0,\]

whose exact minimum is found from \(f'(x)=2x-\dfrac{54}{x^{2}}=0\Rightarrow x^{3}=27\Rightarrow x^{*}=3\), with \(f(3)=9+18=27\) and \(f''(x)=2+108/x^{3}>0\) (convex, so this is global).

Starting from \(x_0=1\) with step \(s=0.5\) and doubling, bracket the minimum.

Solution.

Step \(x\) \(s\) used \(f(x)=x^2+54/x\) Comment
0 1.0 — \(1+54=55.00000\) start
1 1.5 0.5 \(2.25+36=38.25000\) decreased — continue, double \(s\)
2 2.5 1.0 \(6.25+21.6=27.85000\) decreased — continue, double \(s\)
3 4.5 2.0 \(20.25+12=32.25000\) increased — stop
\[\boxed{\text{Bracket }[1.5,\ 4.5],\quad L_0=3.0}\]

Interpretation. Four evaluations located the minimum inside an interval of width \(3\). Without doubling, the same march at a constant step of \(0.5\) would have needed seven evaluations to reach \(4.5\). Acceleration matters more the worse the initial guess: the number of evaluations grows like \(\log_2(\text{distance})\) rather than linearly.

Note also the essential caution: this bracket is trustworthy only if \(f\) is unimodal on it. The three points \(1.5,\,2.5,\,4.5\) show a decrease then an increase, which is consistent with a single minimum but does not prove it.

Minimise \(f\) on \([1,5]\) by exhaustive search with \(8\) equal sub-intervals.

Solution. Step \(=(5-1)/8=0.5\).

\(x\) 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0
\(f(x)\) 55.000 38.250 31.000 27.850 27.000 27.679 29.500 32.250 35.800

The smallest value is at \(x=3.0\), so

\[\boxed{x^{*}\in[2.5,\ 3.5],\qquad L_{\text{final}}=1.0}\]

Efficiency. The grid has \(7\) interior points, so the theoretical ratio is \(L_n/L_0=2/(7+1)=0.25\), and indeed \(4\times0.25=1.0\) ✓. Counting the two endpoints, \(9\) evaluations were made in all.

Interpretation. Exhaustive search is the only method here that does not assume unimodality — it simply looks everywhere on a grid. That robustness is why it is the standard first pass on an unknown function. Its weakness is that the reduction is only linear: halving the final interval requires doubling the number of evaluations, whereas the next two methods halve it for a fixed extra couple of evaluations.

Minimise \(f\) on \([1,5]\) using \(6\) evaluations (\(3\) pairs) with \(\delta=0.1\).

Solution.

Pair 1. \([a,b]=[1,5]\), midpoint \(3.0\):

\[x_1=2.95,\ f_1=8.7025+18.30508=27.00758;\qquad x_2=3.05,\ f_2=9.3025+17.70492=27.00742\]

\(f_1>f_2\Rightarrow\) discard \([1,\,2.95]\). New interval \([2.95,\ 5]\), \(L=2.05\).

Pair 2. Midpoint \(3.975\):

\[x_1=3.925,\ f_1=29.16359;\qquad x_2=4.025,\ f_2=29.61677\]

\(f_1<f_2\Rightarrow\) discard \([4.025,\,5]\). New interval \([2.95,\ 4.025]\), \(L=1.075\).

Pair 3. Midpoint \(3.4875\):

\[x_1=3.4375,\ f_1=27.52550;\qquad x_2=3.5375,\ f_2=27.77892\]

\(f_1<f_2\Rightarrow\) discard \([3.5375,\,4.025]\).

\[\boxed{x^{*}\in[2.95,\ 3.5375],\qquad L_{6}=0.5875}\]

Check against the formula.

\[L_6=\frac{4}{2^{3}}+0.1\left(1-\frac{1}{2^{3}}\right)=0.5+0.0875=0.5875\ \checkmark\]

Interpretation. Note the first comparison: \(f_1=27.00758\) and \(f_2=27.00742\) differ in the fourth decimal place, because both points sit almost exactly at the flat bottom of the curve. This is the characteristic hazard of dichotomous search — near the optimum the decision rests on a difference that may be smaller than the numerical noise in evaluating \(f\). Here the near-tie was harmless, but a rounding error of \(10^{-4}\) would have sent the search the other way.

The \(\delta\) term also sets a floor: as \(n\to\infty\), \(L_n\to\delta=0.1\). No number of evaluations can beat \(\delta\), which is why dichotomous search is a teaching device rather than a production method.

Problem 4 — Interval halving

Minimise \(f\) on \([1,5]\) by interval halving, three stages.

Solution.

Stage 1. \([1,5]\), \(L=4\): \(x_1=2.0\), \(x_m=3.0\), \(x_2=4.0\).

\[f(x_1)=31.000,\quad f(x_m)=27.000,\quad f(x_2)=29.500\]

\(f(x_1)>f(x_m)\) and \(f(x_2)>f(x_m)\) \(\Rightarrow\) discard both outer quarters. New interval \([2,4]\), \(L=2\), with \(x_m=3\) retained.

Stage 2. \([2,4]\), \(L=2\): \(x_1=2.5\), \(x_m=3.0\) (already known!), \(x_2=3.5\).

\[f(2.5)=27.850,\quad f(3.0)=27.000,\quad f(3.5)=27.679\]

Again the midpoint wins \(\Rightarrow\) new interval \([2.5,3.5]\), \(L=1\).

Stage 3. \([2.5,3.5]\), \(L=1\): \(x_1=2.75\), \(x_m=3.0\), \(x_2=3.25\).

\[f(2.75)=27.19886,\quad f(3.0)=27.000,\quad f(3.25)=27.17788\]

Midpoint wins again.

\[\boxed{x^{*}\in[2.75,\ 3.25],\qquad L_{\text{final}}=0.5}\]

Evaluation count. Stage 1 used \(3\); stages 2 and 3 used \(2\) each (the midpoint was inherited), so \(n=7\) in total.

Check against the formula. \(\left(\tfrac12\right)^{(7-1)/2}=\left(\tfrac12\right)^{3}=\tfrac18\), and \(4\times\tfrac18=0.5\) ✓.

Interpretation. Compare with Problem 2: exhaustive search used \(9\) evaluations to reach \(L=1\), while interval halving used \(7\) to reach \(L=0.5\) — twice the accuracy for fewer evaluations. The whole difference is that interval halving reuses the midpoint. Note also that the true minimum \(x=3\) is the retained midpoint at every stage, so the method has effectively converged already; the interval merely certifies how much is known.

Problem 5 — Comparing the methods

How many evaluations does each method need to reduce \([1,5]\) to a final interval of \(0.05\) (an accuracy of \(1.25\,\%\))? Take \(\delta=0.01\) for the dichotomous method.

Solution. Required ratio \(L_n/L_0=0.05/4=0.0125\).

Exhaustive: \(\dfrac{2}{n+1}=0.0125\Rightarrow n+1=160\Rightarrow \mathbf{n=159}\).

Dichotomous: solve \(\dfrac{4}{2^{n/2}}+0.01\left(1-\dfrac{1}{2^{n/2}}\right)=0.05\):

\[\frac{3.99}{2^{n/2}}=0.04\ \Rightarrow\ 2^{n/2}=99.75\ \Rightarrow\ \frac n2=\log_2 99.75=6.64 \ \Rightarrow\ \mathbf{n=14}\ (\text{7 pairs})\]

Interval halving: \(\left(\tfrac12\right)^{(n-1)/2}=0.0125\Rightarrow \dfrac{n-1}{2}=\log_2 80=6.32\Rightarrow n-1=12.64\Rightarrow \mathbf{n=15}\).

Fibonacci (Lesson 39): \(\dfrac{1}{F_n}\le0.0125\Rightarrow F_n\ge80\), and \(F_{10}=89\ge80\), so \(\mathbf{n=10}\).

Golden section (Lesson 40): \(0.618^{\,n-1}\le0.0125\Rightarrow (n-1)\ge\dfrac{\ln 0.0125}{\ln0.618}=9.10 \Rightarrow \mathbf{n=11}\).

Method Evaluations Relative to exhaustive
Exhaustive 159 \(1.00\times\)
Interval halving 15 \(10.6\times\) better
Dichotomous (\(\delta=0.01\)) 14 \(11.4\times\) better
Golden section 11 \(\mathbf{14.5\times}\) better
Fibonacci 10 \(\mathbf{15.9\times}\) better — optimal

Interpretation.

  • Sequential beats parallel by an order of magnitude. Exhaustive search wastes every evaluation on a fixed grid decided in advance; the others use each result to decide where to look next.
  • Dichotomous and interval halving are close, but dichotomous carries the \(\delta\) floor: demand an accuracy of \(0.005\) and it becomes impossible at \(\delta=0.01\), while interval halving simply needs two more evaluations.
  • Fibonacci is provably optimal among methods using a fixed number of evaluations, and beats golden section here by exactly one evaluation. Golden section pays that one evaluation for the freedom of not having to commit to \(n\) in advance. Lessons 39 and 40 derive both.
  • All the same, exhaustive search retains its place as a first pass on an unknown function, because it is the only one that does not silently assume unimodality.

38.6 Practice Problems

  1. Bracket the minimum of \(f(x)=x^{2}-8x+20\) starting at \(x_0=0\) with \(s=1\), doubling. (Answer: \(x=0,1,3,7\) with \(f=20,13,5,13\) — bracket \([1,7]\))
  2. Perform two stages of interval halving on \(f(x)=(x-2)^{2}+3\) over \([0,6]\). (Answer: stage 1 has \(f(1.5)=3.25<f(3)=4\), so the interval becomes \([0,3]\); stage 2 has \(f(2.25)=3.0625<f(1.5)=3.25\), giving \([1.5,3.0]\))
  3. How many evaluations does dichotomous search with \(\delta=0.02\) need to reduce \([0,10]\) to \(0.1\)? (Answer: \(2^{n/2}=124.75\), \(n/2=6.96\), so \(n=14\))
  4. Show that interval halving with \(n\) evaluations always leaves \(L_0(1/2)^{(n-1)/2}\), and explain why \(n\) must be odd.
  5. Why is exhaustive search the only method in this lesson that does not require unimodality? Give a function on which the other three would fail.

38.7 Summary

  • Every multivariable method reduces to repeated line searches, so one-dimensional methods are the workhorse of non-linear optimisation.
  • Bracket first, refine second. Unrestricted search with a doubling step finds a bracket in \(O(\log)\) evaluations; the bracket is what licenses the unimodality assumption.
  • Exhaustive: \(L_n/L_0=\dfrac{2}{n+1}\) — linear, wasteful, but assumption-free and parallelisable.
  • Dichotomous: \(L_n=\dfrac{L_0}{2^{n/2}}+\delta\!\left(1-\dfrac{1}{2^{n/2}}\right)\) — exponential, but cannot beat \(\delta\), and near the optimum its comparisons rest on tiny differences.
  • Interval halving: \(L_n/L_0=\left(\dfrac12\right)^{(n-1)/2}\) — \(3\) evaluations for the first stage and \(2\) thereafter, because the midpoint is reused.
  • Reuse of evaluations is the whole game. It is why interval halving beats dichotomous search, and Lessons 39–40 push the idea to its optimum.
  • To reduce \([1,5]\) to \(0.05\): exhaustive needs \(159\) evaluations, interval halving \(15\), Fibonacci only \(10\) and golden section \(11\).

Next lesson: L39 — The Fibonacci search method, provably the optimal elimination method.

Practise now: unit4-nlp-search-lab.html → Line Search Lab: pick a function and an interval, run all four methods side by side, and watch the intervals shrink at their different rates.