scipy.optimize.

- scipy.optimize.lsq_linear(
*A*,*b*,*bounds=(-inf, inf)*,*method='trf'*,*tol=1e-10*,*lsq_solver=None*,*lsmr_tol=None*,*max_iter=None*,*verbose=0*,***,*lsmr_maxiter=None*)[source]# 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||**2subject to lb <= x <= ub

This optimization problem is convex, hence a found minimum (if iterationshave converged) is guaranteed to be global.

- Parameters:
**A**array_like, sparse matrix of LinearOperator, shape (m, n)Design matrix. Can be scipy.sparse.linalg.LinearOperator.

**b**array_like, shape (m,)Target vector.

**bounds**2-tuple of array_like or Bounds, optionalLower 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 eitheran array with the length equal to the number of parameters, or ascalar (in which case the bound is taken to be the same for allparameters). Use

`np.inf`

with an appropriate sign to disablebounds on all or some parameters.

**method**‘trf’ or ‘bvls’, optionalMethod to perform minimization.

‘trf’ : Trust Region Reflective algorithm adapted for a linearleast-squares problem. This is an interior-point-like methodand the required number of iterations is weakly correlated withthe number of variables.

‘bvls’ : Bounded-variable least-squares algorithm. This isan active set method, which requires the number of iterationscomparable to the number of variables. Can’t be used when

*A*issparse or LinearOperator.

Default is ‘trf’.

**tol**float, optionalTolerance parameter. The algorithm terminates if a relative changeof 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 conditionsare satisfied within*tol*tolerance.

**lsq_solver**{None, ‘exact’, ‘lsmr’}, optionalMethod of solving unbounded least-squares problems throughoutiterations:

‘exact’ : Use dense QR or SVD decomposition approach. Can’t beused when

*A*is sparse or LinearOperator.‘lsmr’ : Use scipy.sparse.linalg.lsmr iterative procedurewhich requires only matrix-vector product evaluations. Can’tbe used with

`method='bvls'`

.

If None (default), the solver is chosen based on type of

*A*.**lsmr_tol**None, float or ‘auto’, optionalTolerance parameters ‘atol’ and ‘btol’ for scipy.sparse.linalg.lsmrIf None (default), it is set to

`1e-2 * tol`

. If ‘auto’, thetolerance will be adjusted based on the optimality of the currentiterate, which can speed up the optimization process, but is not alwaysreliable.**max_iter**None or int, optionalMaximum number of iterations before termination. If None (default), itis set to 100 for

`method='trf'`

or to the number of variables for`method='bvls'`

(not counting iterations for ‘bvls’ initialization).**verbose**{0, 1, 2}, optionalLevel of algorithm’s verbosity:

0 : work silently (default).

1 : display a termination report.

2 : display progress during iterations.

**lsmr_maxiter**None or int, optionalMaximum number of iterations for the lsmr least squares solver,if it is used (by setting

`lsq_solver='lsmr'`

). If None (default), ituses lsmr’s default of`min(m, n)`

where`m`

and`n`

are thenumber 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,)Solution found.

**cost**floatValue of the cost function at the solution.

**fun**ndarray, shape (m,)Vector of residuals at the solution.

**optimality**floatFirst-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 asequence of strictly feasible iterates and active_mask is determinedwithin a tolerance threshold.**unbounded_sol**tupleUnbounded least squares solution tuple returned by the least squaressolver (set with

*lsq_solver*option). If*lsq_solver*is not set or isset to`'exact'`

, the tuple contains an ndarray of shape (n,) withthe unbounded solution, an ndarray with the sum of squared residuals,an int with the rank of*A*, and an ndarray with the singular valuesof*A*(see NumPy’s`linalg.lstsq`

for more information). If*lsq_solver*is set to`'lsmr'`

, the tuple contains an ndarray ofshape (n,) with the unbounded solution, an int with the exit code,an int with the number of iterations, and five floats withvarious norms and the condition number of*A*(see SciPy’s`sparse.linalg.lsmr`

for more information). This output can beuseful for determining the convergence of the least squares solver,particularly the iterative`'lsmr'`

solver. The unbounded leastsquares problem is to minimize`0.5 * ||A x - b||**2`

.**nit**intNumber of iterations. Zero if the unconstrained solution is optimal.

**status**intReason for algorithm termination:

-1 : the algorithm was not able to make progress on the lastiteration.

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.

**message**strVerbal description of the termination reason.

**success**boolTrue if one of the convergence criteria is satisfied (

*status*> 0).

See also

- nnls
Linear least squares with non-negativity constraint.

- least_squares
Nonlinear least squares with bounds on the variables.

Notes

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 thebounds.Method ‘trf’ runs the adaptation of the algorithm described in [STIR] fora linear least-squares problem. The iterations are essentially the same asin the nonlinear least-squares algorithm, but as the quadratic functionmodel is always accurate, we don’t need to track or modify the radius ofa trust region. The line search (backtracking) is used as a safety netwhen a selected step does not decrease the cost function. Read moredetailed 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, oneach iteration chooses a new variable to move from the active set to thefree set and then solves the unconstrained least-squares problem on freevariables. This algorithm is guaranteed to give an accurate solutioneventually, but may require up to n iterations for a problem with nvariables. Additionally, an ad-hoc initialization procedure isimplemented, that determines which variables to set free or activeinitially. It takes some number of iterations before actual BVLS starts,but can significantly reduce the number of further iterations.

References

[STIR]

M. A. Branch, T. F. Coleman, and Y. Li, “A Subspace, Interior,and Conjugate Gradient Method for Large-Scale Bound-ConstrainedMinimization Problems,” SIAM Journal on Scientific Computing,Vol. 21, Number 1, pp 1-23, 1999.

[BVLS]

P. B. Start and R. L. Parker, “Bounded-Variable Least-Squares:an Algorithm and Applications”, Computational Statistics, 10,129-141, 1995.

Examples

In this example, a problem with a large sparse matrix and bounds on thevariables 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 varyThe 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.