NAG CL Interface
e04pcc (bnd_​lin_​lsq)

1 Purpose

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

2 Specification

#include <nag.h>
void  e04pcc (Nag_RegularizedType itype, Integer m, Integer n, double a[], Integer pda, double b[], const double bl[], const double bu[], double tol, double x[], double *rnorm, Integer *nfree, double w[], Integer indx[], NagError *fail)
The function may be called by the names: e04pcc or nag_opt_bnd_lin_lsq.

3 Description

Given an m by n matrix A, an n-vector l of lower bounds, an n-vector u of upper bounds, and an m-vector b, e04pcc computes an n-vector x that solves the least squares problem Ax=b subject to xi satisfying li xi ui .
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.

4 References

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

5 Arguments

1: itype Nag_RegularizedType Input
On entry: provides the choice of returning a regularized solution if the matrix is not of full rank.
itype=Nag_Regularized
Specifies that a regularized solution is to be computed.
itype=Nag_NotRegularized
Specifies that no regularization is to take place.
Suggested value: unless there is a definite need for a minimal length solution we recommend that itype=Nag_NotRegularized is used.
Constraint: itype=Nag_Regularized or Nag_NotRegularized.
2: m Integer Input
On entry: m, the number of linear equations.
Constraint: m0.
3: n Integer Input
On entry: n, the number of variables.
Constraint: n0.
4: a[pda×n] double Input/Output
Note: the i,jth element of the matrix A is stored in a[j-1×pda+i-1].
On entry: the m by n matrix A.
On exit: if itype=Nag_NotRegularized, a contains the product matrix QA, where Q is an m by m orthogonal matrix generated by e04pcc; otherwise a is unchanged.
5: pda Integer Input
On entry: the stride separating matrix row elements in the array a.
Constraint: pdam.
6: b[m] double Input/Output
On entry: the right-hand side vector b.
On exit: if itype=Nag_NotRegularized, the product of Q times the original vector b, where Q is as described in argument a; otherwise b is unchanged.
7: bl[n] const double Input
8: bu[n] const double Input
On entry: bl[i-1] and bu[i-1] must specify the lower and upper bounds, li and ui respectively, to be imposed on the solution vector xi.
Constraint: bl[i-1] bu[i-1], for i=1,2,,n.
9: tol double 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 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 machine precision is recommended (see X02AJC).
If on entry tol<machine precision, machine precision is used.
Suggested value: tol=0.0
10: x[n] double Output
On exit: the solution vector x.
11: rnorm double * Output
On exit: the Euclidean norm of the residual vector b-Ax.
12: nfree Integer * Output
On exit: indicates the number of components of the solution vector that are not at one of the constraints.
13: w[n] double Output
On exit: 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 xi 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=Nag_NotRegularized. However a matrix may have less than full rank without w[i-1] being set to -999.0. If itype=Nag_NotRegularized, 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=Nag_Regularized. Otherwise the values of w[i-1] have the following meaning:
w[i-1]=0
if xi is unconstrained.
w[i-1]<0
if xi is constrained by its lower bound.
w[i-1]>0
if xi is constrained by its upper bound.
w[i-1]
may be any value if li=ui.
14: indx[n] Integer Output
On exit: the contents of this array describe the components of the solution vector as follows:
indx[i-1], for i=1,2,,nfree
These elements of the solution have not hit a constraint; i.e., w[i-1]=0.
indx[i-1], for i=nfree+1,,k
These elements of the solution have been constrained by either the lower or upper bound.
indx[i-1], for i=k+1 ,,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.)
15: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_CONVERGENCE
The function failed to converge in 3×n iterations. This is not expected. Please contact NAG.
NE_INT
On entry, m=value.
Constraint: m0.
On entry, n=value.
Constraint: n0.
NE_INT_2
On entry, m=value and pda=value.
Constraint: pdam.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_REAL_2
On entry, when i=value, bl[i-1]=value and bu[i-1]=value.
Constraint: bl[i-1]bu[i-1].

7 Accuracy

Orthogonal rotations are used.

8 Parallelism and Performance

e04pcc 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 function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

If either m or n is zero on entry then e04pcc sets fail.code= NE_NOERROR and simply returns without setting any other output arguments.

10 Example

The example minimizes Ax-b2 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 1x5.

10.1 Program Text

Program Text (e04pcce.c)

10.2 Program Data

Program Data (e04pcce.d)

10.3 Program Results

Program Results (e04pcce.r)