naginterfaces.library.opt.bnd_​lin_​lsq

naginterfaces.library.opt.bnd_lin_lsq(a, b, bl, bu, itype=1, tol=0.0)

bnd_lin_lsq solves a linear least squares problem subject to fixed lower and upper bounds on the variables.

For full information please refer to the NAG Library document for e04pc

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/e04/e04pcf.html

Parameters

afloat, array-like, shape $(m,n)$

The $m\times n$ matrix $A$.

bfloat, array-like, shape $\left(m\right)$

The right-hand side vector $b$.

blfloat, array-like, shape $\left(n\right)$

$bl[\text{i}-1]$ and $bu[\text{i}-1]$ must specify the lower and upper bounds, $l_i$ and $u_i$ respectively, to be imposed on the solution vector $x_i$.

bufloat, array-like, shape $\left(n\right)$

$bl[\text{i}-1]$ and $bu[\text{i}-1]$ must specify the lower and upper bounds, $l_i$ and $u_i$ respectively, to be imposed on the solution vector $x_i$.

itypeint, optional

Provides the choice of returning a regularized solution if the matrix is not of full rank.

$itype=0$

Specifies that a regularized solution is to be computed.

$itype=1$

Specifies that no regularization is to take place.

tolfloat, optional

$tol$ specifies a parameter used to determine the relative linear dependence of a column vector for a variable moved from its initial value. It determines the computational rank of the matrix. Increasing its value from $\sqrt{\text{machine precision}}$ will increase the likelihood of additional elements of $x$ being set to zero. It may be worth experimenting with increasing values of $tol$ to determine whether the nature of the solution, $x$, changes significantly. In practice a value of $\sqrt{\text{machine precision}}$ is recommended (see machine.precision).

If on entry $tol<\sqrt{\text{machine precision}}$, $\sqrt{\text{machine precision}}$ is used.

Returns

afloat, ndarray, shape $(m,n)$

If $itype=1$, $a$ contains the product matrix $QA$, where $Q$ is an $m\times m$ orthogonal matrix generated by bnd_lin_lsq; otherwise, $a$ is unchanged.

bfloat, ndarray, shape $\left(m\right)$

If $itype=1$, the product of $Q$ times the original vector $b$, where $Q$ is as described in argument $a$; otherwise, $b$ is unchanged.

xfloat, ndarray, shape $\left(n\right)$

The solution vector $x$.

rnormfloat

The Euclidean norm of the residual vector $b-Ax$.

nfreeint

Indicates the number of components of the solution vector that are not at one of the constraints.

wfloat, ndarray, shape $\left(n\right)$

Contains the dual solution vector. The magnitude of $w[i-1]$ gives a measure of the improvement in the objective value if the corresponding bound were to be relaxed so that $x_i$ could take different values.

A value of $w[i-1]$ equal to the special value $-999.0$ is indicative of the matrix $A$ not having full rank.

It is only likely to occur when $itype=1$.

However a matrix may have less than full rank without $w[i-1]$ being set to $-999.0$.

If $itype=1$, then the values contained in $w$ (other than those set to $-999.0$) may be unreliable; the corresponding values in $indx$ may likewise be unreliable.

If you have any doubts set $itype=0$.

Otherwise, the values of $w[i-1]$ have the following meaning:

$w[i-1]=0$

if $x_i$ is unconstrained.

$w[i-1]<0$

if $x_i$ is constrained by its lower bound.

$w[i-1]>0$

if $x_i$ is constrained by its upper bound.

$w[i-1]$

may be any value if $l_i=u_i$.

indxint, ndarray, shape $\left(n\right)$

The contents of this array describe the components of the solution vector as follows:

$indx[\text{i}-1]$, for $\text{i}=1,2,\dots ,nfree$

These elements of the solution have not hit a constraint; i.e., $w[i-1]=0$.

$indx[\text{i}-1]$, for $\text{i}=nfree+1,\dots ,k$

These elements of the solution have been constrained by either the lower or upper bound.

$indx[\text{i}-1]$, for $\text{i}=k+1,\dots ,n$

These elements of the solution are fixed by the bounds; i.e., $bl[i-1]=bu[i-1]$.

Here $k$ is determined from $nfree$ and the number of fixed components. (Often the latter will be $0$, so $k$ will be $n-nfree$.)

Raises

NagValueError

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 0$.

(errno $1$)

On entry, $m=⟨value⟩$.

Constraint: $m\ge 0$.

(errno $1$)

On entry, when $i=⟨value⟩$, $bl[i-1]=⟨value⟩$ and $bu[i-1]=⟨value⟩$.

Constraint: $bl[i-1]\le bu[i-1]$.

(errno $1$)

On entry, $m=⟨value⟩$ and $\text{lda}=⟨value⟩$.

Constraint: $\text{lda}\ge m$.

Warns

NagAlgorithmicMajorWarning

(errno $2$)

The function failed to converge in $3\times n$ iterations. This is not expected. Please contact NAG.

Notes

Given an $m\times n$ matrix $A$, an $n$-vector $l$ of lower bounds, an $n$-vector $u$ of upper bounds, and an $m$-vector $b$, bnd_lin_lsq computes an $n$-vector $x$ that solves the least squares problem $Ax=b$ subject to $x_i$ satisfying $l_i\le x_i\le u_i$.

A facility is provided to return a ‘regularized’ solution, which will closely approximate a minimal length solution whenever $A$ is not of full rank. A minimal length solution is the solution to the problem which has the smallest Euclidean norm.

The algorithm works by applying orthogonal transformations to the matrix and to the right-hand side to obtain within the matrix an upper triangular matrix $R$. In general the elements of $x$ corresponding to the columns of $R$ will be the candidate nonzero solutions. If a diagonal element of $R$ is small compared to the other members of $R$ then this is undesirable. $R$ will be nearly singular and the equations for $x$ thus ill-conditioned. You may specify the tolerance used to determine the relative linear dependence of a column vector for a variable moved from its initial value.

References

Lawson, C L and Hanson, R J, 1974, Solving Least Squares Problems, Prentice–Hall