naginterfaces.library.fit.glinc_​l1sol

naginterfaces.library.fit.glinc_l1sol(m, e, f, x, mxs, monit, iprint, data=None)

glinc_l1sol calculates an $l_1$ solution to an overdetermined system of linear equations, possibly subject to linear inequality constraints.

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e02/e02gbf.html

Parameters

mint

The number of equations in the overdetermined system, $m$ (i.e., the number of rows of the matrix $A$).

efloat, array-like, shape $(n,\text{mpl})$

The equation and constraint matrices stored in the following manner.

The first $m$ columns contain the $m$ rows of the matrix $A$; element $e[\text{i}-1,\text{j}-1]$ specifying the element $a_{\text{j}\text{i}}$ in the $\text{j}$th row and $\text{i}$th column of $A$ (the coefficient of the $\text{i}$th unknown in the $\text{j}$th equation), for $\text{j}=1,2,\dots ,m$, for $\text{i}=1,2,\dots ,n$.

The next $l$ columns contain the $l$ rows of the constraint matrix $C$; element $e[\text{i}-1,\text{j}+m-1]$ containing the element $c_{\text{j}\text{i}}$ in the $\text{j}$th row and $\text{i}$th column of $C$ (the coefficient of the $\text{i}$th unknown in the $\text{j}$th constraint), for $\text{j}=1,2,\dots ,l$, for $\text{i}=1,2,\dots ,n$.

ffloat, array-like, shape $\left(\text{mpl}\right)$

$f[\text{i}-1]$, for $\text{i}=1,2,\dots ,m$, must contain $b_{\text{i}}$ (the $\text{i}$th element of the right-hand side vector of the overdetermined system of equations) and $f[m+\text{i}-1]$, for $\text{i}=1,2,\dots ,l$, must contain $d_i$ (the $i$th element of the right-hand side vector of the constraints), where $l$ is the number of constraints.

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

$x[\text{i}-1]$ must contain an estimate of the $\text{i}$th unknown, for $\text{i}=1,2,\dots ,n$. If no better initial estimate for $x[i-1]$ is available, set $x[i-1]=0.0$.

mxsint

The maximum number of steps to be allowed for the solution of the unconstrained problem. Typically this may be a modest multiple of $n$. If, on entry, $mxs$ is zero or negative, the value returned by machine.integer_max is used.

monitcallable monit(x, niter, k, el1n, data=None)

$monit$ can be used to print out the current values of any selection of its arguments.

The frequency with which $monit$ is called in glinc_l1sol is controlled by $iprint$.

Parameters

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

The latest estimate of the unknowns.

niterint

The number of iterations so far carried out.

kint

The total number of equations and constraints which are currently active (i.e., the number of equations with zero residuals plus the number of constraints which are satisfied as equations).

el1nfloat

The $l_1$-norm of the current residuals of the overdetermined system of equations.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

iprintint

The frequency of iteration print out.

$iprint>0$

$monit$ is called every $iprint$ iterations and at the solution.

$iprint=0$

Information is printed out at the solution only. Otherwise $monit$ is not called.

dataarbitrary, optional

User-communication data for callback functions.

Returns

efloat, ndarray, shape $(n,\text{mpl})$

Unchanged, except possibly to the extent of a small multiple of the machine precision. (See Further Comments.)

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

The latest estimate of the $\text{i}$th unknown, for $\text{i}=1,2,\dots ,n$. If no exception or warning is raised on exit, these are the solution values.

kint

The total number of equations and constraints which are then active (i.e., the number of equations with zero residuals plus the number of constraints which are satisfied as equalities).

el1nfloat

The $l_1$-norm (sum of absolute values) of the equation residuals.

indxint, ndarray, shape $\left(\text{mpl}\right)$

Specifies which columns of $e$ relate to the inactive equations and constraints. $indx\left[0\right]$ up to $indx[k-1]$ number the active columns and $indx\left[k\right]$ up to $indx[\text{mpl}-1]$ number the inactive columns.

Raises

NagValueError

(errno $1$)

The constraints cannot all be satisfied simultaneously: they are not compatible with one another. Hence no solution is possible.

(errno $2$)

The limit imposed by $mxs$ has been reached without finding a solution. Consider restarting from the current point by simply calling glinc_l1sol again without changing the arguments.

(errno $3$)

The function has failed because of numerical difficulties; the problem is too ill-conditioned. Consider rescaling the unknowns.

(errno $4$)

Elements $1$ to $m$ of one of the first $\text{mpl}$ columns of the array $e$ are all zero – this corresponds to a zero row in either of the matrices $A$ or $C$.

(errno $4$)

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

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

(errno $4$)

On entry, $m=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $m\ge n$.

(errno $4$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 2$.

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

Given a matrix $A$ with $m$ rows and $n$ columns $(m\ge n)$ and a vector $b$ with $m$ elements, the function calculates an $l_1$ solution to the overdetermined system of equations

$$Ax=b\text{.}$$

That is to say, it calculates a vector $x$, with $n$ elements, which minimizes the $l_1$-norm (the sum of the absolute values) of the residuals

$$r\left(x\right)=\sum _{i=1}^m\left|r_i\right|\text{,}$$

where the residuals $r_i$ are given by

$$r_i=b_i-\sum _{j=1}^n{a}_{ij}{x}_j\text{,}i=1,2,\dots ,m\text{.}$$

Here $a_{ij}$ is the element in row $i$ and column $j$ of $A$, $b_i$ is the $i$th element of $b$ and $x_j$ the $j$th element of $x$.

If, in addition, a matrix $C$ with $l$ rows and $n$ columns and a vector $d$ with $l$ elements, are given, the vector $x$ computed by the function is such as to minimize the $l_1$-norm $r\left(x\right)$ subject to the set of inequality constraints $Cx\ge d$.

The matrices $A$ and $C$ need not be of full rank.

Typically in applications to data fitting, data consisting of $m$ points with coordinates $(t_i,y_i)$ is to be approximated by a linear combination of known functions ${\varphi }_i\left(t\right)$,

$${\alpha }_1{\varphi }_1\left(t\right)+{\alpha }_2{\varphi }_2\left(t\right)+\cdots +{\alpha }_n{\varphi }_n\left(t\right)\text{,}$$

in the $l_1$-norm, possibly subject to linear inequality constraints on the coefficients ${\alpha }_j$ of the form $C\alpha \ge d$ where $\alpha$ is the vector of the ${\alpha }_j$ and $C$ and $d$ are as in the previous paragraph. This is equivalent to finding an $l_1$ solution to the overdetermined system of equations

$$\sum _{j=1}^n{\varphi }_j\left(t_i\right){\alpha }_j=y_i\text{,}i=1,2,\dots ,m\text{,}$$

subject to $C\alpha \ge d$.

Thus if, for each value of $i$ and $j$, the element $a_{ij}$ of the matrix $A$ above is set equal to the value of ${\varphi }_j\left(t_i\right)$ and $b_i$ is equal to $y_i$ and $C$ and $d$ are also supplied to the function, the solution vector $x$ will contain the required values of the ${\alpha }_j$. Note that the independent variable $t$ above can, instead, be a vector of several independent variables (this includes the case where each of ${\varphi }_i$ is a function of a different variable, or set of variables).

The algorithm follows the Conn–Pietrzykowski approach (see Bartels et al. (1978) and Conn and Pietrzykowski (1977)), which is via an exact penalty function

$$g\left(x\right)=\gamma r\left(x\right)-\sum _{i=1}^{l}min(0,c_i^{T}x-d_i)\text{,}$$

where $\gamma$ is a penalty argument, $c_i^T$ is the $i$th row of the matrix $C$, and $d_i$ is the $i$th element of the vector $d$. It proceeds in a step-by-step manner much like the simplex method for linear programming but does not move from vertex to vertex and does not require the problem to be cast in a form containing only non-negative unknowns. It uses stable procedures to update an orthogonal factorization of the current set of active equations and constraints.

References

Bartels, R H, Conn, A R and Charalambous, C, 1976, Minimisation techniques for piecewise Differentiable functions – the $l_{\infty }$ solution to an overdetermined linear system, Technical Report No. 247, CORR 76/30, Mathematical Sciences Department, The John Hopkins University

Bartels, R H, Conn, A R and Sinclair, J W, 1976, A Fortran program for solving overdetermined systems of linear equations in the $l_1$ Sense, Technical Report No. 236, CORR 76/7, Mathematical Sciences Department, The John Hopkins University

Bartels, R H, Conn, A R and Sinclair, J W, 1978, Minimisation techniques for piecewise differentiable functions – the $l_1$ solution to an overdetermined linear system, SIAM J. Numer. Anal. (15), 224–241

Conn, A R and Pietrzykowski, T, 1977, A penalty-function method converging directly to a constrained optimum, SIAM J. Numer. Anal. (14), 348–375