Scholar.Optimize.Brent (Scholar v0.4.2)

Copy Markdown View Source

Brent's method for univariate function minimization.

Brent's method combines the robustness of golden section search with the speed of parabolic interpolation. It uses parabolic interpolation when it appears to be converging well, but falls back to golden section search when the parabola would produce a step outside the bracket or too small a reduction.

Algorithm

At each iteration, the algorithm considers fitting a parabola through three points and using its minimum as the next guess. If the parabolic step is acceptable (within bounds and making sufficient progress), it is used. Otherwise, a golden section step is taken.

The algorithm tracks six points:

  • a, b: Current bracket bounds (minimum is between a and b)
  • x: Best point found so far (lowest function value)
  • w: Second best point
  • v: Previous value of w
  • d: Most recent step size
  • e: Step size from two iterations ago

Convergence

Brent's method typically achieves superlinear convergence near the minimum due to parabolic interpolation, while maintaining the guaranteed convergence of golden section search. It is significantly faster than pure golden section for smooth functions.

References

  • Brent, R. P. (1973). "Algorithms for Minimization without Derivatives"
  • Press, W. H., et al. "Numerical Recipes: The Art of Scientific Computing"

Summary

Types

t()

Functions

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

Minimizes a scalar function using Brent's method.

Types

t()

@type t() :: %Scholar.Optimize.Brent{
  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 Brent's method.

Brent's method is the recommended algorithm for scalar optimization as it combines the reliability of golden section search with faster convergence from parabolic interpolation.

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 - Relative 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.Brent 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.Brent.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-4) |> 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.Brent.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

Comparison with Golden Section

Brent's method typically converges in significantly fewer iterations than golden section search:

# For a simple parabola (x-3)^2 on [0, 5]:
# Brent: ~5-8 function evaluations
# Golden Section: ~40-45 function evaluations