Unimodal Optimization

Why Unimodal Optimization Matters

Suppose a deterministic simulation reports the cost of choosing one scalar parameter: a delay, an operating point, or a position along a line. You can evaluate the cost, but derivatives are unavailable. If cost falls toward one valley and rises afterward, you can minimize it by repeatedly comparing two interior points and discarding a region that cannot improve the answer.

Ternary search places the probes at one third and two thirds of the current interval. Golden-section search chooses a different ratio so that, after a reduction, one old point and its function value can be reused. This matters when an objective call means running an expensive simulation rather than evaluating a small formula.

Both methods optimize a single real variable on a supplied bounded interval. They need a suitable unimodal shape and reliable comparisons; they do not discover all minima of an arbitrary landscape. The implementations below expose the interval, cached probes, best observed value, evaluation count, and stopping reason. The worked quadratic has a known analytic solution, allowing the search to be checked independently.

Core Concepts and Terminology

We minimize a deterministic function $f:[a,b]\to\mathbb{R}$. For the guarantees in this lesson, assume continuity and a connected minimum set $[u,v]$: the function is strictly decreasing before $u$, constant on $[u,v]$, and strictly increasing after $v$. The minimum set may be a single point or touch a domain endpoint. A function flat only at its minimum is allowed, including a constant function; an arbitrary flat region above the minimum is not covered by our equality rules.

The current closed interval is $[l,r]$, with width $W=r-l$. It must retain at least one minimizer; retaining every point of a minimum plateau is unnecessary. For probes $l\lt x_1\lt x_2\lt r$, if $f(x_1)\lt f(x_2)$, at least one minimizer lies in $[l,x_2]$. If $f(x_1)\gt f(x_2)$, retain $[x_1,r]$. Equality permits retaining $[x_1,x_2]$ under the strict-sided shape assumption; golden-section search instead keeps $[l,x_2]$ to preserve its reuse geometry.

The location tolerance $\varepsilon\gt0$ applies to width: stop when $r-l\le\varepsilon$. The midpoint estimate is $\widehat{x}=l+(r-l)/2$. If the retained interval really contains a minimizer $x_{\min}$, then

$$\lvert\widehat{x}-x_{\min}\rvert\le\frac{r-l}{2}\le\frac{\varepsilon}{2}.$$

This is an interval-based location statement, conditional on the shape and comparisons being valid. It does not imply a particular error in objective value. The diagram shows the worked function $f(x)=(x-2.5)^2+1$, initially on $[0,9]$, whose exact minimum is $f(2.5)=1$.

How Unimodal Optimization Works, Step by Step

1. Validate the request. Require ordered finite endpoints, a positive finite absolute tolerance, a supported method, and valid iteration/evaluation caps. The demonstration limits endpoint magnitudes so subtraction and midpoint calculation cannot overflow.
2. Check stopping conditions before spending evaluations. If width is already at most tolerance, return CONVERGED. Otherwise, if the completed-reduction cap is reached, return ITER_LIMIT. A singleton interval therefore needs no objective calls.
3. Place two distinct interior probes. Ternary search uses $x_1=l+W/3$ and $x_2=r-W/3$. Golden-section search initializes $x_1=r-\rho W$ and $x_2=l+\rho W$, with

$$\rho=\frac{\sqrt{5}-1}{2},\qquad 1-\rho=\rho^2.$$

If rounding prevents $l\lt x_1\lt x_2\lt r$, return STALLED instead of looping without useful progress. 4. Obtain only the needed values. Ternary search evaluates both probes. Golden-section initially evaluates both and subsequently evaluates only the new probe; the reused coordinate and its cached value travel together. Refuse a call that would exceed the evaluation cap. Count a call that returns NaN or infinity, then return NONFINITE. 5. Choose the retained interval. Ternary search keeps $[l,x_2]$ when $f_1\lt f_2$, $[x_1,r]$ when $f_1\gt f_2$, and $[x_1,x_2]$ on equality. Golden-section keeps $[l,x_2]$ when $f_1\le f_2$, otherwise $[x_1,r]$. Check that represented width actually decreases before committing the change. 6. Record a completed reduction. The history contains old endpoints, both probes and values, new endpoints, the best valid sample seen so far, and the cumulative objective-call count. If either required value is unavailable, do not commit a reduction; an earlier valid sample can still update the best observed value. 7. Prepare golden reuse and repeat. If the left interval is retained, old $x_1,f_1$ become new $x_2,f_2$; compute a new left probe. If the right interval is retained, old $x_2,f_2$ become new $x_1,f_1$; compute a new right probe. Evaluate that new point only if another reduction is needed.

Why does the ratio work? After retaining $[l,x_2]$, its width is $\rho W$. The old left probe is at $l+(1-\rho)W=l+\rho^2W$, exactly the new right probe's ideal position $l+\rho(\rho W)$. This identity makes one value reusable. In floating point, preserve the old coordinate itself rather than recomputing a slightly different point and attaching the old value to it.

The best-observed score is updated only on a strict improvement, so equal values keep the earliest sample. It is nonincreasing for a minimization run. The midpoint and its unknown objective value need not improve monotonically. If you need $f(\widehat{x})$, make and account for a separate objective call.

flowchart TD
    A["Validate interval, tolerance, method, and caps"] --> B{"Width at most tolerance?"}
    B -->|Yes| C["Return CONVERGED"]
    B -->|No| D{"Reduction cap reached?"}
    D -->|Yes| E["Return ITER_LIMIT"]
    D -->|No| F["Place ternary probes or prepare golden cached pair"]
    F --> G{"Two distinct interior probes?"}
    G -->|No| H["Return STALLED"]
    G -->|Yes| I{"Needed evaluation fits budget?"}
    I -->|No| J["Return EVAL_LIMIT with last committed interval"]
    I -->|Yes| K["Call objective; count call"]
    K --> L{"Finite value?"}
    L -->|No| M["Return NONFINITE with last committed interval"]
    L -->|Yes| N["Update best observed sample"]
    N --> O{"More needed values?"}
    O -->|Yes| I
    O -->|No| P["Compare values and choose interval"]
    P --> Q{"Represented width decreases?"}
    Q -->|No| H
    Q -->|Yes| R["Commit reduction and append trace row"]
    R --> S["For golden: preserve reused point and value"]
    S --> B

Worked Example with a Full Trace

Minimize $f(x)=(x-2.5)^2+1$ on $[0,9]$, with width tolerance $\varepsilon=0.75$, iteration cap $64$, and evaluation cap $128$. The true minimizer is $x=2.5$ and its objective value is $1$. There is no randomness or seed: the starting interval and all arithmetic determine the trace.

The tables below record every completed reduction. A probe cell is $(x,f(x))$; endpoint and value displays are rounded to nine decimal places, while comparisons use full binary64 precision. The last column records the best sampled coordinate and value, which can differ from the final midpoint.

Ternary search. The first probes are $3$ and $6$, with values $1.25$ and $13.25$, so the interval becomes $[0,6]$. The second probes are $2$ and $4$, with values $1.25$ and $3.25$; keep $[0,4]$, retaining the earlier best sample at $3$ on the tie between sampled objective values. Both probes in each subsequent row are fresh calls.

Golden-section search. The first probes are approximately $3.437694101$ and $5.562305899$; their values are $1.879270228$ and $10.377717418$, so keep $[0,5.562305899]$. The old left probe becomes the next right probe. Row $2$ evaluates only the new left point $2.124611797$, and the same one-value reuse continues.

Ternary search completes $7$ reductions and $14$ evaluations, ending with interval $[2.189300412,2.716049383]$, width about $0.526748971$, and midpoint $2.452674897$. Its best observed sample is approximately $(2.518518519,1.000342936)$.

Golden-section completes $6$ reductions and $7$ evaluations, ending with interval $[2.124611797,2.626164608]$, width about $0.501552810$, and midpoint $2.375388203$. Its best observed sample is approximately $(2.434588481,1.004278667)$. Both intervals contain $2.5$ and satisfy the same width target. Golden uses fewer calls, while ternary happens to sample a lower objective value in this particular run; those are different comparisons.

Implementation in Python, C++, and Java

The three complete programs implement both methods with identical control flow and arithmetic order. The callback takes one real coordinate and returns one scalar objective value. The example objective is a quadratic; additional fixtures cover an endpoint minimum, a flat minimum set, resource limits, adjacent doubles, a non-finite result, and an interval that is already narrow.

Contract. Endpoints and tolerance must be finite; $-10^6\le l\le r\le10^6$ and $\varepsilon\gt0$. The method is exactly ternary or golden. The maximum number of completed reductions is an integer in $[0,256]$, and the evaluation cap is an integer in $[0,2000]$. These endpoint limits ensure safe width and midpoint arithmetic in this demonstration. Inputs outside those numeric ranges are rejected. The callback must be callable and deterministic for caching and unimodal-search guarantees; ordinary callback exceptions propagate to the caller. NaN or infinite returned values are handled with NONFINITE.

Result contains a status, final retained endpoints, midpoint, a has_best flag, best observed coordinate/value, completed-reduction count, attempted objective-call count, and the full history. The best fields are dummy zeroes when has_best is false. CONVERGED means only the represented width met tolerance; ITER_LIMIT, EVAL_LIMIT, STALLED, and NONFINITE report distinct incomplete outcomes. A failure preserves the last committed interval, but a valid call made before it can improve the best sample. The programs do not evaluate endpoints or the final midpoint automatically.

Stopping precedence is deliberate: width, then iteration cap, then representable interior probes, then evaluation availability and finiteness. An evaluation budget of zero therefore does not prevent returning CONVERGED for an already narrow interval. A call returning a non-finite value counts against the budget; a refused call does not. No interval update occurs until both comparison values are valid. A cache entry always consists of the exact sampled coordinate together with its value.

For $k\ge1$ fully completed reductions with valid finite evaluations and no partial failed comparison, ternary uses $2k$ objective calls and golden uses $k+1$. For $k=0$ caused by an already narrow interval, both use zero calls. Other zero- or partial-reduction outcomes can have calls already spent; for example, initialization can stop after one valid call or one valid and one non-finite call.

Each printed iteration reports the new interval and the best valid objective value observed so far. It does not label that value as $f(\text{midpoint})$. The returned trace also stores both probes and both comparison values. Six-decimal output is for readability; branches use the full values, so visually equal rounded prints need not imply an equality branch.

Use Python 3, C++14 or newer, and Java 17 or newer; save Java as Main.java. For reproducible C++ floating-point histories, compile with g++ -std=c++14 -O2 -ffp-contract=off main.cpp -o main and avoid unsafe floating-point transformations. The hard-coded binary64 golden fraction and explicit operation order produce identical sample output in all three languages.

import math
from dataclasses import dataclass

RHO = 0.6180339887498948482


@dataclass
class Row:
    old_left: float
    old_right: float
    x1: float
    x2: float
    f1: float
    f2: float
    left: float
    right: float
    best_x: float
    best_f: float
    evaluations: int


@dataclass
class Result:
    status: str
    left: float
    right: float
    midpoint: float
    has_best: bool
    best_x: float
    best_f: float
    iterations: int
    evaluations: int
    history: list


class Stop(Exception):
    pass


def minimize(f, left, right, tolerance, method="golden", max_iterations=256, max_evaluations=2000):
    if (method not in ("ternary", "golden") or
            not all(math.isfinite(x) for x in (left, right, tolerance)) or
            abs(left) > 1_000_000 or abs(right) > 1_000_000 or left > right or tolerance <= 0 or
            type(max_iterations) is not int or not 0 <= max_iterations <= 256 or
            type(max_evaluations) is not int or not 0 <= max_evaluations <= 2000):
        raise ValueError("invalid search parameters")
    left, right, tolerance = float(left), float(right), float(tolerance)
    evaluations, has_best, best_x, best_f = 0, False, 0.0, 0.0
    history = []

    def finish(status):
        return Result(status, left, right, left + 0.5 * (right - left),
                      has_best, best_x, best_f, len(history), evaluations, history.copy())

    def evaluate(x):
        nonlocal evaluations, has_best, best_x, best_f
        if evaluations >= max_evaluations:
            raise Stop("EVAL_LIMIT")
        evaluations += 1
        value = float(f(x))
        if not math.isfinite(value):
            raise Stop("NONFINITE")
        if not has_best or value < best_f:
            has_best, best_x, best_f = True, x, value
        return value

    x1 = x2 = f1 = f2 = 0.0
    need = 0  # Golden: 0 = initialize both, 1/2 = evaluate only that new probe.
    while True:
        width = right - left
        if width <= tolerance:
            return finish("CONVERGED")
        if len(history) >= max_iterations:
            return finish("ITER_LIMIT")
        if method == "ternary":
            x1, x2 = left + width / 3.0, right - width / 3.0
        elif need == 0:
            x1, x2 = right - RHO * width, left + RHO * width
        if not left < x1 < x2 < right:
            return finish("STALLED")
        try:
            if method == "ternary" or need in (0, 1):
                f1 = evaluate(x1)
            if method == "ternary" or need in (0, 2):
                f2 = evaluate(x2)
        except Stop as stopped:
            return finish(str(stopped))
        old_left, old_right = left, right
        if method == "ternary":
            if f1 < f2:
                new_left, new_right = left, x2
            elif f1 > f2:
                new_left, new_right = x1, right
            else:
                new_left, new_right = x1, x2
        elif f1 <= f2:
            new_left, new_right = left, x2
        else:
            new_left, new_right = x1, right
        if not new_right - new_left < width:
            return finish("STALLED")
        left, right = new_left, new_right  # Commit only after both values are valid.
        history.append(Row(old_left, old_right, x1, x2, f1, f2, left, right, best_x, best_f, evaluations))
        if method == "golden":
            if f1 <= f2:
                x2, f2 = x1, f1
                x1 = right - RHO * (right - left)
                need = 1
            else:
                x1, f1 = x2, f2
                x2 = left + RHO * (right - left)
                need = 2


def fixed(x):
    return f"{0.0 if abs(x) < 0.0000005 else x:.6f}"


def show(name, f, left, right, tolerance, method, iterations=64, evaluations=128):
    result = minimize(f, left, right, tolerance, method, iterations, evaluations)
    print(f"{name}: {result.status}, iterations={result.iterations}, evaluations={result.evaluations}")
    print(f"midpoint={fixed(result.midpoint)}, width={result.right-result.left:.6e}, best=" +
          (f"({fixed(result.best_x)},{fixed(result.best_f)})" if result.has_best else "NONE"))
    for i, row in enumerate(result.history, 1):
        print(f"i={i}, interval=[{fixed(row.left)},{fixed(row.right)}], " +
              f"best_x={fixed(row.best_x)}, best_f={fixed(row.best_f)}, evaluations={row.evaluations}")


def quadratic(x):
    z = x - 2.5
    return z * z + 1.0


def main():
    show("ternary", quadratic, 0.0, 9.0, 0.75, "ternary")
    show("golden", quadratic, 0.0, 9.0, 0.75, "golden")
    show("endpoint", lambda x: x, 0.0, 5.0, 0.5, "golden")
    show("minimum plateau", lambda x: max(0.0, abs(x - 2.0) - 0.5), 0.0, 6.0, 0.5, "ternary")
    show("evaluation cap", quadratic, 0.0, 9.0, 1e-6, "golden", evaluations=3)
    show("iteration cap", quadratic, 0.0, 9.0, 1e-6, "ternary", iterations=2)
    show("adjacent doubles", quadratic, 1.0, math.nextafter(1.0, math.inf), math.ulp(0.0), "ternary")
    show("nonfinite", lambda x: quadratic(x) if x < 5.0 else math.inf, 0.0, 9.0, 0.75, "golden")
    show("already narrow", quadratic, 1.0, 1.0, 0.1, "golden")
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <locale>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;
const double RHO=0.6180339887498948482;
struct Stop { string status; };
struct Row {
    double old_left,old_right,x1,x2,f1,f2,left,right,best_x,best_f;
    int evaluations;
};
struct Result {
    string status;
    double left,right,midpoint;
    bool has_best;
    double best_x,best_f;
    int iterations,evaluations;
    vector<Row> history;
};
class Runner {
public:
    function<double(double)> objective;
    double left,right,tolerance;
    string method;
    int max_iterations,max_evaluations,evaluations=0;
    bool has_best=false;
    double best_x=0,best_f=0;
    vector<Row> history;
    Runner(function<double(double)> f,double l,double r,double tol,string meth,int it,int ev)
        :objective(f),left(l),right(r),tolerance(tol),method(meth),max_iterations(it),max_evaluations(ev) {
        if(!objective || (method!="ternary" && method!="golden") || !isfinite(left) || !isfinite(right) || !isfinite(tolerance) ||
           abs(left)>1000000 || abs(right)>1000000 || left>right || tolerance<=0 ||
           max_iterations<0 || max_iterations>256 || max_evaluations<0 || max_evaluations>2000)
            throw invalid_argument("invalid search parameters");
    }
    Result finish(const string& status) const {
        return {status,left,right,left+0.5*(right-left),has_best,best_x,best_f,static_cast<int>(history.size()),evaluations,history};
    }
    double evaluate(double x) {
        if(evaluations>=max_evaluations) throw Stop{"EVAL_LIMIT"};
        ++evaluations;
        double value=objective(x);
        if(!isfinite(value)) throw Stop{"NONFINITE"};
        if(!has_best || value<best_f) { has_best=true; best_x=x; best_f=value; }
        return value;
    }
    Result run() {
        double x1=0,x2=0,f1=0,f2=0;
        int need=0; // Golden: initialize both, or evaluate only new probe 1/2.
        while(true) {
            double width=right-left;
            if(width<=tolerance) return finish("CONVERGED");
            if(static_cast<int>(history.size())>=max_iterations) return finish("ITER_LIMIT");
            if(method=="ternary") { x1=left+width/3.0; x2=right-width/3.0; }
            else if(need==0) { x1=right-RHO*width; x2=left+RHO*width; }
            if(!(left<x1 && x1<x2 && x2<right)) return finish("STALLED");
            try {
                if(method=="ternary" || need==0 || need==1) f1=evaluate(x1);
                if(method=="ternary" || need==0 || need==2) f2=evaluate(x2);
            } catch(const Stop& stopped) { return finish(stopped.status); }
            double old_left=left,old_right=right,new_left,new_right;
            if(method=="ternary") {
                if(f1<f2) { new_left=left; new_right=x2; }
                else if(f1>f2) { new_left=x1; new_right=right; }
                else { new_left=x1; new_right=x2; }
            } else if(f1<=f2) { new_left=left; new_right=x2; }
            else { new_left=x1; new_right=right; }
            if(!(new_right-new_left<width)) return finish("STALLED");
            left=new_left; right=new_right;
            history.push_back({old_left,old_right,x1,x2,f1,f2,left,right,best_x,best_f,evaluations});
            if(method=="golden") {
                if(f1<=f2) { x2=x1; f2=f1; x1=right-RHO*(right-left); need=1; }
                else { x1=x2; f1=f2; x2=left+RHO*(right-left); need=2; }
            }
        }
    }
};
Result minimize(function<double(double)> f,double left,double right,double tolerance,const string& method="golden",int iterations=256,int evaluations=2000) {
    Runner runner(f,left,right,tolerance,method,iterations,evaluations);
    return runner.run();
}
string fixed6(double x) {
    ostringstream out; out.imbue(locale::classic());
    out<<fixed<<setprecision(6)<<(abs(x)<0.0000005 ? 0.0 : x); return out.str();
}
string scientific6(double x) {
    ostringstream out; out.imbue(locale::classic()); out<<scientific<<setprecision(6)<<x; return out.str();
}
void show(const string& name,function<double(double)> f,double left,double right,double tolerance,const string& method,int iterations=64,int evaluations=128) {
    Result r=minimize(f,left,right,tolerance,method,iterations,evaluations);
    cout<<name<<": "<<r.status<<", iterations="<<r.iterations<<", evaluations="<<r.evaluations<<'\n';
    cout<<"midpoint="<<fixed6(r.midpoint)<<", width="<<scientific6(r.right-r.left)<<", best=";
    if(r.has_best) cout<<'('<<fixed6(r.best_x)<<','<<fixed6(r.best_f)<<')'; else cout<<"NONE";
    cout<<'\n';
    for(size_t i=0;i<r.history.size();++i) {
        const Row& row=r.history[i];
        cout<<"i="<<i+1<<", interval=["<<fixed6(row.left)<<','<<fixed6(row.right)<<"], best_x="<<fixed6(row.best_x)
            <<", best_f="<<fixed6(row.best_f)<<", evaluations="<<row.evaluations<<'\n';
    }
}
double quadratic(double x) { double z=x-2.5; return z*z+1.0; }
int main() {
    show("ternary",quadratic,0.0,9.0,0.75,"ternary");
    show("golden",quadratic,0.0,9.0,0.75,"golden");
    show("endpoint",[](double x){return x;},0.0,5.0,0.5,"golden");
    show("minimum plateau",[](double x){return fmax(0.0,abs(x-2.0)-0.5);},0.0,6.0,0.5,"ternary");
    show("evaluation cap",quadratic,0.0,9.0,1e-6,"golden",64,3);
    show("iteration cap",quadratic,0.0,9.0,1e-6,"ternary",2,128);
    show("adjacent doubles",quadratic,1.0,nextafter(1.0,numeric_limits<double>::infinity()),numeric_limits<double>::denorm_min(),"ternary");
    show("nonfinite",[](double x){return x<5.0 ? quadratic(x) : numeric_limits<double>::infinity();},0.0,9.0,0.75,"golden");
    show("already narrow",quadratic,1.0,1.0,0.1,"golden");
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.function.DoubleUnaryOperator;

public class Main {
    static final double RHO=0.6180339887498948482;
    static final class Stop extends RuntimeException {
        private static final long serialVersionUID=1L;
        Stop(String status) { super(status); }
    }
    static final class Row {
        final double oldLeft,oldRight,x1,x2,f1,f2,left,right,bestX,bestF;
        final int evaluations;
        Row(double ol,double or,double x1,double x2,double f1,double f2,double l,double r,double bx,double bf,int ev) {
            oldLeft=ol; oldRight=or; this.x1=x1; this.x2=x2; this.f1=f1; this.f2=f2; left=l; right=r; bestX=bx; bestF=bf; evaluations=ev;
        }
    }
    static final class Result {
        final String status; final double left,right,midpoint,bestX,bestF;
        final boolean hasBest; final int iterations,evaluations; final List<Row> history;
        Result(String status,double l,double r,boolean hb,double bx,double bf,int ev,List<Row> hist) {
            this.status=status; left=l; right=r; midpoint=l+0.5*(r-l); hasBest=hb; bestX=bx; bestF=bf;
            iterations=hist.size(); evaluations=ev; history=new ArrayList<>(hist);
        }
    }
    static final class Runner {
        final DoubleUnaryOperator objective;
        double left,right; final double tolerance; final String method;
        final int maxIterations,maxEvaluations; int evaluations=0;
        boolean hasBest=false; double bestX=0,bestF=0;
        final List<Row> history=new ArrayList<>();
        Runner(DoubleUnaryOperator f,double l,double r,double tol,String method,int it,int ev) {
            if(f==null || (!"ternary".equals(method) && !"golden".equals(method)) ||
               !Double.isFinite(l) || !Double.isFinite(r) || !Double.isFinite(tol) ||
               Math.abs(l)>1_000_000 || Math.abs(r)>1_000_000 || l>r || tol<=0 || it<0 || it>256 || ev<0 || ev>2000)
                throw new IllegalArgumentException("invalid search parameters");
            objective=f; left=l; right=r; tolerance=tol; this.method=method; maxIterations=it; maxEvaluations=ev;
        }
        Result finish(String status) { return new Result(status,left,right,hasBest,bestX,bestF,evaluations,history); }
        double evaluate(double x) {
            if(evaluations>=maxEvaluations) throw new Stop("EVAL_LIMIT");
            ++evaluations;
            double value=objective.applyAsDouble(x);
            if(!Double.isFinite(value)) throw new Stop("NONFINITE");
            if(!hasBest || value<bestF) { hasBest=true; bestX=x; bestF=value; }
            return value;
        }
        Result run() {
            double x1=0,x2=0,f1=0,f2=0; int need=0;
            while(true) {
                double width=right-left;
                if(width<=tolerance) return finish("CONVERGED");
                if(history.size()>=maxIterations) return finish("ITER_LIMIT");
                if(method.equals("ternary")) { x1=left+width/3.0; x2=right-width/3.0; }
                else if(need==0) { x1=right-RHO*width; x2=left+RHO*width; }
                if(!(left<x1 && x1<x2 && x2<right)) return finish("STALLED");
                try {
                    if(method.equals("ternary") || need==0 || need==1) f1=evaluate(x1);
                    if(method.equals("ternary") || need==0 || need==2) f2=evaluate(x2);
                } catch(Stop stopped) { return finish(stopped.getMessage()); }
                double oldLeft=left,oldRight=right,newLeft,newRight;
                if(method.equals("ternary")) {
                    if(f1<f2) { newLeft=left; newRight=x2; }
                    else if(f1>f2) { newLeft=x1; newRight=right; }
                    else { newLeft=x1; newRight=x2; }
                } else if(f1<=f2) { newLeft=left; newRight=x2; }
                else { newLeft=x1; newRight=right; }
                if(!(newRight-newLeft<width)) return finish("STALLED");
                left=newLeft; right=newRight;
                history.add(new Row(oldLeft,oldRight,x1,x2,f1,f2,left,right,bestX,bestF,evaluations));
                if(method.equals("golden")) {
                    if(f1<=f2) { x2=x1; f2=f1; x1=right-RHO*(right-left); need=1; }
                    else { x1=x2; f1=f2; x2=left+RHO*(right-left); need=2; }
                }
            }
        }
    }
    static Result minimize(DoubleUnaryOperator f,double left,double right,double tolerance,String method,int iterations,int evaluations) {
        return new Runner(f,left,right,tolerance,method,iterations,evaluations).run();
    }
    static String fixed6(double x) { return String.format(Locale.ROOT,"%.6f",Math.abs(x)<0.0000005 ? 0.0 : x); }
    static void show(String name,DoubleUnaryOperator f,double left,double right,double tolerance,String method,int iterations,int evaluations) {
        Result r=minimize(f,left,right,tolerance,method,iterations,evaluations);
        System.out.println(name+": "+r.status+", iterations="+r.iterations+", evaluations="+r.evaluations);
        System.out.println("midpoint="+fixed6(r.midpoint)+", width="+String.format(Locale.ROOT,"%.6e",r.right-r.left)+", best="+
                           (r.hasBest ? "("+fixed6(r.bestX)+","+fixed6(r.bestF)+")" : "NONE"));
        for(int i=0;i<r.history.size();++i) {
            Row row=r.history.get(i);
            System.out.println("i="+(i+1)+", interval=["+fixed6(row.left)+","+fixed6(row.right)+"], best_x="+fixed6(row.bestX)+
                               ", best_f="+fixed6(row.bestF)+", evaluations="+row.evaluations);
        }
    }
    static double quadratic(double x) { double z=x-2.5; return z*z+1.0; }
    public static void main(String[] args) {
        show("ternary",Main::quadratic,0.0,9.0,0.75,"ternary",64,128);
        show("golden",Main::quadratic,0.0,9.0,0.75,"golden",64,128);
        show("endpoint",x->x,0.0,5.0,0.5,"golden",64,128);
        show("minimum plateau",x->Math.max(0.0,Math.abs(x-2.0)-0.5),0.0,6.0,0.5,"ternary",64,128);
        show("evaluation cap",Main::quadratic,0.0,9.0,1e-6,"golden",64,3);
        show("iteration cap",Main::quadratic,0.0,9.0,1e-6,"ternary",2,128);
        show("adjacent doubles",Main::quadratic,1.0,Math.nextUp(1.0),Double.MIN_VALUE,"ternary",64,128);
        show("nonfinite",x->x<5.0 ? quadratic(x) : Double.POSITIVE_INFINITY,0.0,9.0,0.75,"golden",64,128);
        show("already narrow",Main::quadratic,1.0,1.0,0.1,"golden",64,128);
        System.out.println("checks = PASS");
    }
}

Expected standard output, identical in all three languages:

• ternary: CONVERGED, iterations=7, evaluations=14
• midpoint=2.452675, width=5.267490e-01, best=(2.518519,1.000343)
• i=1, interval=[0.000000,6.000000], best_x=3.000000, best_f=1.250000, evaluations=2
• i=2, interval=[0.000000,4.000000], best_x=3.000000, best_f=1.250000, evaluations=4
• i=3, interval=[1.333333,4.000000], best_x=2.666667, best_f=1.027778, evaluations=6
• i=4, interval=[1.333333,3.111111], best_x=2.666667, best_f=1.027778, evaluations=8
• i=5, interval=[1.925926,3.111111], best_x=2.518519, best_f=1.000343, evaluations=10
• i=6, interval=[1.925926,2.716049], best_x=2.518519, best_f=1.000343, evaluations=12
• i=7, interval=[2.189300,2.716049], best_x=2.518519, best_f=1.000343, evaluations=14
• golden: CONVERGED, iterations=6, evaluations=7
• midpoint=2.375388, width=5.015528e-01, best=(2.434588,1.004279)
• i=1, interval=[0.000000,5.562306], best_x=3.437694, best_f=1.879270, evaluations=2
• i=2, interval=[0.000000,3.437694], best_x=2.124612, best_f=1.140916, evaluations=3
• i=3, interval=[1.313082,3.437694], best_x=2.124612, best_f=1.140916, evaluations=4
• i=4, interval=[2.124612,3.437694], best_x=2.626165, best_f=1.015918, evaluations=5
• i=5, interval=[2.124612,2.936141], best_x=2.626165, best_f=1.015918, evaluations=6
• i=6, interval=[2.124612,2.626165], best_x=2.434588, best_f=1.004279, evaluations=7
• endpoint: CONVERGED, iterations=5, evaluations=6
• midpoint=0.225425, width=4.508497e-01, best=(0.278640,0.278640)
• i=1, interval=[0.000000,3.090170], best_x=1.909830, best_f=1.909830, evaluations=2
• i=2, interval=[0.000000,1.909830], best_x=1.180340, best_f=1.180340, evaluations=3
• i=3, interval=[0.000000,1.180340], best_x=0.729490, best_f=0.729490, evaluations=4
• i=4, interval=[0.000000,0.729490], best_x=0.450850, best_f=0.450850, evaluations=5
• i=5, interval=[0.000000,0.450850], best_x=0.278640, best_f=0.278640, evaluations=6
• minimum plateau: CONVERGED, iterations=5, evaluations=10
• midpoint=2.074074, width=3.950617e-01, best=(2.000000,0.000000)
• i=1, interval=[0.000000,4.000000], best_x=2.000000, best_f=0.000000, evaluations=2
• i=2, interval=[0.000000,2.666667], best_x=2.000000, best_f=0.000000, evaluations=4
• i=3, interval=[0.888889,2.666667], best_x=2.000000, best_f=0.000000, evaluations=6
• i=4, interval=[1.481481,2.666667], best_x=2.000000, best_f=0.000000, evaluations=8
• i=5, interval=[1.876543,2.271605], best_x=2.000000, best_f=0.000000, evaluations=10
• evaluation cap: EVAL_LIMIT, iterations=2, evaluations=3
• midpoint=1.718847, width=3.437694e+00, best=(2.124612,1.140916)
• i=1, interval=[0.000000,5.562306], best_x=3.437694, best_f=1.879270, evaluations=2
• i=2, interval=[0.000000,3.437694], best_x=2.124612, best_f=1.140916, evaluations=3
• iteration cap: ITER_LIMIT, iterations=2, evaluations=4
• midpoint=2.000000, width=4.000000e+00, best=(3.000000,1.250000)
• i=1, interval=[0.000000,6.000000], best_x=3.000000, best_f=1.250000, evaluations=2
• i=2, interval=[0.000000,4.000000], best_x=3.000000, best_f=1.250000, evaluations=4
• adjacent doubles: STALLED, iterations=0, evaluations=0
• midpoint=1.000000, width=2.220446e-16, best=NONE
• nonfinite: NONFINITE, iterations=0, evaluations=2
• midpoint=4.500000, width=9.000000e+00, best=(3.437694,1.879270)
• already narrow: CONVERGED, iterations=0, evaluations=0
• midpoint=1.000000, width=0.000000e+00, best=NONE
• checks = PASS

Complexity, Correctness, and Invariants

Let initial width be $W_0=b-a$ and assume exact arithmetic, valid shape, finite reliable values, and no resource interruption. If $W_0\le\varepsilon$, no reduction is needed. Otherwise, a ternary inequality retains $2/3$ of the width and a ternary equality retains $1/3$, giving

$$W_k\le\left(\frac23\right)^kW_0,\qquad k_{\mathrm{ternary}}\le\left\lceil\frac{\log(W_0/\varepsilon)}{\log(3/2)}\right\rceil.$$

That upper bound is attained when every reduction takes an inequality branch. If every comparison ties, only $\lceil\log(W_0/\varepsilon)/\log3\rceil$ reductions are needed. Golden-section always retains fraction $\rho$ under this lesson's tie policy:

$$W_k=\rho^kW_0,\qquad k_{\mathrm{golden}}=\left\lceil\frac{\log(W_0/\varepsilon)}{\log(1/\rho)}\right\rceil.$$

Thus both need $O(\log(W_0/\varepsilon))$ reductions when reduction is necessary, but objective-call constants differ: $2k$ for ternary and $k+1$ for golden, for $k\ge1$. If each evaluation costs $C_f$, time is $O((C_f+1)k)$; with variable evaluation costs, charge their actual sum. Golden-section has linear convergence in interval width, not quadratic convergence in the estimate. Floating-point steps approximate these exact ratios and can stall before an arbitrarily small tolerance is reached.

Best, average, worst. The best request has an already narrow interval and uses constant work and zero evaluations. For a fixed nontrivial width target, golden's ideal reduction count is independent of function values; ternary lies between its all-tie and all-inequality bounds. An average ternary count requires a distribution over objectives or comparisons, which is not specified here. Worst-case mathematical work follows the logarithmic bounds; in the programs, explicit caps additionally limit reductions and calls, without implying success.

The interval-search core stores a constant number of scalars and uses $O(1)$ auxiliary space. These programs retain the entire history, so actual additional storage is $O(k)$, plus any memory owned by the objective. They are iterative and have no recursion stack. A slow callback can dominate runtime even with a small evaluation count.

Why interval elimination is correct. If $f(x_1)\lt f(x_2)$ and all minimizers were strictly to the right of $x_2$, the strict decreasing side would require $f(x_1)\gt f(x_2)$, a contradiction. Therefore retaining $[l,x_2]$ preserves some minimizer; the opposite inequality is symmetric. On equality, either the probes straddle the minimum set or both lie on it, because strict monotonicity excludes equality elsewhere on one side. Retaining $[x_1,x_2]$, or the larger left interval used by golden, preserves at least one minimizer. Induct from the initial interval, and geometric shrinkage yields the width target.

This proof assumes truthful comparisons of the specified function. Floating-point representation, noise, or an unsupported flat region can violate that premise. Numeric checks establish finite values, distinct probes, and progress; they cannot establish unimodality or certify comparison accuracy from a few black-box samples.

Location and value accuracy differ. If a retained interval contains a minimizer, the midpoint is within half its width of some minimizer. If $f$ is also $L$-Lipschitz, then $f(\widehat{x})-f_{\min}\le L\varepsilon/2$. If instead it is twice differentiable around an interior stationary minimizer and $0\le f''(x)\le M$ on the relevant segment, then $f(\widehat{x})-f_{\min}\le M\varepsilon^2/8$. These are additional assumptions, and neither bound is supplied just by calling the search routine. The best sampled value is a separate observed quantity, not an automatically certified value-error bound.

Variants, Pitfalls, and Optimizations

Do not confuse weak unimodality with safe tie handling. Consider a continuous function that stays at value $1$ on $[0,0.8]$, decreases linearly to $0$ at $0.9$, and rises afterward. Its first ternary probes at $1/3$ and $2/3$ tie at $1$, but retaining the middle discards the true minimizer. Golden's equal-value left choice also discards it. A shape described merely as nonincreasing then nondecreasing can contain this trap; the stronger assumption at the start of this lesson excludes it.

Numerical ties can be false information. In binary64, evaluating $10^{20}+(x-0.9)^2$ on $[0,1]$ rounds away the small variation. Both methods see equal values and can discard $0.9$, although the underlying real-valued quadratic has its minimum there. CONVERGED then certifies only the represented width. Scaling the variable, removing a known large additive constant before computation, using higher precision, or using trustworthy error bounds can help; adding an arbitrary comparison epsilon does not restore the proof. Simulation noise likewise requires a statistical comparison model and usually repeated sampling rather than ordinary deterministic golden caching.

Choose a meaningful tolerance. An absolute location tolerance has the same units as $x$. A combined rule such as $r-l\le\varepsilon_{\mathrm{abs}}+\varepsilon_{\mathrm{rel}}\max(\lvert l\rvert,\lvert r\rvert)$ can be useful at different scales, but it is a different stopping policy from the code. Adjacent doubles may have no distinct interior pair; the sample near $1$ returns STALLED at width about $2.220446\times10^{-16}$ when the requested tolerance is the smallest positive subnormal. Increasing iterations cannot manufacture additional precision.

Preserve the cache exactly. Move an old coordinate together with its evaluated value. Recomputing its ideal golden coordinate can differ by one rounding unit, and reusing its old value at that new location is not an exact cache hit. Also avoid evaluating the pending new probe after tolerance is already met; that extra call wastes the very benefit golden-section is meant to provide. Objective exceptions, non-finite values, and evaluation limits must leave the last committed interval intact.

Bounded intervals and endpoints matter. The examples retain the original domain and allow the minimizer at an endpoint, as in $f(x)=x$ on $[0,5]$. The algorithm need not sample that endpoint, so its best sampled score will not necessarily equal the exact boundary optimum. If endpoint objective values are required for reporting, query and count them explicitly. A library's two-point bracket can instead be a starting pair for an expanding downhill search; it is not automatically a hard bound. In SciPy, bounded scalar minimization has a dedicated bounds interface, distinct from the bracket argument used by golden/Brent methods.

Use the right variant. To maximize, minimize $-f$ with finite, well-scaled arithmetic and reverse the final reported score. On integer domains, stop while a few candidate indices remain and evaluate all of them; real-width tolerances and rounded golden coordinates are not a replacement for that scan. With integer ternary probes, ensure they are distinct and each update strictly reduces the candidate range. If adjacent-value slope comparisons are available under a compatible strict-sided sequence model, binary search can be simpler. A derivative-sign method can halve a continuous interval when the derivative assumptions hold; Brent-style interpolation can improve practical speed on smooth objectives. Multimodal or high-dimensional objectives require additional structure or a different optimization strategy.

Practice Problems and Real-World Use

Start with functions whose minimizers are independently known: shifted quadratics, absolute-value valleys, monotone objectives with endpoint minima, and functions flat only on their minimum set. Record every queried coordinate, verify nested intervals and progress, and check that no call is made outside the initial domain or beyond the evaluation cap. Test ties, zero budgets, already narrow intervals, failure on the second initialization call, and representability limits separately.

The programs were checked on 8,960 inputs per language, comprising $8{,}946$ valid requests and $14$ invalid numeric/method requests. Across a well-conditioned subset, analytic minimum sets checked $8{,}724$ final results and $170{,}674$ retained intervals. The full corpus included $172{,}306$ interval-update audits and $81{,}974$ exact golden probe/value-reuse checks, plus explicit non-finite, budget, subnormal, and false-equality cases. Four deliberate counterexamples reproduced loss of the intended real minimizer when the shape or reliable-comparison premise was absent; those are limitations demonstrated by the tests, not cases claimed to satisfy the convergence theorem. Python, C++, and Java matched all result/history floating-point fields bit for bit under the stated arithmetic settings and agreed on repeated runs. The C++ corpus also passed address/undefined-behavior instrumentation.

Primary background includes Michael Heath's golden-section teaching module and Jan Verschelde's numerical-analysis lecture. For library parameter semantics, consult the official SciPy scalar-minimization documentation. The exact tie policy, lazy evaluation timing, status contract, code, and numerical caveats in this lesson are specified directly here.