Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_bnd_lin_lsq (e04pc)

## Purpose

nag_bnd_lin_lsq (e04pc) solves a linear least squares problem subject to fixed lower and upper bounds on the variables.

## Syntax

[a, b, x, rnorm, nfree, w, indx, ifail] = e04pc(itype, a, b, bl, bu, 'm', m, 'n', n, 'tol', tol)
[a, b, x, rnorm, nfree, w, indx, ifail] = nag_bnd_lin_lsq(itype, a, b, bl, bu, 'm', m, 'n', n, 'tol', tol)

## Description

Given an m$m$ by n$n$ matrix A$A$, an n$n$-vector l$l$ of lower bounds, an n$n$-vector u$u$ of upper bounds, and an m$m$-vector b$b$, nag_bnd_lin_lsq (e04pc) computes an n$n$-vector x$x$ that solves the least squares problem Ax = b$Ax=b$ subject to xi${x}_{i}$ satisfying li xi ui ${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$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$R$. In general the elements of x$x$ corresponding to the columns of R$R$ will be the candidate non-zero solutions. If a diagonal element of R$R$ is small compared to the other members of R$R$ then this is undesirable. R$R$ will be nearly singular and the equations for x$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

## Parameters

### Compulsory Input Parameters

1:     itype – int64int32nag_int scalar
Provides the choice of returning a regularized solution if the matrix is not of full rank.
itype = 0${\mathbf{itype}}=0$
Specifies that a regularized solution is to be computed.
itype = 1${\mathbf{itype}}=1$
Specifies that no regularization is to take place.
Default: itype = 1${\mathbf{itype}}=1$
Constraint: itype = 0${\mathbf{itype}}=0$ or 1$1$.
2:     a(lda, : $:$) – double array
The first dimension of the array a must be at least m${\mathbf{m}}$
The second dimension of the array must be at least n${\mathbf{n}}$
The m$m$ by n$n$ matrix A$A$.
3:     b(m) – double array
m, the dimension of the array, must satisfy the constraint m0${\mathbf{m}}\ge 0$.
The right-hand side vector b$b$.
4:     bl(n) – double array
5:     bu(n) – double array
n, the dimension of the array, must satisfy the constraint n0${\mathbf{n}}\ge 0$.
bl(i)${\mathbf{bl}}\left(\mathit{i}\right)$ and bu(i)${\mathbf{bu}}\left(\mathit{i}\right)$ must specify the lower and upper bounds, li${l}_{i}$ and ui${u}_{i}$ respectively, to be imposed on the solution vector xi${x}_{i}$.
Constraint: bl(i) bu(i)${\mathbf{bl}}\left(\mathit{i}\right)\le {\mathbf{bu}}\left(\mathit{i}\right)$, for i = 1,2,,n$\mathit{i}=1,2,\dots ,{\mathbf{n}}$.

### Optional Input Parameters

1:     m – int64int32nag_int scalar
Default: The first dimension of the array a and the dimension of the array b. (An error is raised if these dimensions are not equal.)
m$m$, the number of linear equations.
Constraint: m0${\mathbf{m}}\ge 0$.
2:     n – int64int32nag_int scalar
Default: The second dimension of the array a and the dimension of the arrays bl, bu. (An error is raised if these dimensions are not equal.)
n$n$, the number of variables.
Constraint: n0${\mathbf{n}}\ge 0$.
3:     tol – double scalar
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(machine precision) will increase the likelihood of additional elements of x$x$ being set to zero. It may be worth experimenting with increasing values of tol to determine whether the nature of the solution, x$x$, changes significantly. In practice a value of sqrt(machine precision) is recommended (see nag_machine_precision (x02aj)).
If on entry tol < sqrt(machine precision), then sqrt(machine precision) is used.
Default: tol = 0.0${\mathbf{tol}}=0.0$

lda

### Output Parameters

1:     a(lda, : $:$) – double array
The first dimension of the array a will be m${\mathbf{m}}$
The second dimension of the array will be n${\mathbf{n}}$
ldam$\mathit{lda}\ge {\mathbf{m}}$.
If itype = 1${\mathbf{itype}}=1$, a contains the product matrix QA$QA$, where Q$Q$ is an m$m$ by m$m$ orthogonal matrix generated by nag_bnd_lin_lsq (e04pc); otherwise a is unchanged.
2:     b(m) – double array
If itype = 1${\mathbf{itype}}=1$, the product of Q$Q$ times the original vector b$b$, where Q$Q$ is as described in parameter a; otherwise b is unchanged.
3:     x(n) – double array
The solution vector x$x$.
4:     rnorm – double scalar
The Euclidean norm of the residual vector bAx$b-Ax$.
5:     nfree – int64int32nag_int scalar
Indicates the number of components of the solution vector that are not at one of the constraints.
6:     w(n) – double array
Contains the dual solution vector. The magnitude of w(i)${\mathbf{w}}\left(i\right)$ gives a measure of the improvement in the objective value if the corresponding bound were to be relaxed so that xi${x}_{i}$ could take different values.
A value of w(i)${\mathbf{w}}\left(i\right)$ equal to the special value 999.0$-999.0$ is indicative of the matrix A$A$ not having full rank. It is only likely to occur when itype = 1${\mathbf{itype}}=1$. However a matrix may have less than full rank without w(i)${\mathbf{w}}\left(i\right)$ being set to 999.0$-999.0$. If itype = 1${\mathbf{itype}}=1$ then the values contained in w (other than those set to 999.0$-999.0$) may be unreliable; the corresponding values in indx may likewise be unreliable. If you have any doubts set itype = 0${\mathbf{itype}}=0$. Otherwise the values of w(i)${\mathbf{w}}\left(i\right)$ have the following meaning:
w(i) = 0${\mathbf{w}}\left(i\right)=0$
if xi${x}_{i}$ is unconstrained.
w(i) < 0${\mathbf{w}}\left(i\right)<0$
if xi${x}_{i}$ is constrained by its lower bound.
w(i) > 0${\mathbf{w}}\left(i\right)>0$
if xi${x}_{i}$ is constrained by its upper bound.
w(i)${\mathbf{w}}\left(i\right)$
may be any value if li = ui${l}_{i}={u}_{i}$.
7:     indx(n) – int64int32nag_int array
The contents of this array describe the components of the solution vector as follows:
indx(i)${\mathbf{indx}}\left(\mathit{i}\right)$, for i = 1,2,,nfree$\mathit{i}=1,2,\dots ,{\mathbf{nfree}}$
These elements of the solution have not hit a constraint; i.e., w(i) = 0${\mathbf{w}}\left(i\right)=0$.
indx(i)${\mathbf{indx}}\left(\mathit{i}\right)$, for i = nfree + 1,,k$\mathit{i}={\mathbf{nfree}}+1,\dots ,k$
These elements of the solution have been constrained by either the lower or upper bound.
indx(i)${\mathbf{indx}}\left(\mathit{i}\right)$, for i = k + 1 ,,n$\mathit{i}=k+1,\dots ,{\mathbf{n}}$
These elements of the solution are fixed by the bounds; i.e., bl(i) = bu(i)${\mathbf{bl}}\left(i\right)={\mathbf{bu}}\left(i\right)$.
Here k$k$ is determined from nfree and the number of fixed components. (Often the latter will be 0$0$, so k$k$ will be ${\mathbf{n}}-{\mathbf{nfree}}$.)
8:     ifail – int64int32nag_int scalar
${\mathrm{ifail}}={\mathbf{0}}$ unless the function detects an error (see [Error Indicators and Warnings]).

## Error Indicators and Warnings

Note: nag_bnd_lin_lsq (e04pc) may return useful information for one or more of the following detected errors or warnings.
Errors or warnings detected by the function:
ifail = 1${\mathbf{ifail}}=1$
Constraint: bl(i)bu(i)${\mathbf{bl}}\left(i\right)\le {\mathbf{bu}}\left(i\right)$.
Constraint: ldam$\mathit{lda}\ge {\mathbf{m}}$.
Constraint: m0${\mathbf{m}}\ge 0$.
Constraint: n0${\mathbf{n}}\ge 0$.
ifail = 2${\mathbf{ifail}}=2$
The function failed to converge in 3 × n$3×n$ iterations. This is not expected. Please contact NAG.
ifail = 999${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

## Accuracy

Orthogonal rotations are used.

If either m or n is zero on entry then nag_bnd_lin_lsq (e04pc) sets ${\mathbf{ifail}}={\mathbf{0}}$ and simply returns without setting any other output parameters.

## Example

```function nag_bnd_lin_lsq_example
a = [0.05, 0.05, 0.25,-0.25;
0.25, 0.25, 0.05,-0.05;
0.35, 0.35, 1.75,-1.75;
1.75, 1.75, 0.35,-0.35;
0.30,-0.30, 0.30, 0.30;
0.40,-0.40, 0.40, 0.40];
b = [1,  2,  3,  4,  5,  6,];
bl = [1, 1, 1, 1];
bu = [5, 5, 5, 5];
itype = int64(1);

[a, b, x, rnorm, nfree, w, indx, ifail] = ...
nag_bnd_lin_lsq(itype, a, b, bl, bu);
fprintf('\nSolution vector:\n');
disp(x');
fprintf('Dual Solution:\n');
disp(w');
fprintf('Residual: %9.4f\n', rnorm);
```
```

Solution vector:
1.8133    1.0000    5.0000    4.3467

Dual Solution:
0   -2.7200    2.7200         0

Residual:    3.4246

```
```function e04pc_example
a = [0.05, 0.05, 0.25,-0.25;
0.25, 0.25, 0.05,-0.05;
0.35, 0.35, 1.75,-1.75;
1.75, 1.75, 0.35,-0.35;
0.30,-0.30, 0.30, 0.30;
0.40,-0.40, 0.40, 0.40];
b = [1,  2,  3,  4,  5,  6,];
bl = [1, 1, 1, 1];
bu = [5, 5, 5, 5];
itype = int64(1);

[a, b, x, rnorm, nfree, w, indx, ifail] = e04pc(itype, a, b, bl, bu);
fprintf('\nSolution vector:\n');
disp(x');
fprintf('Dual Solution:\n');
disp(w');
fprintf('Residual: %9.4f\n', rnorm);
```
```

Solution vector:
1.8133    1.0000    5.0000    4.3467

Dual Solution:
0   -2.7200    2.7200         0

Residual:    3.4246

```