Scholar.Optimize.BFGS (Scholar v0.4.2)

Copy Markdown View Source

BFGS (Broyden-Fletcher-Goldfarb-Shanno) algorithm for multivariate function minimization.

BFGS is a quasi-Newton optimization method that approximates the inverse Hessian matrix using gradient information. It is well-suited for smooth, differentiable objective functions and typically converges much faster than derivative-free methods like Nelder-Mead.

Algorithm

At each iteration, the algorithm:

  1. Computes the gradient using automatic differentiation
  2. Determines a search direction from the inverse Hessian approximation
  3. Performs a line search to find an acceptable step length
  4. Updates the inverse Hessian approximation using the BFGS formula

Convergence

The algorithm converges when the gradient norm falls below the specified tolerance.

References

  • Nocedal, J. and Wright, S. J. (2006). "Numerical Optimization"
  • Fletcher, R. (1987). "Practical Methods of Optimization"

Summary

Types

t()

Functions

minimize(x0, fun, opts \\ [])

Minimizes a multivariate function using the BFGS algorithm.

Types

t()

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

Functions

minimize(x0, fun, opts \\ [])

Minimizes a multivariate function using the BFGS algorithm.

BFGS is a gradient-based method that uses automatic differentiation to compute gradients and approximates the inverse Hessian matrix for fast convergence.

Arguments

  • x0 - Initial guess as a 1-D tensor of shape {n}.
  • fun - The objective function to minimize. Must be a defn-compatible function that takes a 1-D tensor of shape {n} and returns a scalar tensor.
  • opts - Options (see below).

Options

  • :gtol - Gradient norm tolerance for convergence. The algorithm stops when the infinity norm of the gradient is below this threshold. The default value is 1.0e-5.

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

Returns

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

  • :x - The optimal point found (shape {n})
  • :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
  • :grad_evals - Number of gradient evaluations

Examples

iex> # Minimize a simple quadratic: f(x) = x1^2 + x2^2
iex> fun = fn x -> Nx.sum(Nx.pow(x, 2)) end
iex> x0 = Nx.tensor([1.0, 2.0])
iex> result = Scholar.Optimize.BFGS.minimize(x0, fun)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor([0.0, 0.0]), atol: 1.0e-4) |> Nx.to_number()
1

For higher precision, use f64 tensors:

iex> fun = fn x -> Nx.sum(Nx.pow(x, 2)) end
iex> x0 = Nx.tensor([1.0, 2.0], type: :f64)
iex> result = Scholar.Optimize.BFGS.minimize(x0, fun, gtol: 1.0e-10)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor([0.0, 0.0]), atol: 1.0e-8) |> Nx.to_number()
1

Minimizing the Rosenbrock function:

iex> # Rosenbrock: f(x,y) = (1-x)^2 + 100*(y-x^2)^2, minimum at (1, 1)
iex> rosenbrock = fn x ->
...>   x0 = x[0]
...>   x1 = x[1]
...>   term1 = Nx.pow(Nx.subtract(1, x0), 2)
...>   term2 = Nx.multiply(100, Nx.pow(Nx.subtract(x1, Nx.pow(x0, 2)), 2))
...>   Nx.add(term1, term2)
...> end
iex> x0 = Nx.tensor([0.0, 0.0], type: :f64)
iex> result = Scholar.Optimize.BFGS.minimize(x0, rosenbrock, gtol: 1.0e-8, maxiter: 1000)
iex> Nx.to_number(result.converged)
1
iex> Nx.all_close(result.x, Nx.tensor([1.0, 1.0]), atol: 1.0e-4) |> Nx.to_number()
1