Algo: Ternary Search on Unimodal Functions

In engineering design and analysis, you often need to find the optimal value—like the minimum cost or maximum efficiency—of a function without relying on derivatives or complex calculus. When that function is guaranteed to have a single peak or valley, ternary search provides a remarkably efficient, intuitive, and derivative-free method to pinpoint that extremum. This algorithm is a cornerstone for solving optimization problems in fields ranging from signal processing to mechanical design, where evaluating the objective function might be computationally expensive or analytically challenging.

Understanding Unimodal Functions

A unimodal function is a function that has a single extremum—either one maximum or one minimum—within a given interval. To its left and right, the function is strictly monotonic (either always increasing or always decreasing). Formally, for a function $f(x)$ defined on an interval $[l,r]$, if there exists a point $m$ such that:

• For a maximum: $f(x)$ is strictly increasing on $[l,m]$ and strictly decreasing on $[m,r]$.
• For a minimum: $f(x)$ is strictly decreasing on $[l,m]$ and strictly increasing on $[m,r]$.

Think of a unimodal function as a single smooth hill or valley. In engineering, many practical objective functions are unimodal, at least locally. For example, the drag force on a vehicle as a function of its shape parameter might have one clear minimum, or the signal strength from a sensor as a function of orientation might have one clear maximum. Recognizing unimodality is crucial because it allows you to apply efficient search algorithms like ternary search, which would fail on functions with multiple peaks.

The Ternary Search Algorithm: Core Mechanics

Ternary search operates by recursively narrowing down the interval containing the extremum. It does this by evaluating the function at two interior points and comparing their values to discard one-third of the current search space. The process is analogous to finding the highest point on a ridge by checking two spots and ruling out the section that cannot contain the peak.

Here’s the step-by-step procedure for finding a maximum on a continuous interval $[l,r]$:

1. Choose two points, $m1$ and $m2$, that divide the interval into three roughly equal parts. A common choice is $m1=l+(r-l)/3$ and $m2=r-(r-l)/3$.
2. Evaluate the function at these points: $f(m1)$ and $f(m2)$.
3. Compare the values:

• If $f(m1)<f(m2)$ for a maximum, then the maximum cannot lie in the leftmost third $[l,m1]$, because the function is still rising towards $m2$. Update $l=m1$.
• If $f(m1)>f(m2)$ for a maximum, then the maximum cannot lie in the rightmost third $[m2,r]$. Update $r=m2$.
• If $f(m1)=f(m2)$, the maximum lies between $m1$ and $m2$, so you can update both ends: $l=m1$ and $r=m2$.

1. Repeat steps 1-3 until the interval $[l,r]$ is sufficiently small (e.g., its width is below a tolerance $ϵ$).

The key insight is that each iteration eliminates precisely one-third of the current interval, making the search converge quickly. For finding a minimum, simply reverse the comparison logic.

Implementation for Continuous and Discrete Domains

You must adapt the ternary search logic based on whether your domain is continuous (real numbers) or discrete (integers or indices), as this affects termination conditions and point selection.

For Continuous Domains: You work with real numbers and a precision tolerance $ϵ$. The algorithm runs until $(r-l)<ϵ$. The choice of $m1$ and $m2$ is as described above. Here’s a practical implementation snippet in conceptual form:

while (r - l > epsilon):
    m1 = l + (r - l) / 3
    m2 = r - (r - l) / 3
    if f(m1) < f(m2):
        l = m1  # For maximum
    else:
        r = m2
return (l + r) / 2  # Approximate extremum point

Consider an engineering example: finding the optimal angle $\theta$ in $[0,\pi ]$ to maximize the range of a projectile, ignoring air resistance. The range function $R(\theta )=(v^2\sin (2\theta ))/g$ is unimodal (with a maximum at $\pi /4$). Ternary search would efficiently hone in on this angle through successive evaluations.

For Discrete Domains: The domain consists of integer indices, such as when searching for a peak in an array. Here, you cannot divide into perfect thirds, so you choose integer points close to the one-third marks. The search continues until the interval contains only a few elements (typically 2 or 3), which you then check directly.

while (r - l > 2):  # Until interval has 3 or fewer elements
    m1 = l + (r - l) // 3
    m2 = r - (r - l) // 3
    if f(m1) < f(m2):
        l = m1
    else:
        r = m2
# Now check f(x) for remaining x in [l, r] to find exact extremum

A common discrete application is finding the maximum value in a unimodal array, like temperature readings from a sensor over time that first increase to a peak and then decrease.

Analyzing Convergence Rate and Efficiency

The convergence rate of ternary search is logarithmic, similar to binary search but with a different base. Each iteration reduces the search interval to two-thirds of its previous size. Starting with an interval of length $L$, after $k$ iterations, the interval length is $L\times (2/3{)}^k$.

To find the number of iterations required to achieve a tolerance $ϵ$, you solve $L\times (2/3{)}^k<ϵ$. Taking logarithms, you get: $$k>\frac{\log (L/ϵ)}{\log (3/2)}$$

This shows that the number of iterations grows as $O({\log }_{1.5}(L/ϵ))$ or, equivalently, $O(\log (L/ϵ))$. In practice, ternary search requires more iterations than binary search for the same precision because it eliminates only one-third per step versus one-half. However, it is necessary when the comparison logic relies on function values at two points rather than a simple midpoint comparison. The efficiency makes it highly suitable for optimization where function evaluations are costly but manageable, as it minimizes the number of such evaluations.

Engineering Applications and Optimization Problems

Ternary search is a powerful tool for optimization problems where the objective function is known or observed to be unimodal. In engineering, this often arises in parameter tuning, design optimization, and resource allocation.

• Mechanical Design: Finding the optimal dimension of a beam to minimize deflection under load, where the deflection function versus dimension is unimodal within practical bounds.
• Electrical Engineering: Tuning a circuit component value (e.g., a resistor in a filter) to maximize output signal-to-noise ratio, which often varies unimodally with the parameter.
• Control Systems: Adjusting a gain parameter to minimize the settling time of a system response, where the relationship is typically unimodal.
• Algorithmic Optimization: In computer-aided engineering, ternary search can be used as a subroutine in larger algorithms, such as line search methods in multivariable optimization, where the search direction is unimodal.

The strength of ternary search lies in its simplicity and robustness when unimodality holds. It is particularly useful when the function is not easily differentiable, is defined by simulations or experiments, or when you need a guaranteed convergence without gradient information.

Common Pitfalls

1. Applying to Non-Unimodal Functions: The most critical error is using ternary search on a function that is not unimodal. If the function has multiple local extrema, the algorithm can converge to a local optimum or fail entirely. Correction: Always verify unimodality theoretically or through preliminary analysis. In practice, if you suspect multimodality, consider using global optimization methods or restricting the search to a known unimodal region.

1. Incorrect Point Selection for Discrete Domains: In discrete implementations, improperly choosing $m1$ and $m2$ can lead to infinite loops or missed extrema. For example, if $m1$ and $m2$ are not distinct or not properly bounded, the interval might not shrink. Correction: Use integer arithmetic carefully, ensuring $m1<m2$. A robust approach is to set $m1=l+(r-l)//3$ and $m2=r-(r-l)//3$, and handle the case when the interval is small by direct comparison.

1. Poor Handling of Equality in Comparisons: When $f(m1)=f(m2)$, if you arbitrarily choose to discard the left or right third, you might eliminate the region containing the extremum. Correction: In the equality case, safely discard both outer thirds by setting $l=m1$ and $r=m2$, as the extremum must lie between them. This preserves the unimodal property.

1. Ignoring Precision in Continuous Search: Using a fixed number of iterations instead of a tolerance-based loop can result in insufficient accuracy or wasted computation. Correction: Base termination on the interval width relative to your required precision $ϵ$. Also, be mindful of floating-point errors when comparing function values; use a small tolerance for equality checks if necessary.

Summary

• Ternary search is an efficient, iterative algorithm for finding the maximum or minimum of a unimodal function by evaluating the function at two interior points and eliminating one-third of the search interval each step.
• You must adapt the implementation for continuous domains (using a precision tolerance) and discrete domains (using integer indices and direct checks for small intervals).
• The convergence rate is logarithmic, with the interval reducing by a factor of $2/3$ per iteration, requiring $O(\log (L/ϵ))$ evaluations to reach a tolerance $ϵ$.
• Its primary engineering application is in optimization problems with unimodal objective functions, such as parameter tuning in design and control systems, where derivative information is unavailable or expensive to obtain.
• Avoid common mistakes by ensuring function unimodality, carefully selecting points in discrete cases, correctly handling equal function values, and managing precision in continuous searches.