Optimization and root finding ( scipy.optimize )#
SciPy optimize provides functions for minimizing (or maximizing) objective functions, possibly subject to constraints. It includes solvers for nonlinear problems (with support for both local and global optimization algorithms), linear programing, constrained and nonlinear least-squares, root finding, and curve fitting.
Common functions and objects, shared across different solvers, are:
Show documentation for additional options of optimization solvers.
Represents the optimization result.
Optimization#
Scalar functions optimization#
Minimization of scalar function of one variable.
The minimize_scalar function supports the following methods:
Local (multivariate) optimization#
minimize (fun, x0[, args, method, jac, hess, . ])
Minimization of scalar function of one or more variables.
The minimize function supports the following methods:
- minimize(method=’Nelder-Mead’)
- minimize(method=’Powell’)
- minimize(method=’CG’)
- minimize(method=’BFGS’)
- minimize(method=’Newton-CG’)
- minimize(method=’L-BFGS-B’)
- minimize(method=’TNC’)
- minimize(method=’COBYLA’)
- minimize(method=’SLSQP’)
- minimize(method=’trust-constr’)
- minimize(method=’dogleg’)
- minimize(method=’trust-ncg’)
- minimize(method=’trust-krylov’)
- minimize(method=’trust-exact’)
Constraints are passed to minimize function as a single object or as a list of objects from the following classes:
Nonlinear constraint on the variables.
Linear constraint on the variables.
Simple bound constraints are handled separately and there is a special class for them:
Bounds constraint on the variables.
Quasi-Newton strategies implementing HessianUpdateStrategy interface can be used to approximate the Hessian in minimize function (available only for the ‘trust-constr’ method). Available quasi-Newton methods implementing this interface are:
Broyden-Fletcher-Goldfarb-Shanno (BFGS) Hessian update strategy.
Symmetric-rank-1 Hessian update strategy.
Global optimization#
Find the global minimum of a function using the basin-hopping algorithm.
brute (func, ranges[, args, Ns, full_output, . ])
Minimize a function over a given range by brute force.
Finds the global minimum of a multivariate function.
shgo (func, bounds[, args, constraints, n, . ])
Finds the global minimum of a function using SHG optimization.
Find the global minimum of a function using Dual Annealing.
direct (func, bounds, *[, args, eps, maxfun, . ])
Finds the global minimum of a function using the DIRECT algorithm.
Least-squares and curve fitting#
Nonlinear least-squares#
Solve a nonlinear least-squares problem with bounds on the variables.
Linear least-squares#
Solve argmin_x || Ax — b ||_2 for x>=0 .
Solve a linear least-squares problem with bounds on the variables.
Curve fitting#
Use non-linear least squares to fit a function, f, to data.
Root finding#
Scalar functions#
Find a root of a scalar function.
brentq (f, a, b[, args, xtol, rtol, maxiter, . ])
Find a root of a function in a bracketing interval using Brent’s method.
brenth (f, a, b[, args, xtol, rtol, maxiter, . ])
Find a root of a function in a bracketing interval using Brent’s method with hyperbolic extrapolation.
ridder (f, a, b[, args, xtol, rtol, maxiter, . ])
Find a root of a function in an interval using Ridder’s method.
bisect (f, a, b[, args, xtol, rtol, maxiter, . ])
Find root of a function within an interval using bisection.
Find a root of a real or complex function using the Newton-Raphson (or secant or Halley’s) method.
Find a root using TOMS Algorithm 748 method.
Represents the root finding result.
The root_scalar function supports the following methods:
The table below lists situations and appropriate methods, along with asymptotic convergence rates per iteration (and per function evaluation) for successful convergence to a simple root(*). Bisection is the slowest of them all, adding one bit of accuracy for each function evaluation, but is guaranteed to converge. The other bracketing methods all (eventually) increase the number of accurate bits by about 50% for every function evaluation. The derivative-based methods, all built on newton , can converge quite quickly if the initial value is close to the root. They can also be applied to functions defined on (a subset of) the complex plane.
scipy.optimize.lsq_linear#
Solve a linear least-squares problem with bounds on the variables.
Given a m-by-n design matrix A and a target vector b with m elements, lsq_linear solves the following optimization problem:
minimize 0.5 * ||A x - b||**2 subject to lb x ub
This optimization problem is convex, hence a found minimum (if iterations have converged) is guaranteed to be global.
Parameters : A array_like, sparse matrix of LinearOperator, shape (m, n)
b array_like, shape (m,)
bounds 2-tuple of array_like or Bounds , optional
Lower and upper bounds on parameters. Defaults to no bounds. There are two ways to specify the bounds:
- Instance of Bounds class.
- 2-tuple of array_like: Each element of the tuple must be either an array with the length equal to the number of parameters, or a scalar (in which case the bound is taken to be the same for all parameters). Use np.inf with an appropriate sign to disable bounds on all or some parameters.
Method to perform minimization.
- ‘trf’ : Trust Region Reflective algorithm adapted for a linear least-squares problem. This is an interior-point-like method and the required number of iterations is weakly correlated with the number of variables.
- ‘bvls’ : Bounded-variable least-squares algorithm. This is an active set method, which requires the number of iterations comparable to the number of variables. Can’t be used when A is sparse or LinearOperator.
tol float, optional
Tolerance parameter. The algorithm terminates if a relative change of the cost function is less than tol on the last iteration. Additionally, the first-order optimality measure is considered:
- method=’trf’ terminates if the uniform norm of the gradient, scaled to account for the presence of the bounds, is less than tol.
- method=’bvls’ terminates if Karush-Kuhn-Tucker conditions are satisfied within tol tolerance.
Method of solving unbounded least-squares problems throughout iterations:
- ‘exact’ : Use dense QR or SVD decomposition approach. Can’t be used when A is sparse or LinearOperator.
- ‘lsmr’ : Use scipy.sparse.linalg.lsmr iterative procedure which requires only matrix-vector product evaluations. Can’t be used with method=’bvls’ .
If None (default), the solver is chosen based on type of A.
lsmr_tol None, float or ‘auto’, optional
Tolerance parameters ‘atol’ and ‘btol’ for scipy.sparse.linalg.lsmr If None (default), it is set to 1e-2 * tol . If ‘auto’, the tolerance will be adjusted based on the optimality of the current iterate, which can speed up the optimization process, but is not always reliable.
max_iter None or int, optional
Maximum number of iterations before termination. If None (default), it is set to 100 for method=’trf’ or to the number of variables for method=’bvls’ (not counting iterations for ‘bvls’ initialization).
verbose , optional
Level of algorithm’s verbosity:
- 0 : work silently (default).
- 1 : display a termination report.
- 2 : display progress during iterations.
Maximum number of iterations for the lsmr least squares solver, if it is used (by setting lsq_solver=’lsmr’ ). If None (default), it uses lsmr’s default of min(m, n) where m and n are the number of rows and columns of A, respectively. Has no effect if lsq_solver=’exact’ .
Returns : OptimizeResult with the following fields defined: x ndarray, shape (n,)
cost float
Value of the cost function at the solution.
fun ndarray, shape (m,)
Vector of residuals at the solution.
optimality float
First-order optimality measure. The exact meaning depends on method, refer to the description of tol parameter.
active_mask ndarray of int, shape (n,)
Each component shows whether a corresponding constraint is active (that is, whether a variable is at the bound):
- 0 : a constraint is not active.
- -1 : a lower bound is active.
- 1 : an upper bound is active.
Might be somewhat arbitrary for the trf method as it generates a sequence of strictly feasible iterates and active_mask is determined within a tolerance threshold.
unbounded_sol tuple
Unbounded least squares solution tuple returned by the least squares solver (set with lsq_solver option). If lsq_solver is not set or is set to ‘exact’ , the tuple contains an ndarray of shape (n,) with the unbounded solution, an ndarray with the sum of squared residuals, an int with the rank of A, and an ndarray with the singular values of A (see NumPy’s linalg.lstsq for more information). If lsq_solver is set to ‘lsmr’ , the tuple contains an ndarray of shape (n,) with the unbounded solution, an int with the exit code, an int with the number of iterations, and five floats with various norms and the condition number of A (see SciPy’s sparse.linalg.lsmr for more information). This output can be useful for determining the convergence of the least squares solver, particularly the iterative ‘lsmr’ solver. The unbounded least squares problem is to minimize 0.5 * ||A x — b||**2 .
Number of iterations. Zero if the unconstrained solution is optimal.
status int
Reason for algorithm termination:
- -1 : the algorithm was not able to make progress on the last iteration.
- 0 : the maximum number of iterations is exceeded.
- 1 : the first-order optimality measure is less than tol.
- 2 : the relative change of the cost function is less than tol.
- 3 : the unconstrained solution is optimal.
Verbal description of the termination reason.
success bool
True if one of the convergence criteria is satisfied (status > 0).
Linear least squares with non-negativity constraint.
Nonlinear least squares with bounds on the variables.
The algorithm first computes the unconstrained least-squares solution by numpy.linalg.lstsq or scipy.sparse.linalg.lsmr depending on lsq_solver. This solution is returned as optimal if it lies within the bounds.
Method ‘trf’ runs the adaptation of the algorithm described in [STIR] for a linear least-squares problem. The iterations are essentially the same as in the nonlinear least-squares algorithm, but as the quadratic function model is always accurate, we don’t need to track or modify the radius of a trust region. The line search (backtracking) is used as a safety net when a selected step does not decrease the cost function. Read more detailed description of the algorithm in scipy.optimize.least_squares .
Method ‘bvls’ runs a Python implementation of the algorithm described in [BVLS]. The algorithm maintains active and free sets of variables, on each iteration chooses a new variable to move from the active set to the free set and then solves the unconstrained least-squares problem on free variables. This algorithm is guaranteed to give an accurate solution eventually, but may require up to n iterations for a problem with n variables. Additionally, an ad-hoc initialization procedure is implemented, that determines which variables to set free or active initially. It takes some number of iterations before actual BVLS starts, but can significantly reduce the number of further iterations.
M. A. Branch, T. F. Coleman, and Y. Li, “A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems,” SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp 1-23, 1999.
P. B. Start and R. L. Parker, “Bounded-Variable Least-Squares: an Algorithm and Applications”, Computational Statistics, 10, 129-141, 1995.
In this example, a problem with a large sparse matrix and bounds on the variables is solved.
>>> import numpy as np >>> from scipy.sparse import rand >>> from scipy.optimize import lsq_linear >>> rng = np.random.default_rng() . >>> m = 20000 >>> n = 10000 . >>> A = rand(m, n, density=1e-4, random_state=rng) >>> b = rng.standard_normal(m) . >>> lb = rng.standard_normal(n) >>> ub = lb + 1 . >>> res = lsq_linear(A, b, bounds=(lb, ub), lsmr_tol='auto', verbose=1) # may vary The relative change of the cost function is less than `tol`. Number of iterations 16, initial cost 1.5039e+04, final cost 1.1112e+04, first-order optimality 4.66e-08.