One-dimensional optimization

Updated 03 Nov 2026

• •

  Minimum versus root

  • •

    Root finding -> solve $f(x) = 0$

  • •

    Optimization -> minimize or maximize an objective; a minimum need not have $f(x)=0$

  • •

    a smooth interior optimum satisfies $f'(x)=0$; that condition alone does not distinguish a minimum, maximum, or stationary inflection

  • •

    check interval endpoints when solving a bounded optimization problem

• •

  Golden-section search

  • •

    derivative-free interval reduction for a unimodal objective on the chosen interval

  • •

    define $\phi=(\sqrt5-1)/2\approx0.618034$, with $a<c<d<b$.

    • •

      $c=b-\phi(b-a)$, $d=a+\phi(b-a)$.

    • •

      if $f(c)\le f(d)$, retain $[a,d]$; otherwise retain $[c,b]$.

    • •

      reuse one interior point and value; only one new function evaluation is needed per reduction.

  • •

    Interval width -> $L_k=\phi^kL_0$ after $k$ reductions.

    • •

      to reach width $\tau<L_0$: $k\ge\lceil\ln(\tau/L_0)/\ln\phi\rceil$.

    • •

      reducing width 10 to $10^{-4}$ requires 24 reductions.

  • •

    a small interval supports a location estimate under the unimodality assumption, not a global guarantee for arbitrary objectives

• •

  Parabolic and Newton steps

  • •

    Parabolic interpolation

    • •

      fit a parabola through three distinct trial points and use its vertex as the next candidate.

    • •

      with $f_i=f(x_i)$, define $N=(x_2-x_1)^2(f_2-f_3)-(x_2-x_3)^2(f_2-f_1)$.

    • •

      define $D=(x_2-x_1)(f_2-f_3)-(x_2-x_3)(f_2-f_1)$; propose $x_{\mathrm{new}}=x_2-N/(2D)$.

    • •

      guard small denominators, poor curvature, and candidates outside the bracket.

    • •

      example: points $(1,2),(2,-1),(3,4)$ give vertex $x=1.875$.

  • •

    Brent minimization -> safeguards parabolic steps with golden-section fallback

    • •

      scipy.optimize.minimize_scalar offers bounded/Brent methods; this is not the same problem as Brent root finding

  • •

    Newton optimization -> $x_{k+1}=x_k-f'(x_k)/f''(x_k)$

    • •

      needs reliable derivatives and nonzero curvature

    • •

      can converge to a maximum or leave the intended region; check the resulting point and objective

• •

  Python: cached golden-section search

  • •

    standalone standard-library example; explicit status distinguishes convergence from exhausting the limit

  • •

    import math
    
    def golden_min(f, a, b, tol=1e-8, max_iter=200):
          if not all(math.isfinite(v) for v in (a, b, tol)) or a >= b or tol <= 0:
              raise ValueError("finite ordered bounds and positive tolerance required")
          if not isinstance(max_iter, int) or max_iter < 1:
              raise ValueError("positive integer iteration limit required")
          def evaluate(x):
              value = f(x)
              if not math.isfinite(value):
                  raise ValueError("nonfinite objective")
              return value
          phi = (math.sqrt(5) - 1)/2
          c, d = b - phi*(b-a), a + phi*(b-a)
          fc, fd = evaluate(c), evaluate(d)
          it = 0
          while b-a > tol and it < max_iter:
              if fc <= fd:
                  b, d, fd = d, c, fc
                  c = b - phi*(b-a)
                  fc = evaluate(c)
              else:
                  a, c, fc = c, d, fd
                  d = a + phi*(b-a)
                  fd = evaluate(d)
              it += 1
          status = "converged" if b-a <= tol else "iteration_limit"
          x = (a+b)/2
          return x, evaluate(x), (a, b), it, status
    
    x, value, bracket, it, status = golden_min(lambda x: x*x - 4*math.sin(x), 0., 3.)
    assert status == "converged" and bracket[1]-bracket[0] <= 1e-8
    assert abs(x - 1.0298665293) < 5e-8
    assert abs(value + 2.368296005) < 1e-8
    print("minimum:", x, value, "reductions:", it)
    

◌ Explore connections in Graph view