Scholar.Optimize.GoldenSection (Scholar v0.4.2)

Copy Markdown View Source

Golden section search for univariate function minimization.

Golden section search is a derivative-free optimization technique for finding the minimum of a unimodal function within a specified interval. It works by iteratively narrowing the bracket using the golden ratio to determine probe points.

Algorithm

The golden ratio $\phi = \frac{\sqrt{5} - 1}{2} \approx 0.618$ is used to select interior points that maintain optimal bracket reduction per iteration. At each step, one of the interior points is reused, requiring only one new function evaluation per iteration.

Convergence

The bracket width decreases by a factor of $\phi \approx 0.618$ per iteration, giving linear convergence. After $n$ iterations, the bracket width is approximately $\phi^n$ times the original width.

References

  • Press, W. H., et al. "Numerical Recipes: The Art of Scientific Computing"
  • Kiefer, J. (1953). "Sequential minimax search for a maximum"

Summary

Types

t()

Functions

minimize(a, b, fun, opts \\ [])

Minimizes a scalar function using golden section search.

Types

t()

@type t() :: %Scholar.Optimize.GoldenSection{
  converged: Nx.Tensor.t(),
  fun: Nx.Tensor.t(),
  fun_evals: Nx.Tensor.t(),
  iterations: Nx.Tensor.t(),
  x: Nx.Tensor.t()
}

Functions

minimize(a, b, fun, opts \\ [])

Minimizes a scalar function using golden section search.

Arguments

  • a - Lower bound of the search interval (number or scalar tensor).
  • b - Upper bound of the search interval (number or scalar tensor). Must satisfy a < b.
  • fun - The objective function to minimize. Must be a defn-compatible function that takes a scalar tensor and returns a scalar tensor.
  • opts - Options (see below).

Options

  • :tol - Absolute tolerance for convergence. Default is 1.0e-5 which works with f32 precision. For higher precision, use f64 tensors for bounds and a smaller tolerance. The default value is 1.0e-5.

  • :maxiter (pos_integer/0) - Maximum number of iterations. The default value is 500.

Returns

A Scholar.Optimize.GoldenSection struct with the optimization result:

  • :x - The optimal point found
  • :fun - The function value at the optimal point
  • :converged - Whether the optimization converged (1 if true, 0 if false)
  • :iterations - Number of iterations performed
  • :fun_evals - Number of function evaluations

Examples

iex> fun = fn x -> Nx.pow(Nx.subtract(x, 3), 2) end
iex> result = Scholar.Optimize.GoldenSection.minimize(0.0, 5.0, fun)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor(3.0), atol: 1.0e-3) |> Nx.to_number()
1

For higher precision, use f64 tensors:

iex> fun = fn x -> Nx.pow(Nx.subtract(x, 3), 2) end
iex> a = Nx.tensor(0.0, type: :f64)
iex> b = Nx.tensor(5.0, type: :f64)
iex> result = Scholar.Optimize.GoldenSection.minimize(a, b, fun, tol: 1.0e-10)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor(3.0), atol: 1.0e-8) |> Nx.to_number()
1