NAG Library Function Document
nag_opt_bnd_lin_lsq (e04pcc) solves a linear least squares problem subject to fixed lower and upper bounds on the variables.
||nag_opt_bnd_lin_lsq (Nag_RegularizedType itype,
const double bl,
const double bu,
Given an by matrix , an -vector of lower bounds, an -vector of upper bounds, and an -vector , nag_opt_bnd_lin_lsq (e04pcc) computes an -vector that solves the least squares problem subject to satisfying .
A facility is provided to return a ‘regularized’ solution, which will closely approximate a minimal length solution whenever 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 . In general the elements of corresponding to the columns of will be the candidate non-zero solutions. If a diagonal element of is small compared to the other members of then this is undesirable. will be nearly singular and the equations for 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.
Lawson C L and Hanson R J (1974) Solving Least Squares Problems Prentice–Hall
itype – Nag_RegularizedTypeInput
: provides the choice of returning a regularized solution if the matrix is not of full rank.
- Specifies that a regularized solution is to be computed.
- Specifies that no regularization is to take place.
unless there is a definite need for a minimal length solution we recommend that is used.
m – IntegerInput
On entry: , the number of linear equations.
n – IntegerInput
On entry: , the number of variables.
a – doubleInput/Output
Note: the th element of the matrix is stored in .
On entry: the by matrix .
contains the product matrix
orthogonal matrix generated by nag_opt_bnd_lin_lsq (e04pcc); otherwise a
pda – IntegerInput
: the stride separating matrix row elements in the array a
b[m] – doubleInput/Output
On entry: the right-hand side vector .
, the product of
times the original vector
is as described in argument a
; otherwise b
bl[n] – const doubleInput
bu[n] – const doubleInput
On entry: and must specify the lower and upper bounds, and respectively, to be imposed on the solution vector .
, for .
tol – doubleInput
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
being set to zero. It may be worth experimenting with increasing values of tol
to determine whether the nature of the solution,
, changes significantly. In practice a value of
is recommended (see nag_machine_precision (X02AJC)
If on entry , then is used.
x[n] – doubleOutput
On exit: the solution vector .
rnorm – double *Output
On exit: the Euclidean norm of the residual vector .
nfree – Integer *Output
On exit: indicates the number of components of the solution vector that are not at one of the constraints.
w[n] – doubleOutput
: contains the dual solution vector. The magnitude of
gives a measure of the improvement in the objective value if the corresponding bound were to be relaxed so that
could take different values.
A value of
equal to the special value
is indicative of the matrix
not having full rank. It is only likely to occur when
. However a matrix may have less than full rank without
being set to
then the values contained in w
(other than those set to
) may be unreliable; the corresponding values in indx
may likewise be unreliable. If you have any doubts set
. Otherwise the values of
have the following meaning:
- if is unconstrained.
- if is constrained by its lower bound.
- if is constrained by its upper bound.
- may be any value if .
indx[n] – IntegerOutput
: the contents of this array describe the components of the solution vector as follows:
- , for
- These elements of the solution have not hit a constraint; i.e., .
- , for
- These elements of the solution have been constrained by either the lower or upper bound.
- , for
- These elements of the solution are fixed by the bounds; i.e., .
is determined from nfree
and the number of fixed components. (Often the latter will be
fail – NagError *Input/Output
The NAG error argument (see Section 3.6
in the Essential Introduction).
6 Error Indicators and Warnings
Dynamic memory allocation failed.
On entry, argument had an illegal value.
The function failed to converge in
iterations. This is not expected. Please contact NAG
On entry, .
On entry, .
On entry, and .
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
On entry, when , and .
Orthogonal rotations are used.
8 Parallelism and Performance
nag_opt_bnd_lin_lsq (e04pcc) is not threaded by NAG in any implementation.
nag_opt_bnd_lin_lsq (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 Users' Note
for your implementation for any additional implementation-specific information.
If either m
is zero on entry then nag_opt_bnd_lin_lsq (e04pcc) sets
NE_NOERROR and simply returns without setting any other output arguments.
The example minimizes
10.1 Program Text
Program Text (e04pcce.c)
10.2 Program Data
Program Data (e04pcce.d)
10.3 Program Results
Program Results (e04pcce.r)