Brent-search’s documentation

Date:May 16, 2021
Version:2.0.0

You can get the source and open issues on Github.

Install

Pip

pip install brent-search

Conda

conda install -c conda-forge brent-search

Examples

Often the first step of a function optimisation is to find an interval within which a solution is believed to exist. The following example shows how brent_search.bracket() can be used to attain that task.

>>> from brent_search import bracket
>>> def f(x):
...     return (x-2)**2
>>>
>>> (x0, x1, x2, f0, f1, f2), e = bracket(f)
>>> print("Left point: {:.2f}".format(x0))
Left point: 1.25
>>> print("Best point: {:.2f}".format(x1))
Best point: 2.50
>>> print("Right point: {:.2f}".format(x2))
Right point: 5.00
>>> print("{:.2f}".format(f0))
0.56
>>> print("{:.2f}".format(f1))
0.25
>>> print("{:.2f}".format(f2))
9.00

The brent_search.brent() function can then be applied to find a minimum within the interval.

>>> from brent_search import brent
>>> (x, fx, exit_code) = brent(f, x0, x2, x1, f1)
>>> print("({:.1f}, {:.1f}, {})".format(x, fx, exit_code))
(2.0, 0.0, 6)

Functions

bracket(f[, x0, x1, a, b, gfactor, rtol, …]) Find a bracketing interval.
brent(f[, a, b, x0, f0, rtol, atol, maxiter]) Seeks a minimum of a function via Brent’s method.
minimize(f[, x0, x1, a, b, gfactor, rtol, …]) Function minimization.

Bracket

brent_search.bracket(f, x0=None, x1=None, a=-inf, b=inf, gfactor=2.0, rtol=1.4902e-08, atol=1.4902e-08, maxiter=500)[source]

Find a bracketing interval.

Given a function f, a bracketing interval is defined as any three strictly increasing points (x0, x1, x2) such that f(x0) > f(x1) < f(x2).

Parameters:
  • f (callable) – Function of interest.
  • x0 (float, optional) – First point.
  • x1 (float, optional) – Second point.
  • a (float, optional) – Interval’s lower limit. Defaults to -inf.
  • b (float, optional) – Interval’s upper limit. Defaults to +inf.
  • gfactor (float, optional) – Growing factor.
  • rtol (float, optional) – Relative tolerance. Defaults to 1.4902e-08.
  • atol (float, optional) – Absolute tolerance. Defaults to 1.4902e-08.
  • maxiter (int, optional) – Maximum number of iterations. Defaults to 500.
Returns:

  • tuple – Found solution (if any): (x0, x1, x2, f0, f1, f2)
  • int – Exit code. From zero to five, they mean “unknown”, “found bracketing interval”, “hit the boundary”, “too close points”, “maxiter reached”, and “not strictly convex function”. Therefore, an exit code 1 means a valid solution has been found. Otherwise an error has occurred.

Brent

brent_search.brent(f, a=-inf, b=inf, x0=None, f0=None, rtol=1.4902e-08, atol=1.4902e-08, maxiter=500)[source]

Seeks a minimum of a function via Brent’s method.

Given a function f with a minimum in the interval a <= b, seeks a local minimum using a combination of golden section search and successive parabolic interpolation.

Let tol = rtol * abs(x0) + atol, where x0 is the best guess found so far. It converges if evaluating a next guess would imply evaluating f at a point that is closer than tol to a previously evaluated one or if the number of iterations reaches maxiter.

Parameters:
  • f (object) – Objective function to be minimized.
  • a (float, optional) – Interval’s lower limit. Defaults to -inf.
  • b (float, optional) – Interval’s upper limit. Defaults to +inf.
  • x0 (float, optional) –

    Initial guess. Defaults to None, which implies that:

    x0 = a + 0.382 * (b - a)
f0 = f(x0)
  • f0 (float, optional) – Function evaluation at x0.
  • rtol (float) – Relative tolerance. Defaults to 1.4902e-08.
  • atol (float) – Absolute tolerance. Defaults to 1.4902e-08.
  • maxiter (int) – Maximum number of iterations.
Returns:

  • float – Best guess x for the minimum of f.
  • float – Value f(x).
  • int – Number of iterations performed.

References

Minimize

brent_search.minimize(f, x0=None, x1=None, a=-inf, b=inf, gfactor=2, rtol=1.4902e-08, atol=1.4902e-08, maxiter=500)[source]

Function minimization.

Applies brent_search.bracket() to find a bracketing interval, to which brent_search.brent() is subsequently applied to find a local minimum.

Parameters:
  • f (callable) – Function of interest.
  • x0 (float, optional) – First point.
  • x1 (float, optional) – Second point.
  • a (float, optional) – Interval’s lower limit. Defaults to -inf.
  • b (float, optional) – Interval’s upper limit. Defaults to +inf.
  • gfactor (float, optional) – Growing factor.
  • rtol (float, optional) – Relative tolerance. Defaults to 1.4902e-08.
  • atol (float, optional) – Absolute tolerance. Defaults to 1.4902e-08.
  • maxiter (int, optional) – Maximum number of iterations. Defaults to 500.
Returns:

  • float – Found solution (if any).
  • float – Function evaluation at that point.
  • int – The number of function evaluations.