The dichotomous algorithm in optimization: Dividing to find the minimum

Image by Thomas Wolter taken from Unsplash

The Dichotomous Method (or Dichotomous Search) is one of the most popular direct sequential algorithms in one-dimensional numerical optimization. Unlike Uniform Search, which evaluates all points simultaneously along a grid, the dichotomous method leverages the information obtained at each step to approximately halve the interval of uncertainty in every iteration, guaranteeing faster convergence without calculating derivatives.

In the mid-20th century, with the systematization of operations research by authors like Douglass J. Wilde (1964) (Wilde, 1964), the dichotomous method established itself as the perfect conceptual bridge between blind grid exploration and sequentially optimal algorithms such as Golden Section Search.

The dichotomous algorithm

The goal of the algorithm is to minimize a continuous and unimodal function $f(x)$ within an initial interval $[a, b]$.

Instead of evaluating a single point at the center of the interval $m = \frac{a + b}{2}$ (which would provide no information about the slope of the curve), the method evaluates an extremely close pair of points separated by a small distance $2\delta$ ($\delta > 0$):

1. Midpoint calculation: The center of the current interval $[a_k, b_k]$ is determined: \(m_k = \frac{a_k + b_k}{2}\)

2. Generation of the test pair: Two points symmetric to the midpoint are defined using a small scalar tolerance $\delta > 0$: \(x_1 = m_k - \delta \quad \text{and} \quad x_2 = m_k + \delta\)

3. Function evaluation: The values $f(x_1)$ and $f(x_2)$ are calculated.

4. Interval reduction rule:

   • If $f(x_1) < f(x_2)$, unimodality guarantees that the minimum cannot lie in $[x_2, b_k]$. That half is discarded, and the new interval becomes $[a_{k+1}, b_{k+1}] = [a_k, x_2]$.
   • If $f(x_1) > f(x_2)$, the minimum is not in $[a_k, x_1]$. That region is discarded, and the new interval becomes $[a_{k+1}, b_{k+1}] = [x_1, b_k]$.

The new interval length after each iteration is reduced to $L_{k+1} = \frac{b_k - a_k}{2} + \delta$. That is, the interval is not exactly halved: the lengths decrease geometrically towards a limit width of $2\delta$. For this reason, the stopping tolerance $\varepsilon$ must satisfy $\varepsilon > 2\delta$; otherwise, the loop would never terminate.

Pseudocode

Below is the structured algorithmic formulation:

\begin{algorithm}
\caption{One-Dimensional Dichotomous Search}
\begin{algorithmic}
\PROCEDURE{DichotomousSearch}{$$f, a, b, delta, epsilon$$}
    \STATE $$ak = a$$
    \STATE $$bk = b$$
    \WHILE{$$(bk - ak) > epsilon$$}
        \STATE $$m = (ak + bk) / 2$$
        \STATE $$x1 = m - delta$$
        \STATE $$x2 = m + delta$$
        \IF{$$f(x1) < f(x2)$$}
            \STATE $$bk = x2$$
        \ELSE
            \STATE $$ak = x1$$
        \ENDIF
    \ENDWHILE
    \STATE $$xopt = (ak + bk) / 2$$
    \RETURN $$xopt, f(xopt), [ak, bk]$$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Numerical example

To directly compare efficiency with the Uniform Search post, let us consider the non-linear function:

over the interval $[a, b] = [0, 3]$. We will set a perturbation margin $\delta = 0.1$.

Analytically, the exact minimum is located at $x^* = 1.6$ with $f(1.6) = 0.44$.

The iterations using the dichotomous method for this example are:

Iteration 1:

• Initial interval: $[a_0, b_0] = [0, 3]$ (Length $L_0 = 3.0$).
• Midpoint: $m_0 = (0 + 3)/2 = 1.5$.
• Test points:
  • $x_1 = 1.5 - 0.1 = 1.4 \implies f(1.4) = 0.48$
  • $x_2 = 1.5 + 0.1 = 1.6 \implies f(1.6) = 0.44$
• Decision: Since $f(1.4) > f(1.6)$, we discard the region $[0, 1.4]$.
• New interval: $[a_1, b_1] = [1.4, 3.0]$ (Length $L_1 = 1.6$).

Iteration 2:

• Current interval: $[a_1, b_1] = [1.4, 3.0]$.
• Midpoint: $m_1 = (1.4 + 3.0)/2 = 2.2$.
• Test points:
  • $x_1 = 2.2 - 0.1 = 2.1 \implies f(2.1) = 0.69$
  • $x_2 = 2.2 + 0.1 = 2.3 \implies f(2.3) = 0.93$
• Decision: Since $f(2.1) < f(2.3)$, we discard the region $[2.3, 3.0]$.
• New interval: $[a_2, b_2] = [1.4, 2.3]$ (Length $L_2 = 0.9$).

Iteration 3:

• Current interval: $[a_2, b_2] = [1.4, 2.3]$.
• Midpoint: $m_2 = (1.4 + 2.3)/2 = 1.85$.
• Test points:
  • $x_1 = 1.85 - 0.1 = 1.75 \implies f(1.75) = 0.4625$
  • $x_2 = 1.85 + 0.1 = 1.95 \implies f(1.95) = 0.5625$
• Decision: Since $f(1.75) < f(1.95)$, we discard the region $[1.95, 2.3]$.
• New interval: $[a_3, b_3] = [1.4, 1.95]$ (Length $L_3 = 0.55$).

Result: In just 3 iterations (6 function evaluations, excluding the final evaluation of $f(x_{opt})$ in the pseudocode), the initial interval of length $3.0$ has been reduced to $0.55$, guaranteeing that the optimum $x^* = 1.6$ lies within $[1.4, 1.95]$.

If the Uniform Search method were used, 7 evaluations would be required to achieve a similar reduction to an interval of length $1.0$.

These three iterations are shown graphically in the following figure:

Technical analysis: Dichotomous Search vs. Uniform Search

The fundamental difference between both methods lies in their convergence speed relative to the number of numerical evaluations $N$:

• Uniform Search (Simultaneous): The reduction of the interval is linear, with a ratio $R_N = \frac{2}{N-1}$.

• Dichotomous Method (Sequential): If $k$ iterations are performed ($N = 2k$ evaluations), the final interval length is approximately:

  \[L_k \approx \frac{b - a}{2^k} + 2\delta \left(1 - \frac{1}{2^k}\right)\]

This convergence of the dichotomous method allows achieving very strict precision tolerances (e.g., $\varepsilon = 10^{-4}$, choosing a sufficiently small $\delta$ such as $10^{-5}$) with barely 30 or so function evaluations, whereas Uniform Search would require tens of thousands.

Advantages and Limitations

• Advantages:
  • Extreme efficiency: Drastically reduces the search space in very few evaluations.
  • Derivative-free: It only requires function evaluations. However, the interval guarantee relies on the function being continuous and unimodal.
• Limitations:
  • Sequential nature: Not as easy to massively parallelize as Uniform Search, since each pair of evaluations depends on the previous result.
  • Redundancy: Evaluates 2 points per step (more advanced methods manage to reuse points to require only one evaluation per step after the first iteration).

The Dichotomous Method represents the fundamental bridge between blind grid sampling and advanced sequential methods. By leveraging the information from each step to bisect the interval without calculating derivatives, it demonstrates that the key to algorithmic efficiency lies in intelligently discarding half of the problem at every decision.

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.