# NAG FL Interfacee04pcf (bnd_​lin_​lsq)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

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

## 2Specification

Fortran Interface
 Subroutine e04pcf ( m, n, a, lda, b, bl, bu, tol, x, w, indx,
 Integer, Intent (In) :: itype, m, n, lda Integer, Intent (Inout) :: ifail Integer, Intent (Out) :: nfree, indx(n) Real (Kind=nag_wp), Intent (In) :: bl(n), bu(n), tol Real (Kind=nag_wp), Intent (Inout) :: a(lda,*), b(m) Real (Kind=nag_wp), Intent (Out) :: x(n), rnorm, w(n)
#include <nag.h>
 void e04pcf_ (const Integer *itype, const Integer *m, const Integer *n, double a[], const Integer *lda, double b[], const double bl[], const double bu[], const double *tol, double x[], double *rnorm, Integer *nfree, double w[], Integer indx[], Integer *ifail)
The routine may be called by the names e04pcf or nagf_opt_bnd_lin_lsq.

## 3Description

Given an $m×n$ matrix $A$, an $n$-vector $l$ of lower bounds, an $n$-vector $u$ of upper bounds, and an $m$-vector $b$, e04pcf 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.

## 4References

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

## 5Arguments

1: $\mathbf{itype}$Integer Input
On entry: provides the choice of returning a regularized solution if the matrix is not of full rank.
${\mathbf{itype}}=0$
Specifies that a regularized solution is to be computed.
${\mathbf{itype}}=1$
Specifies that no regularization is to take place.
Suggested value: unless there is a definite need for a minimal length solution we recommend that ${\mathbf{itype}}=1$ is used.
Constraint: ${\mathbf{itype}}=0$ or $1$.
2: $\mathbf{m}$Integer Input
On entry: $m$, the number of linear equations.
Constraint: ${\mathbf{m}}\ge 0$.
3: $\mathbf{n}$Integer Input
On entry: $n$, the number of variables.
Constraint: ${\mathbf{n}}\ge 0$.
4: $\mathbf{a}\left({\mathbf{lda}},*\right)$Real (Kind=nag_wp) array Input/Output
Note: the second dimension of the array a must be at least ${\mathbf{n}}$.
On entry: the $m×n$ matrix $A$.
On exit: if ${\mathbf{itype}}=1$, a contains the product matrix $QA$, where $Q$ is an $m×m$ orthogonal matrix generated by e04pcf; otherwise, a is unchanged.
5: $\mathbf{lda}$Integer Input
On entry: the first dimension of the array a as declared in the (sub)program from which e04pcf is called.
Constraint: ${\mathbf{lda}}\ge {\mathbf{m}}$.
6: $\mathbf{b}\left({\mathbf{m}}\right)$Real (Kind=nag_wp) array Input/Output
On entry: the right-hand side vector $b$.
On exit: if ${\mathbf{itype}}=1$, the product of $Q$ times the original vector $b$, where $Q$ is as described in argument a; otherwise, b is unchanged.
7: $\mathbf{bl}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input
8: $\mathbf{bu}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Input
On entry: ${\mathbf{bl}}\left(\mathit{i}\right)$ and ${\mathbf{bu}}\left(\mathit{i}\right)$ must specify the lower and upper bounds, ${l}_{i}$ and ${u}_{i}$ respectively, to be imposed on the solution vector ${x}_{i}$.
Constraint: ${\mathbf{bl}}\left(\mathit{i}\right)\le {\mathbf{bu}}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.
9: $\mathbf{tol}$Real (Kind=nag_wp) Input
On entry: 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 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 is recommended (see x02ajf).
If on entry , is used.
Suggested value: ${\mathbf{tol}}=0.0$
10: $\mathbf{x}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Output
On exit: the solution vector $x$.
11: $\mathbf{rnorm}$Real (Kind=nag_wp) Output
On exit: the Euclidean norm of the residual vector $b-Ax$.
12: $\mathbf{nfree}$Integer Output
On exit: indicates the number of components of the solution vector that are not at one of the constraints.
13: $\mathbf{w}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Output
On exit: contains the dual solution vector. The magnitude of ${\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 ${x}_{i}$ could take different values.
A value of ${\mathbf{w}}\left(i\right)$ equal to the special value $-999.0$ is indicative of the matrix $A$ not having full rank. It is only likely to occur when ${\mathbf{itype}}=1$. However a matrix may have less than full rank without ${\mathbf{w}}\left(i\right)$ being set to $-999.0$. If ${\mathbf{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 ${\mathbf{itype}}=0$. Otherwise, the values of ${\mathbf{w}}\left(i\right)$ have the following meaning:
${\mathbf{w}}\left(i\right)=0$
if ${x}_{i}$ is unconstrained.
${\mathbf{w}}\left(i\right)<0$
if ${x}_{i}$ is constrained by its lower bound.
${\mathbf{w}}\left(i\right)>0$
if ${x}_{i}$ is constrained by its upper bound.
${\mathbf{w}}\left(i\right)$
may be any value if ${l}_{i}={u}_{i}$.
14: $\mathbf{indx}\left({\mathbf{n}}\right)$Integer array Output
On exit: the contents of this array describe the components of the solution vector as follows:
${\mathbf{indx}}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,{\mathbf{nfree}}$
These elements of the solution have not hit a constraint; i.e., ${\mathbf{w}}\left(i\right)=0$.
${\mathbf{indx}}\left(\mathit{i}\right)$, for $\mathit{i}={\mathbf{nfree}}+1,\dots ,k$
These elements of the solution have been constrained by either the lower or upper bound.
${\mathbf{indx}}\left(\mathit{i}\right)$, for $\mathit{i}=k+1,\dots ,{\mathbf{n}}$
These elements of the solution are fixed by the bounds; i.e., ${\mathbf{bl}}\left(i\right)={\mathbf{bu}}\left(i\right)$.
Here $k$ is determined from nfree and the number of fixed components. (Often the latter will be $0$, so $k$ will be ${\mathbf{n}}-{\mathbf{nfree}}$.)
15: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $-1$ is recommended since useful values can be provided in some output arguments even when ${\mathbf{ifail}}\ne {\mathbf{0}}$ on exit. When the value $-\mathbf{1}$ or $\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
Note: in some cases e04pcf may return useful information.
${\mathbf{ifail}}=1$
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}\ge 0$.
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{lda}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{lda}}\ge {\mathbf{m}}$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, when $i=⟨\mathit{\text{value}}⟩$, ${\mathbf{bl}}\left(i\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{bu}}\left(i\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{bl}}\left(i\right)\le {\mathbf{bu}}\left(i\right)$.
${\mathbf{ifail}}=2$
The routine failed to converge in $3×n$ iterations. This is not expected. Please contact NAG.
${\mathbf{ifail}}=-99$
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

## 7Accuracy

Orthogonal rotations are used.

## 8Parallelism and Performance

e04pcf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

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

## 10Example

The example minimizes ${‖Ax-b‖}_{2}$ where
 $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 )$
and
 $b = ( 1.0 2.0 3.0 4.0 5.0 6.0 ) T$
subject to $1\le x\le 5$.

### 10.1Program Text

Program Text (e04pcfe.f90)

### 10.2Program Data

Program Data (e04pcfe.d)

### 10.3Program Results

Program Results (e04pcfe.r)