NAG Library Routine Document

E04NCF/E04NCA

1  Purpose

2  Specification

2.1  Specification for E04NCF

2.2  Specification for E04NCA

3  Description

4  References

5  Parameters

1:     M – INTEGERInput

On entry: $m$, the number of rows in the matrix $A$. If the problem is specified as type FP or LP, M is not referenced and is assumed to be zero.

If the problem is of type QP, M will usually be $n$, the number of variables. However, a value of M less than $n$ is appropriate for QP3 or QP4 if $A$ is an upper trapezoidal matrix with $m$ rows. Similarly, M may be used to define the dimension of a leading block of nonzeros in the Hessian matrices of QP1 or QP2, in which case the last $\left(n-m\right)$ rows and columns of A are assumed to be zero. In the QP case, $m$ should not be greater than $n$; if it is, the last $\left(m-n\right)$ rows of $A$ are ignored.

If the problem is of type LS1 (the default) or specified as type LS2, LS3 or LS4, M is also the dimension of the array B. Note that all possibilities ($m<n$, $m=n$ and $m>n$) are allowed in this case.

Constraint: $\mathbf{M}>0$ if the problem is not of type FP or LP.

2:     N – INTEGERInput

On entry: $n$, the number of variables.

Constraint: $\mathbf{N}>0$.

3:     NCLIN – INTEGERInput

On entry: $n_L$, the number of general linear constraints.

Constraint: $\mathbf{NCLIN}\ge 0$.

4:     LDC – INTEGERInput

On entry: the first dimension of the array C as declared in the (sub)program from which E04NCF/E04NCA is called.

Constraint: $\mathbf{LDC}\ge \max \left(1,\mathbf{NCLIN}\right)$.

5:     LDA – INTEGERInput

On entry: the first dimension of the array A as declared in the (sub)program from which E04NCF/E04NCA is called.

Constraint: $\mathbf{LDA}\ge \max \left(1,\mathbf{M}\right)$.

6:     C(LDC,$*$) – REAL (KIND=nag_wp) arrayInput

Note: the second dimension of the array C must be at least $\mathbf{N}$ if $\mathbf{NCLIN}>0$, and at least $1$ otherwise.

On entry: the $\mathit{i}$th row of C must contain the coefficients of the $\mathit{i}$th general constraint, for $\mathit{i}=1,2,\dots ,\mathbf{NCLIN}$.

If $\mathbf{NCLIN}=0$, C is not referenced.

7:     BL($\mathbf{N}+\mathbf{NCLIN}$) – REAL (KIND=nag_wp) arrayInput

8:     BU($\mathbf{N}+\mathbf{NCLIN}$) – REAL (KIND=nag_wp) arrayInput

On entry: BL must contain the lower bounds and BU the upper bounds, for all the constraints, in the following order. The first $n$ elements of each array must contain the bounds on the variables, and the next $n_L$ elements must contain the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., $l_j=-\infty$), set $\mathbf{BL}\left(j\right)\le -\mathit{bigbnd}$, and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $\mathbf{BU}\left(j\right)\ge \mathit{bigbnd}$; the default value of $\mathit{bigbnd}$ is ${10}^{20}$, but this may be changed by the optional parameter Infinite Bound Size. To specify the $j$th constraint as an equality, set $\mathbf{BU}\left(j\right)=\mathbf{BL}\left(j\right)=\beta$, say, where $\left|\beta \right|<\mathit{bigbnd}$.

Constraints:

• $\mathbf{BL}\left(\mathit{j}\right)\le \mathbf{BU}\left(\mathit{j}\right)$, for $\mathit{j}=1,2,\dots ,\mathbf{N}+\mathbf{NCLIN}$;
• if $\mathbf{BL}\left(j\right)=\mathbf{BU}\left(j\right)=\beta$, $\left|\beta \right|<\mathit{bigbnd}$.

9:     CVEC($*$) – REAL (KIND=nag_wp) arrayInput

Note: the dimension of the array CVEC must be at least $\mathbf{N}$ if the problem is of type LP, QP2, QP4, LS2 or LS4, and at least $1$ otherwise.

On entry: the coefficients of the explicit linear term of the objective function.

If the problem is of type FP, QP1, QP3, LS1 (the default) or LS3, CVEC is not referenced.

10:   ISTATE($\mathbf{N}+\mathbf{NCLIN}$) – INTEGER arrayInput/Output

On entry: need not be set if the (default) optional parameter Cold Start is used.

If the optional parameter Warm Start has been chosen, ISTATE specifies the desired status of the constraints at the start of the feasibility phase. More precisely, the first $n$ elements of ISTATE refer to the upper and lower bounds on the variables, and the next $n_L$ elements refer to the general linear constraints (if any). Possible values for $\mathbf{ISTATE}\left(j\right)$ are as follows:

$\mathbf{ISTATE}\left(j\right)$	Meaning
0	The constraint should not be in the initial working set.
1	The constraint should be in the initial working set at its lower bound.
2	The constraint should be in the initial working set at its upper bound.
3	The constraint should be in the initial working set as an equality. This value must not be specified unless $\mathbf{BL}\left(j\right)=\mathbf{BU}\left(j\right)$.

The values $-2$, $-1$ and $4$ are also acceptable but will be reset to zero by the routine. If E04NCF/E04NCA has been called previously with the same values of N and NCLIN, ISTATE already contains satisfactory information. (See also the description of the optional parameter Warm Start.) The routine also adjusts (if necessary) the values supplied in X to be consistent with ISTATE.

Constraint: $-2\le \mathbf{ISTATE}\left(\mathit{j}\right)\le 4$, for $\mathit{j}=1,2,\dots ,\mathbf{N}+\mathbf{NCLIN}$.

On exit: the status of the constraints in the working set at the point returned in X. The significance of each possible value of $\mathbf{ISTATE}\left(j\right)$ is as follows:

$\mathbf{ISTATE}\left(j\right)$	Meaning
$-2$	The constraint violates its lower bound by more than the feasibility tolerance.
$-1$	The constraint violates its upper bound by more than the feasibility tolerance.
$\phantom{-}0$	The constraint is satisfied to within the feasibility tolerance, but is not in the working set.
$\phantom{-}1$	This inequality constraint is included in the working set at its lower bound.
$\phantom{-}2$	This inequality constraint is included in the working set at its upper bound.
$\phantom{-}3$	The constraint is included in the working set as an equality. This value of ISTATE can occur only when $\mathbf{BL}\left(j\right)=\mathbf{BU}\left(j\right)$.
$\phantom{-}4$	This corresponds to optimality being declared with $\mathbf{X}\left(j\right)$ being temporarily fixed at its current value.

11:   KX(N) – INTEGER arrayInput/Output

On entry: need not be initialized for problems of type FP, LP, QP1, QP2, LS1 (the default) or LS2.

For problems QP3, QP4, LS3 or LS4, KX must specify the order of the columns of the matrix $A$ with respect to the ordering of X. Thus if column $j$ of $A$ is the column associated with the variable $x_i$ then $\mathbf{KX}\left(j\right)=i$.

Constraints:

• $1\le \mathbf{KX}\left(\mathit{i}\right)\le \mathbf{N}$, for $\mathit{i}=1,2,\dots ,\mathbf{N}$;
• if $i\ne j$, $\mathbf{KX}\left(i\right)\ne \mathbf{KX}\left(j\right)$.

On exit: defines the order of the columns of A with respect to the ordering of X, as described above.

12:   X(N) – REAL (KIND=nag_wp) arrayInput/Output

On entry: an initial estimate of the solution.

Note: that it may be best to avoid the choice $\mathbf{X}=0.0$.

On exit: the point at which E04NCF/E04NCA terminated. If $\mathbf{IFAIL}=\mathbf{0}$, $\mathbf{1}$ or $\mathbf{4}$, X contains an estimate of the solution.

13:   A(LDA,$*$) – REAL (KIND=nag_wp) arrayInput/Output

Note: the second dimension of the array A must be at least $\mathbf{N}$ if the problem is of type QP1, QP2, QP3, QP4, LS1 (the default), LS2, LS3 or LS4, and at least $1$ otherwise.

On entry: the array A must contain the matrix $A$ as specified in Table 1 (see Section 3).

If the problem is of type QP1 or QP2, the first $m$ rows and columns of A must contain the leading $m$ by $m$ rows and columns of the symmetric Hessian matrix. Only the diagonal and upper triangular elements of the leading $m$ rows and columns of A are referenced. The remaining elements are assumed to be zero and need not be assigned.

For problems QP3, QP4, LS3 or LS4, the first $m$ rows of A must contain an $m$ by $n$ upper trapezoidal factor of either the Hessian matrix or the least squares matrix, ordered according to the KX array. The factor need not be of full rank, i.e., some of the diagonals may be zero. However, as a general rule, the larger the dimension of the leading nonsingular sub-matrix of $A$, the fewer iterations will be required. Elements outside the upper triangular part of the first $m$ rows of A are assumed to be zero and need not be assigned.

If a constrained least squares problem contains a very large number of observations, storage limitations may prevent storage of the entire least squares matrix. In such cases, you should transform the original $A$ into a triangular matrix before the call to E04NCF/E04NCA and solve the problem as type LS3 or LS4.

On exit: if $\mathbf{Hessian}=\mathrm{NO}$ and the problem is of type LS or QP, A contains the upper triangular Cholesky factor $R$ of (8) (see Section 10.3), with columns ordered as indicated by KX. If $\mathbf{Hessian}=\mathrm{YES}$ and the problem is of type LS or QP, A contains the upper triangular Cholesky factor $R$ of the Hessian matrix $H$, with columns ordered as indicated by KX. In either case $R$ may be used to obtain the variance-covariance matrix or to recover the upper triangular factor of the original least squares matrix.

If the problem is of type FP or LP, A is not referenced.

14:   B($*$) – REAL (KIND=nag_wp) arrayInput/Output

Note: the dimension of the array B must be at least $\mathbf{M}$ if the problem is of type LS1 (the default), LS2, LS3 or LS4, and at least $1$ otherwise.

On entry: the $m$ elements of the vector of observations.

On exit: the transformed residual vector of equation (10) (see Section 10.3).

If the problem is of type FP, LP, QP1, QP2, QP3 or QP4, B is not referenced.

15:   ITER – INTEGEROutput

On exit: the total number of iterations performed.

16:   OBJ – REAL (KIND=nag_wp)Output

On exit: the value of the objective function at $x$ if $x$ is feasible, or the sum of infeasibiliites at $x$ otherwise. If the problem is of type FP and $x$ is feasible, OBJ is set to zero.

17:   CLAMDA($\mathbf{N}+\mathbf{NCLIN}$) – REAL (KIND=nag_wp) arrayOutput

On exit: the values of the Lagrange multipliers for each constraint with respect to the current working set. The first $n$ elements contain the multipliers for the bound constraints on the variables, and the next $n_L$ elements contain the multipliers for the general linear constraints (if any). If $\mathbf{ISTATE}\left(j\right)=0$ (i.e., constraint $j$ is not in the working set), $\mathbf{CLAMDA}\left(j\right)$ is zero. If $x$ is optimal, $\mathbf{CLAMDA}\left(j\right)$ should be non-negative if $\mathbf{ISTATE}\left(j\right)=1$, non-positive if $\mathbf{ISTATE}\left(j\right)=2$ and zero if $\mathbf{ISTATE}\left(j\right)=4$.

18:   IWORK(LIWORK) – INTEGER arrayWorkspace

19:   LIWORK – INTEGERInput

On entry: the dimension of the array IWORK as declared in the (sub)program from which E04NCF/E04NCA is called.

Constraint: $\mathbf{LIWORK}\ge \mathbf{N}$.

20:   WORK(LWORK) – REAL (KIND=nag_wp) arrayWorkspace

21:   LWORK – INTEGERInput

On entry: the dimension of the array WORK as declared in the (sub)program from which E04NCF/E04NCA is called.

Constraints:

• if the problem is of type FP,
  • if $\mathbf{NCLIN}=0$, $\mathbf{LWORK}\ge 6\times \mathbf{N}$;
  • if $\mathbf{NCLIN}\ge \mathbf{N}$, $\mathbf{LWORK}\ge 2\times {\mathbf{N}}^2+6\times \mathbf{N}+6\times \mathbf{NCLIN}$;
  • otherwise $\mathbf{LWORK}\ge 2\times {\left(\mathbf{NCLIN}+1\right)}^2+6\times \mathbf{N}+6\times \mathbf{NCLIN}$;
• if the problem is of type LP,
  • if $\mathbf{NCLIN}=0$, $\mathbf{LWORK}\ge 7\times \mathbf{N}$;
  • if $\mathbf{NCLIN}\ge \mathbf{N}$, $\mathbf{LWORK}\ge 2\times {\mathbf{N}}^2+7\times \mathbf{N}+6\times \mathbf{NCLIN}$;
  • otherwise $\mathbf{LWORK}\ge 2\times {\left(\mathbf{NCLIN}+1\right)}^2+7\times \mathbf{N}+6\times \mathbf{NCLIN}$;
• if problems QP1, QP3, LS1 (the default) and LS3,
  • if $\mathbf{NCLIN}>0$, $\mathbf{LWORK}\ge 2\times {\mathbf{N}}^2+9\times \mathbf{N}+6\times \mathbf{NCLIN}$;
  • if $\mathbf{NCLIN}=0$, $\mathbf{LWORK}\ge 9\times \mathbf{N}$;
• if problems QP2, QP4, LS2 and LS4,
  • if $\mathbf{NCLIN}>0$, $\mathbf{LWORK}\ge 2\times {\mathbf{N}}^2+10\times \mathbf{N}+6\times \mathbf{NCLIN}$;
  • if $\mathbf{NCLIN}=0$, $\mathbf{LWORK}\ge 10\times \mathbf{N}$.

The amounts of workspace provided and required are (by default) output on the current advisory message unit (as defined by X04ABF). As an alternative to computing LIWORK and LWORK from the formulas given above, you may prefer to obtain appropriate values from the output of a preliminary run with LIWORK and LWORK set to $1$. (E04NCF/E04NCA will then terminate with $\mathbf{IFAIL}=\mathbf{6}$.)

22:   IFAIL – INTEGERInput/Output

Note: for E04NCA, IFAIL does not occur in this position in the parameter list. See the additional parameters described below.

On entry: IFAIL must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ or }1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, because for this routine the values of the output parameters may be useful even if $\mathbf{IFAIL}\ne \mathbf{0}$ on exit, the recommended value is $-1$. When the value $-\mathbf{1}\text{ or }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).

E04NCF/E04NCA returns with $\mathbf{IFAIL}=\mathbf{0}$ if $x$ is a strong local minimizer, i.e., the projected gradient (Norm Gz; see Section 8.2) is negligible, the Lagrange multipliers (Lagr Mult; see Section 10.2) are optimal and $R_Z$ (see Section 10.3) is nonsingular.

Note: the following are additional parameters for specific use with E04NCA. Users of E04NCF therefore need not read the remainder of this description.

22:   LWSAV($120$) – LOGICAL arrayCommunication Array

23:   IWSAV($610$) – INTEGER arrayCommunication Array

24:   RWSAV($475$) – REAL (KIND=nag_wp) arrayCommunication Array

The arrays LWSAV, IWSAV and RWSAV must not be altered between calls to any of the routines E04NCA, E04NDA or E04NEA.

25:   IFAIL – INTEGERInput/Output

Note: see the parameter description for IFAIL above.

6  Error Indicators and Warnings

$\mathbf{IFAIL}=1$

X is a weak local minimum, (i.e., the projected gradient is negligible, the Lagrange multipliers are optimal, but either $R_Z$ (see Section 10.3) is singular, or there is a small multiplier). This means that $x$ is not unique.

$\mathbf{IFAIL}=2$

The solution appears to be unbounded. This value of IFAIL implies that a step as large as Infinite Bound Size ($\text{default value}={10}^{20}$) would have to be taken in order to continue the algorithm. This situation can occur only when $A$ is singular, there is an explicit linear term, and at least one variable has no upper or lower bound.

$\mathbf{IFAIL}=3$

No feasible point was found, i.e., it was not possible to satisfy all the constraints to within the feasibility tolerance. In this case, the constraint violations at the final $x$ will reveal a value of the tolerance for which a feasible point will exist – for example, when the feasibility tolerance for each violated constraint exceeds its Slack (see Section 8.2) at the final point. The modified problem (with an altered feasibility tolerance) may then be solved using a Warm Start. You should check that there are no constraint redundancies. If the data for the constraints are accurate only to the absolute precision $\sigma$, you should ensure that the value of the optional parameter Feasibility Tolerance ($\text{default value}=\sqrt{\epsilon }$, where $\epsilon$ is the machine precision) is greater than $\sigma$. For example, if all elements of $\mathbf{C}$ are of order unity and are accurate only to three decimal places, the Feasibility Tolerance should be at least ${10}^{-3}$.

$\mathbf{IFAIL}=4$

The limiting number of iterations (determined by the optional parameters Feasibility Phase Iteration Limit ($\text{default value}=\max \left(50,5\left(n+n_L\right)\right)$) and Optimality Phase Iteration Limit ($\text{default value}=\max \left(50,5\left(n+n_L\right)\right)$)) was reached before normal termination occurred. If the method appears to be making progress (e.g., the objective function is being satisfactorily reduced), either increase the iterations limit and rerun E04NCF/E04NCA or, alternatively, rerun E04NCF/E04NCA using the Warm Start facility to specify the initial working set. If the iteration limit is already large, but some of the constraints could be nearly linearly dependent, check the monitoring information (see Section 12) for a repeated pattern of constraints entering and leaving the working set. (Near-dependencies are often indicated by wide variations in size in the diagonal elements of the matrix $T$ (see Section 10.2), which will be printed if $\mathbf{Print\; Level}\ge 30$ ($\text{default value}=10$). In this case, the algorithm could be cycling (see the comments for $\mathbf{IFAIL}=\mathbf{5}$).

$\mathbf{IFAIL}=5$

The algorithm could be cycling, since a total of $50$ changes were made to the working set without altering $x$. You should check the monitoring information (see Section 12) for a repeated pattern of constraint deletions and additions.

If a sequence of constraint changes is being repeated, the iterates are probably cycling. (E04NCF/E04NCA does not contain a method that is guaranteed to avoid cycling; such a method would be combinatorial in nature.) Cycling may occur in two circumstances: at a constrained stationary point where there are some small or zero Lagrange multipliers; or at a point (usually a vertex) where the constraints that are satisfied exactly are nearly linearly dependent. In the latter case, you have the option of identifying the offending dependent constraints and removing them from the problem, or restarting the run with a larger value of the optional parameter Feasibility Tolerance ($\text{default value}=\sqrt{\epsilon }$, where $\epsilon$ is the machine precision). If E04NCF/E04NCA terminates with $\mathbf{IFAIL}=\mathbf{5}$, but no suspicious pattern of constraint changes can be observed, it may be worthwhile to restart with the final $x$ (with or without the Warm Start option).

Note:  that this error exit may also occur if a poor starting point X is supplied (for example, $\mathbf{X}=0.0$). You are advised to try a non-zero starting point.

$\mathbf{IFAIL}=6$

An input parameter is invalid.

$\mathbf{IFAIL}=7$

The problem to be solved is of type QP1 or QP2, but the Hessian matrix supplied in A is not positive semidefinite.

$\mathbf{\text{Overflow}}$

If the printed output before the overflow error contains a warning about serious ill-conditioning in the working set when adding the $j$th constraint, it may be possible to avoid the difficulty by increasing the magnitude of the Feasibility Tolerance ($\text{default value}=\sqrt{\epsilon }$, where $\epsilon$ is the machine precision) and rerunning the program. If the message recurs even after this change, the offending linearly dependent constraint (with index ‘$j$’) must be removed from the problem.

7  Accuracy

8  Further Comments

8.1  Scaling

8.2  Description of the Printed Output

9  Example

9.1  Program Text

Program Text (e04ncfe.f90)

Program Text (e04ncae.f90)

9.2  Program Data

Program Data (e04ncfe.d)

Program Data (e04ncae.d)

9.3  Program Results

Program Results (e04ncfe.r)

Program Results (e04ncae.r)

10  Algorithmic Details

10.1  Overview

10.2  Definition of Search Direction

10.3  Main Iteration

11  Optional Parameters

• Cold Start
• Crash Tolerance
• Defaults
• Feasibility Phase Iteration Limit
• Feasibility Tolerance
• Hessian
• Infinite Bound Size
• Infinite Step Size
• Iteration Limit
• Iters
• Itns
• List
• Monitoring File
• Nolist
• Optimality Phase Iteration Limit
• Print Level
• Problem Type
• Rank Tolerance
• Warm Start

Begin  
  Print level = 1  
End

 CALL E04NDF (IOPTNS, INFORM)

 CALL E04NEF ('Print Level = 1')

11.1  Description of the Optional Parameters

• the keywords, where the minimum abbreviation of each keyword is underlined (if no characters of an optional qualifier are underlined, the qualifier may be omitted);
• a parameter value, where the letters $a$, $i\text{ and }r$ denote options that take character, integer and real values respectively;
• the default value, where the symbol $\epsilon$ is a generic notation for machine precision (see X02AJF).

12  Description of Monitoring Information