For each option, we give a summary line, a description of the optional parameter and details of constraints.

The summary line contains:

Keywords and character values are case and white space insensitive.

Every $i$th iteration after the most recent basis factorization, a numerical test is made to see if the current solution $\left(x,s\right)$ satisfies the linear constraints $Ax-s=0$. If the largest element of the residual vector $r=Ax-s$ is judged to be too large, the current basis is refactorized and the basic variables recomputed to satisfy the constraints more accurately. If $i\le 0$, the value $i=99999999$ is used and effectively no checks are made.

$\mathbf{Check\; Frequency}=1$ is useful for debugging purposes, but otherwise this option should not be needed.

Note that these options do not apply when $\mathbf{start}=\text{"W"}$ (see [Parameters]).

If $\mathbf{start}=\text{"C"}$, an internal Crash procedure is used to select an initial basis from various rows and columns of the constraint matrix $\left(\begin{array}{cc}A& -I\end{array}\right)$. The value of $i$ determines which rows and columns of $A$ are initially eligible for the basis, and how many times the Crash procedure is called. Columns of $-I$ are used to pad the basis where necessary.

If $i\ge 1$, certain slacks on inequality rows are selected for the basis first. (If $i\ge 2$, numerical values are used to exclude slacks that are close to a bound.) The Crash procedure then makes several passes through the columns of $A$, searching for a basis matrix that is essentially triangular. A column is assigned to ‘pivot’ on a particular row if the column contains a suitably large element in a row that has not yet been assigned. (The pivot elements ultimately form the diagonals of the triangular basis.) For remaining unassigned rows, slack variables are inserted to complete the basis.

The Crash Tolerance allows the Crash procedure to ignore certain ‘small’ nonzero elements in each column of $A$. If $a_{\max }$ is the largest element in column $j$, other nonzeros $a_{ij}$ in the column are ignored if $\left|a_{ij}\right|\le a_{\max }\times r$. (To be meaningful, $r$ should be in the range $0\le r<1$.)

When $r>0.0$, the basis obtained by the Crash procedure may not be strictly triangular, but it is likely to be nonsingular and almost triangular. The intention is to obtain a starting basis containing more columns of $A$ and fewer (arbitrary) slacks. A feasible solution may be reached sooner on some problems.

For example, suppose the first $m$ columns of $A$ form the matrix shown under LU Factor Tolerance; i.e., a tridiagonal matrix with entries $-1$, $4$, $-1$. To help the Crash procedure choose all $m$ columns for the initial basis, we would specify a Crash Tolerance of $r$ for some value of $r>0.5$.

This special keyword may be used to reset all optional parameters to their default values.

Optional parameters Dump File and Load File are similar to optional parameters Punch File and Insert File, but they record solution information in a manner that is more direct and more easily modified. A full description of information recorded in optional parameters Dump File and Load File is given in Gill et al. (2005a).

If $i_1>0$, the last solution obtained will be output to the file with unit number $i$.

If $i_2>0$, the Load File containing basis information will be read. The file will usually have been output previously as a Dump File. The file will not be accessed if optional parameters Old Basis File or Insert File are specified.

This parameter determines if (and when) elastic mode is to be started. Three elastic modes are available as follows:

This determines the form of the composite objective $f\left(x\right)+\gamma {\displaystyle \sum _j}\left(v_j+w_j\right)$ in Phase 2 ($\gamma$). Three types of composite objectives are available.

This defines the value of $\gamma$ in the composite objective in Phase 2 ($\gamma$).

At each iteration of elastic mode, the composite objective is defined to be where $\sigma =1$ for Minimize, $\sigma =-1$ for Maximize, and $f\left(x\right)$ is the quadratic objective.

Note that the effect of $\gamma$ is not disabled once a feasible point is obtained.

This option is part of an anti-cycling procedure (see [Miscellaneous]) designed to allow progress even on highly degenerate problems.

The strategy is to force a positive step at every iteration, at the expense of violating the constraints by a small amount. Suppose that the value of the optional parameter Feasibility Tolerance is $\delta$. Over a period of $i$ iterations, the feasibility tolerance actually used by e04nq (i.e., the working feasibility tolerance) increases from $0.5\delta$ to $\delta$ (in steps of $0.5\delta /i$).

Increasing the value of $i$ helps reduce the number of slightly infeasible nonbasic variables (most of which are eliminated during the resetting procedure). However, it also diminishes the freedom to choose a large pivot element (see the description of the optional parameter Pivot Tolerance).

If $i\le 0$, the value $i=99999999$ is used and effectively no anti-cycling procedure is invoked.

If $i>0$, at most $i$ basis changes will occur between factorizations of the basis matrix.

For LP problems, the basis factors are usually updated at every iteration. Higher values of $i$ may be more efficient on problems that are extremely sparse and well scaled.

For QP problems, fewer basis updates will occur as the solution is approached. The number of iterations between basis factorizations will therefore increase. During these iterations a test is made regularly according to the value of optional parameter Check Frequency to ensure that the linear constraints $Ax-s=0$ are satisfied. Occasionally, the basis will be refactorized before the limit of $i$ updates is reached. If $i\le 0$, the default value is used.

A feasible problem is one in which all variables satisfy their upper and lower bounds to within the absolute tolerance $r$. (This includes slack variables. Hence, the general constraints are also satisfied to within $r$.)

e04nq attempts to find a feasible solution before optimizing the objective function. If the sum of infeasibilities cannot be reduced to zero, the problem is assumed to be infeasible. Let sInf be the corresponding sum of infeasibilities. If sInf is quite small, it may be appropriate to raise $r$ by a factor of $10$ or $100$. Otherwise, some error in the data should be suspected.

Note that if sInf is not small and you have not asked e04nq to minimize the violations of the elastic variables (i.e., you have not specified $\mathbf{Elastic\; Objective}=2$), there may be other points that have a significantly smaller sum of infeasibilities. e04nq will not attempt to find the solution that minimizes the sum unless $\mathbf{Elastic\; Objective}=2$.

If the constraints and variables have been scaled (see the description of the optional parameter Scale Option), then feasibility is defined in terms of the scaled problem (since it is more likely to be meaningful).

If $r\ge 0$, $r$ defines the ‘infinite’ bound $\mathit{infbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\mathit{infbnd}$ will be regarded as $+\infty$ (and similarly any lower bound less than or equal to $-\mathit{infbnd}$ will be regarded as $-\infty$). If $r<0$, the default value is used.

The value of $i$ specifies the maximum number of iterations allowed before termination. Setting $i=0$ and $\mathbf{Print\; Level}>0$ means that: the workspace needed to start solving the problem will be computed and printed; and feasibility and optimality will be checked. No iterations will be performed. If $i<0$, the default value is used.

The density tolerance $r_1$ is used during $LU$ factorization of the basis matrix. Columns of $L$ and rows of $U$ are formed one at a time, and the remaining rows and columns of the basis are altered appropriately. At any stage, if the density of the remaining matrix exceeds $r_1$, the Markowitz strategy for choosing pivots is terminated. The remaining matrix is factored by a dense $LU$ procedure. Raising the density tolerance towards $1.0$ may give slightly sparser $LU$ factors, with a slight increase in factorization time.

If $r_2>0$, $r_2$ defines the singularity tolerance used to guard against ill-conditioned basis matrices. After $B$ is refactorized, the diagonal elements of $U$ are tested as follows. If $\left|u_{jj}\right|\le r_2$ or $\left|u_{jj}\right|<r_2{\displaystyle \underset{i}{\max }}\left|u_{ij}\right|$, the $j$th column of the basis is replaced by the corresponding slack variable. If $r_2\le 0$, the default value is used.

The values of $r_1$ and $r_2$ affect the stability and sparsity of the basis factorization $B=LU$, during refactorization and updates respectively. The lower triangular matrix $L$ is a product of matrices of the form where the multipliers $\mu$ will satisfy $\left|\mu \right|\le r_i$. The default values of $r_1$ and $r_2$ usually strike a good compromise between stability and sparsity. They must satisfy $r_1$, $r_2\ge 1.0$.

For large and relatively dense problems, $r_1=10.0\text{ or }5.0$ (say) may give a useful improvement in stability without impairing sparsity to a serious degree.

For certain very regular structures (e.g., band matrices) it may be necessary to reduce $r_1\text{ and/or }{r}_2$ in order to achieve stability. For example, if the columns of $A$ include a sub-matrix of the form one should set both $r_1$ and $r_2$ to values in the range $1.0\le r_i<4.0$.

The $LU$ factorization implements a Markowitz-type search for pivots that locally minimize the fill-in subject to a threshold pivoting stability criterion. The default option is to use threshold partial pivoting. The options LU Complete Pivoting and LU Rook Pivoting are more expensive but more stable and better at revealing rank, as long as the LU Factor Tolerance is not too large (say $<2.0$).

This option specifies the required direction of the optimization. It applies to both linear and nonlinear terms (if any) in the objective function. Note that if two problems are the same except that one minimizes $f\left(x\right)$ and the other maximizes $-f\left(x\right)$, their solutions will be the same but the signs of the dual variables ${\pi }_i$ and the reduced gradients $d_j$ (see [Main Iteration]) will be reversed.

The option Feasible Point means ‘ignore the objective function, while finding a feasible point for the linear constraints’. It can be used to check that the constraints are feasible without altering the call to e04nq.

Optional parameters New Basis File and Backup Basis File are sometimes referred to as basis maps. They contain the most compact representation of the state of each variable. They are intended for restarting the solution of a problem at a point that was reached by an earlier run. For nontrivial problems, it is advisable to save basis maps at the end of a run, in order to restart the run if necessary.

If $i_1>0$, a basis map will be saved on file $i_1$ every $i_3$th iteration, where $i_3$ is the Save Frequency. The first record of the file will contain the word PROCEEDING if the run is still in progress. A basis map will also be saved at the end of a run, with some other word indicating the final solution status.

Use of $i_2>0$ is intended as a safeguard against losing the results of a long run. Suppose that a New Basis File is being saved every $100$ (Save Frequency) iterations, and that e04nq is about to save such a basis at iteration $2000$. It is conceivable that the run may be interrupted during the next few milliseconds (in the middle of the save). In this case the Basis file will be corrupted and the run will have been essentially wasted.

To eliminate this risk, both a New Basis File and a Backup Basis File may be specified. The following would be suitable for the above example:

 
Backup Basis File 11 
New Basis File 12

The current basis will then be saved every $100$ iterations, first on File 12 and then immediately on File 11. If the run is interrupted at iteration $2000$ during the save on File 12, there will still be a usable basis on File 11 (corresponding to iteration $1900$).

Note that a new basis will be saved in New Basis File at the end of a run if it terminates normally, but it will not be saved in Backup Basis File. In the above example, if an optimum solution is found at iteration $2050$ (or if the iteration limit is $2050$), the final basis on File 12 will correspond to iteration $2050$, but the last basis saved on File 11 will be the one for iteration $2000$.

A full description of information recorded in New Basis File and Backup Basis File is given in Gill et al. (2005a).

Normally each optional parameter specification is printed to unit Print File as it is supplied. Optional parameter Nolist may be used to suppress the printing and optional parameter List may be used to restore printing.

If $i>0$, the basis maps information will be obtained from this file. The file will usually have been output previously as a New Basis File or Backup Basis File. A full description of information recorded in New Basis File and Backup Basis File is given in Gill et al. (2005a).

The file will not be acceptable if the number of rows or columns in the problem has been altered.

This is used to judge the size of the reduced gradients $d_j=g_j-a_j^{\mathrm{T}}\pi$, where $g_j$ is the $j$th component of the gradient, $a_j$ is the associated column of the constraint matrix $\left(\begin{array}{cc}A& -I\end{array}\right)$, and $\pi$ is the set of dual variables.

By construction, the reduced gradients for basic variables are always zero. The problem will be declared optimal if the reduced gradients for nonbasic variables at their lower or upper bounds satisfy respectively, and if $\left|d_j\right|/‖\pi ‖\le r$ for superbasic variables.

In the above tests, $‖\pi ‖$ is a measure of the size of the dual variables. It is included to make the tests independent of a scale factor on the objective function. The quantity $‖\pi ‖$ actually used is defined by so that only large scale factors are allowed for.

If the objective is scaled down to be very small, the optimality test reduces to comparing $d_j$ against $0.01r$.

This option is recommended for large FP or LP problems that have significantly more variables than constraints (i.e., $n\gg m$). It reduces the work required for each pricing operation (i.e., when a nonbasic variable is selected to enter the basis). If $i=1$, all columns of the constraint matrix $\left(\begin{array}{cc}A& -I\end{array}\right)$ are searched. If $i>1$, $A$ and $I$ are partitioned to give $i$ roughly equal segments $A_{\mathit{j}},I_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,i$ (modulo $i$). If the previous pricing search was successful on $A_{j-1},I_{j-1}$, the next search begins on the segments $A_j$ and $I_j$. If a reduced gradient is found that is larger than some dynamic tolerance, the variable with the largest such reduced gradient (of appropriate sign) is selected to enter the basis. If nothing is found, the search continues on the next segments $A_{j+1},I_{j+1}$, and so on. If $i\le 0$, the default value is used.

Broadly speaking, the pivot tolerance is used to prevent columns entering the basis if they would cause the basis to become almost singular.

When $x$ changes to $x+\alpha p$ for some search direction $p$, a ‘ratio test’ determines which component of $x$ reaches an upper or lower bound first. The corresponding element of $p$ is called the pivot element. Elements of $p$ are ignored (and therefore cannot be pivot elements) if they are smaller than the pivot tolerance $r$.

It is common for two or more variables to reach a bound at essentially the same time. In such cases, the optional parameter Feasibility Tolerance (say $t$) provides some freedom to maximize the pivot element and thereby improve numerical stability. Excessively small values of $t$ should therefore not be specified. To a lesser extent, the optional parameter Expand Frequency (say $f$) also provides some freedom to maximize the pivot element. Excessively large values of $f$ should therefore not be specified.

If $i>0$, the following information is output to $i$ during the solution of each problem:

–	a listing of the optional parameters;
–	some statistics about the problem;
–	the amount of storage available for the $LU$ factorization of the basis matrix;
–	notes about the initial basis resulting from a Crash procedure or a Basis file;
–	the iteration log;
–	basis factorization statistics;
–	the exit ifail condition and some statistics about the solution obtained;
–	the printed solution, if requested.

The last four items are described in [Further Comments] and [Description of Monitoring Information]. Further brief output may be directed to the Summary File.

If $i>0$, one line of the iteration log will be printed every $i$th iteration. A value such as $i=10$ is suggested for those interested only in the final solution. If $i\le 0$, the value of $i=99999999$ is used and effectively no checks are made.

This controls the amount of printing produced by e04nq as follows.

These files provide compatibility with commercial mathematical programming systems. The Punch File from a previous run may be used as an Insert File for a later run on the same problem. A full description of information recorded in Insert File and Punch File is given in Gill et al. (2005a).

If $i_1>0$, the final solution obtained will be output to file $i_1$. For linear programs, this format is compatible with various commercial systems.

If $i_2>0$, the Insert File containing basis information will be read. The file will usually have been output previously as a Punch File. The file will not be accessed if Old Basis File is specified.

Specifies the active-set algorithm used to solve the quadratic program in Phase 2 ($\gamma$). QPSolver Cholesky holds the full Cholesky factor $R$ of the reduced Hessian $Z^{\mathrm{T}}HZ$. As the QP iterations proceed, the dimension of $R$ changes with the number of superbasic variables. If the number of superbasic variables needs to increase beyond the value of Reduced Hessian Dimension, the reduced Hessian cannot be stored and the solver switches to QPSolver CG. The Cholesky solver is reactivated if the number of superbasics stabilizes at a value less than Reduced Hessian Dimension.

QPSolver QN solves the QP using a quasi-Newton method. In this case, $R$ is the factor of a quasi-Newton approximate Hessian.

QPSolver CG uses an active-set method similar to QPSolver QN, but uses the conjugate-gradient method to solve all systems involving the reduced Hessian.

The Cholesky QP solver is the most robust, but may require a significant amount of computation if there are many superbasics.

The quasi-Newton QP solver does not require computation of the exact $R$ at the start of Phase 2 ($\gamma$). It may be appropriate when the number of superbasics is large but relatively few iterations are needed to reach a solution (e.g., if e04nq is called with a Warm Start).

The conjugate-gradient QP solver is appropriate for problems with many degrees of freedom (say, more than $2000$ superbasics).

This specifies that an $i$ by $i$ triangular matrix $R$ (to define the reduced Hessian according to $R^{\mathrm{T}}R=Z^{\mathrm{T}}HZ$). is to be available for use by the Cholesky QP solver.

Three scale options are available as follows:

Optional parameter Scale Tolerance affects how many passes might be needed through the constraint matrix. On each pass, the scaling procedure computes the ratio of the largest and smallest nonzero coefficients in each column: If ${\displaystyle \underset{j}{\max }}{\rho }_j$ is less than $r$ times its previous value, another scaling pass is performed to adjust the row and column scales. Raising $r$ from $0.9$ to $0.99$ (say) usually increases the number of scaling passes through $A$. At most $10$ passes are made. The value of $r$ should lie in the range $0<r<1$.

Scale Print causes the row scales $r\left(i\right)$ and column scales $c\left(j\right)$ to be printed to Print File, if System Information Yes has been specified. The scaled matrix coefficients are ${\stackrel{-}{a}}_{ij}=a_{ij}c\left(j\right)/r\left(i\right)$, and the scaled bounds on the variables and slacks are ${\stackrel{-}{l}}_j=l_j/c\left(j\right)$, ${\stackrel{-}{u}}_j=u_j/c\left(j\right)$, where $c\left(j\right)=r\left(j-n\right)$ if $j>n$.

This option determines if the final obtained solution is to be output to the Print File. Note that the Solution File option operates independently.

If $i>0$, the final solution will be output to file $i$ (whether optimal or not).

To see more significant digits in the printed solution, it will sometimes be useful to make $i$ refer to the system Print File.

If $i_1>0$, the Summary File is output to file $i_1$, including a line of the iteration log every $i_2$th iteration. In an interactive environment, it is useful to direct this output to the terminal, to allow a run to be monitored online. (If something looks wrong, the run can be manually terminated.) Further details are given in [Description of Monitoring Information]. If $i_2\le 0$, the value of $i_2=99999999$ is used and effectively no checks are made.

This places a limit on the storage allocated for superbasic variables. Ideally, $i$ should be set slightly larger than the ‘number of degrees of freedom’ expected at an optimal solution.

For linear programs, an optimum is normally a basic solution with no degrees of freedom. (The number of variables lying strictly between their bounds is no more than $m$, the number of general constraints.) The default value of $i$ is therefore $1$.

For quadratic problems, the number of degrees of freedom is often called the ‘number of independent variables’. Normally, $i$ need not be greater than $n_H+1$, where $n_H$ is the number of leading nonzero columns of $H$. For many problems, $i$ may be considerably smaller than $n_H$. This will save storage if $n_H$ is very large.

Normally e04nq prints the options file as it is being read, and then prints a complete list of the available keywords and their final values. The optional parameter Suppress Parameters tells e04nq not to print the full list.

This option prints additional information on the progress of major and minor iterations, and Crash statistics. See [Description of Monitoring Information].

If $i>0$, some timing information will be output to the Print file, if $\mathbf{Print\; File}>0$.

If $r>0$, $r$ specifies the magnitude of the change in variables that will be considered a step to an unbounded solution. (Note that an unbounded solution can occur only when the Hessian is not positive definite.) If the change in $x$ during an iteration would exceed the value of $r$, the objective function is considered to be unbounded below in the feasible region. If $r\le 0$, the default value is used. See Infinite Bound Size for the definition of $\mathit{infbnd}$.