Univariate Optimizers

The optimization problem for a univariate function on a closed interval can be described as

\[\min_{x} f(x), \quad x \in [lb, ub].\]

bboptpy provides a number of algorithms for optimizing univariate functions.

Branch and Bound

The branch and bound technique for univariate functions is described in this paper:

Aaid, Djamel, Amel Noui, and Mohand Ouanes. “New technique for solving univariate global optimization.” Archivum Mathematicum 53.1 (2017): 19-33.

In summary, branch and bound is a search technique that finds a global minimum of a univariate function, which also enjoys strong theoretical convergence properties. It uses an iterative process of splitting the optimization interval into disjoint subintervals until the minimum has been found. A quadratic underestimator of the objective is also fit to guide the division.

BranchAndBound(mfev, tol, K, n=16)

Initializes a new branch and bound optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
tol (float) – Terminate when the estimated error of the solution is lower than this value.
K (float) – Upper bound on the second derivative of the objective function.
n (int) – Number of quadratic functions to use for the underestimator.

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

Brent’s Methods

The Brent’s methods for local and global search are described in this book:

Brent, Richard P. Algorithms for minimization without derivatives. Courier Corporation, 2013.

Both versions of his methods are particularly robust for optimizing univariate functions. The local variant finds a local minimum of a univariate function by adaptive combining golden-section search with parabolic interpolation.

Brent(mfev, atol, rtol=1e-15)

Initializes a new local Brent optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
atol (float) – Terminate when the estimated error of the solution is lower than this value (absolute tolerance).
rtol (float) – Terminate when the estimated error of the solution is lower than this value (relative tolerance).

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

The global variant finds a global minimum under the assumption that the second derivative of the objective is upper-bounded. This is the translation of the Fortran subroutine by John Burkardt.

GlobalBrent(mfev, tol, bound_on_hessian)

Initializes a new global Brent optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
tol (float) – Terminate when the estimated error of the solution is lower than this value.
bound_on_hessian (float) – Upper bound on the second derivative of the objective function.

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

Calvin’s Method

The Calvin’s method for univariate functions is described in this paper:

Calvin, James M., Yvonne Chen, and Antanas Žilinskas. “An adaptive univariate global optimization algorithm and its convergence rate for twice continuously differentiable functions.” Journal of Optimization Theory and Applications 155 (2012): 628-636.

In summary, this is a global search method that uses an interval splitting technique to find the global minimum. It enjoys strong theoretical asymptotic convergence properties for continuous functions sampled randomly according to the Wiener measure.

Calvin(mfev, tol, lam=16)

Initializes a new Calvin optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
tol (float) – Terminate when the estimated error of the solution is lower than this value.
lam (float) – The lambda parameter specified in the paper (must be at least 16).

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

Davies-Swann-Campey Method

This method is described in detail in this book:

Antoniou, Andreas, and Wu-Sheng Lu. Practical optimization. Springer, 2007.

This method is not widely known or implemented, but it appears to be very robust in finding local minima of smooth univariate functions. It takes decreasingly smaller steps along a direction until a bracket for the minimum is located.

DSC(mfev, tol, decay=0.1)

Initializes a new Davies-Swann-Campey optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
tol (float) – Terminate when the estimated error of the solution is lower than this value.
decay (float) – How much to decay the step size in each iteration.

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

Fibonacci Search

The Fibonacci search is described in detail in this paper:

Kiefer, J. (1953), “Sequential minimax search for a maximum”, Proceedings of the American Mathematical Society, 4 (3): 502–506

The Fibonacci search is a simple algorithm for finding the local minimum of a strictly unimodal, but not necessarily continuous, function. This overall strategy works by reducing the interval of uncertainty in every step, ultimately converging the interval, containing the minimizer, to a desired small size. Specifically, the search interval is divided into two parts that have sizes proportional to two consecutive Fibonacci numbers.

Fibonacci(mfev, atol, rtol=1e-15)

Initializes a new Fibonacci optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
atol (float) – Terminate when the estimated error of the solution is lower than this value (absolute tolerance).
rtol (float) – Terminate when the estimated error of the solution is lower than this value (relative tolerance).

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

Golden Section Search

The golden section search is described in detail in this paper:

Kiefer, J. (1953), “Sequential minimax search for a maximum”, Proceedings of the American Mathematical Society, 4 (3): 502–506

This algorithm can be seen as a limit of the Fibonacci search, in the sense that the ratio of two consecutive Fibonacci numbers approaches the golden ratio. Like the Fibonacci search, this algorithm works when the objective function is strictly unimodal, but not necessarily continuous.

GoldenSection(mfev, atol, rtol=1e-15)

Initializes a new golden section search optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
atol (float) – Terminate when the estimated error of the solution is lower than this value (absolute tolerance).
rtol (float) – Terminate when the estimated error of the solution is lower than this value (relative tolerance).

Returns:

optimizer instance

Return type:

object of type UnivariateSearch

Piyavskii’s Method

The Piyavskii method as implemented in this package is described in the following paper:

Lera, Daniela, and Yaroslav D. Sergeyev. “Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives.” SIAM Journal on Optimization 23.1 (2013): 508-529.

The Piyavskii method is suitable for finding the global minimum of a univariate Lipschitz-continuous function. The original algorithm requires the Lipschitz constant to be properly estimated in order for the method to be effective. It uses the Lipschitz property to define a piecewise linear support function over the search space that bounds the original objective. The version implemented here estimates the Lipschitz constant adaptively, and thus does not require the constant to be specified a-priori.

Piyavskii(mfev, tol, r=1.4, xi=1e-6)

Initializes a new adaptive Piyavskii optimizer with the specified parameters.

Parameters:

mfev (int) – Maximum number of function evaluations.
tol (float) – Terminate when the estimated error of the solution is lower than this value.
r (float) – The r parameter specified in the paper for estimating the Lipschitz constant.
xi (float) – The xi parameter specified in the paper for estimating the Lipschitz constant.

Returns:

optimizer instance

Return type:

object of type UnivariateSearch