View source for QPOPT

{{Part Of Manual|title=the SOL Manual|link=[[SOL|SOL]]}}
==Introduction==

TOMLAB /QPOPT (hereafter referred to as QPOPT) is based on an inertia-controlling method that maintains a Cholesky factorization of the reduced Hessian (see below). Here we briefly summarize the main features of the method.

===Overview===

QPOPT's method has a ''feasibility phase ''(finding a feasible point by minimizing the sum of infeasibilities) and an ''optimality phase ''(minimizing the quadratic objective function within  the feasible region). The computations in both phases are performed by the same subroutines,  but with different objective functions. The feasibility phase does ''not ''perform the standard simplex method; i.e., it does not necessarily find a vertex (with  ''n ''constraints active), except in the LP case if ''m<sub>L</sub>  <= n''. Once an iterate is feasible, all subsequent iterates remain feasible. Once a vertex is reached, all subsequent iterates are at a vertex.

QPOPT is designed to be efficient when applied to a ''sequence ''of related problems-for example, within a sequential quadratic programming method for nonlinearly constrained optimization  (e.g., the NPOPT  package).  In particular,  the user may specify an initial  working set (the indices of the constraints believed to be satisfied exactly at the solution); see the discussion of Warm  Start.

In general, an iterative process is required to solve a quadratic program. Each new iterate <math>\bar{x}</math> is defined by

<math>
\bar{x}	= x + \alpha p,
</math>

where the ''step length &alpha; ''is a non-negative scalar, and ''p ''is called the ''search direction ''.  (For simplicity,  we shall consider a typical iteration and avoid reference to the iteration index.)

===The working set===

At each point ''x'', a ''working set ''of constraints is defined to be a linearly independent subset of the constraints that are satisfied "exactly"  (to within the Feasibility tolerance). The working set is the current prediction of the constraints that hold with equality at a solution of LCQP. Let ''m<sub>w</sub>  ''denote the number of constraints in the working set (including bounds), and let ''W ''denote the associated ''m<sub>w</sub>  × n ''matrix of constraint gradients.

The definition of the search direction ensures that constraints in the working set remain ''unaltered ''for any value of the step length. Thus, 

<math>
W p = 0.
</math>

In order to compute ''p'', a ''TQ factorization'' of ''W'' is used:

<math>
W Q = \left( {\begin{array}{cc}
0 & T  \\
\end{array} } \right),
</math>

where ''T ''is a nonsingular ''m<sub>w</sub>  × m<sub>w</sub>  ''upper-triangular matrix,  and ''Q ''is an ''n × n ''nonsingular matrix constructed from a product of orthogonal transformations. If the columns of ''Q ''are partitioned so that

<math>
Q = \left( {\begin{array}{cc}
Z & Y  \\
\end{array} } \right),
</math>

where ''Y ''is ''n × m<sub>w</sub>  ''and ''Z ''is ''n × n<sub>Z</sub>  ''(where ''n<sub>Z</sub> ''= ''n - m<sub>w</sub> ''), then the columns of ''Z ''form a basis for the null space of ''W ''. Let ''n<sub>R</sub>  ''be an integer such that 0 ''<= n<sub>R</sub>  <= n<sub>Z</sub> '', and let ''Z<sub>R</sub>  ''denote a matrix whose ''n<sub>R</sub>  ''columns are a subset of the columns of ''Z ''. (The integer ''n<sub>R</sub>  ''is the quantity "Zr" in the printed output from qpopt).  In many cases, ''Z<sub>R</sub>'' will include ''all ''the columns of ''Z ''. The direction ''p '' will satisfy if

<math>
p = Z_R p_R,
</math>

where ''p<sub>R</sub>'' is any ''n<sub>R</sub> ''-vector.

===The reduced Hessian===

Let ''gQ   ''and ''HQ  ''denote the ''transformed gradient ''and ''transformed Hessian '':

<math>g_Q = Q^T g(x)</math> and <math>H_Q = Q^T H Q.</math>

The first ''n<sub>R</sub>'' elements of the vector ''g<sub>Q</sub>'' will be denoted by ''g<sub>R</sub> '', and the first ''n<sub>R</sub>  ''rows and columns of the matrix ''H<sub>Q</sub> ''will be denoted by ''H<sub>R</sub> ''. The quantities ''g<sub>R</sub>   ''and ''H<sub>R</sub>  ''are known as the ''reduced gradient ''and ''reduced Hessian ''of ''q''(''x''), respectively. Roughly speaking, ''g<sub>R</sub>'' and ''H<sub>R</sub>'' describe the first and second derivatives of an ''unconstrained ''problem for the calculation of ''p<sub>R</sub> ''.

At each iteration, a triangular factorization of ''H<sub>R</sub>'' is available. If ''H<sub>R</sub>  ''is positive definite, ''H<sub>R</sub> ''= ''R<sup>T</sup>R'', where ''R ''is the upper-triangular Cholesky factor of ''H<sub>R</sub> ''. If ''H<sub>R</sub>  ''is not positive definite, ''H<sub>R</sub> ''= ''R<sup>T</sup>DR'', where ''D ''= diag(1, 1, . . . , 1, w), with ''w <= ''0.

In QPOPT,  the computation is arranged so that the reduced-gradient vector is a multiple of ''e<sub>R</sub> '', a vector of all zeros except in the last (''n<sub>R</sub>''th) position. This allows ''p<sub>R</sub>'' to be computed  from a single back-substitution,

<math>
R p\R = \gamma e\R,
</math>

where &gamma; is a scalar whose definition depends on whether the reduced Hessian is positive  definite at ''x''.  In the positive-definite case, ''x ''+ ''p ''is the minimizer of the objective function subject to the working-set constraints being treated as equalities. If ''H<sub>R</sub>  ''is not positive definite, ''p<sub>R</sub>   ''satisfies

<math>p\R^T_R H_R p_R < 0</math> and <math>g^T_R p_R \le 0,</math>

allowing the objective function to be reduced by any step of the form ''x ''+ ''&alpha;p'', ''&alpha; > ''0.

===Optimality conditions===

If the reduced gradient  is zero, ''x ''is a constrained  stationary point  in the subspace defined  by ''Z ''.  During the feasibility phase, the reduced gradient will usually be zero only at a vertex (although it may be zero elsewhere in the presence of constraint dependencies).  During the optimality phase, a zero reduced gradient implies that ''x ''minimizes the  quadratic objective  when the constraints in the working set are treated as equalities.  At a constrained stationary point, Lagrange multipliers ''&lambda;'' are defined from the equations

<math>
W^T\lambda = g(x).
</math>

A Lagrange multiplier  ''&lambda;'' corresponding to an inequality constraint  in the working set is said to be ''optimal ''if <math>\lambda_j \le \sigma</math> when the associated constraint is at its ''upper bound '', or if <math>\lambda_j \ge - \sigma</math> when the associated constraint is at its ''lower bound '', where ''&sigma;'' depends on the Optimality tolerance. If a multiplier  is non-optimal, the objective function (either the true objective  or the sum of infeasibilities) can be reduced by deleting the corresponding constraint from the working set (see [[#The Summary File]]).

If optimal multipliers occur during the feasibility phase but the sum of infeasibilities is not zero, there is no feasible point. The user can request QPOPT  to continue until the sum of infeasibilities is minimized (see the discussion of Min sum).  At such a point, the Lagrange multiplier  <math>\lambda_j</math> corresponding to an inequality constraint in the working set will be such that <math>-(1+\sigma) \le \lambda_j \le \sigma</math> when the associated constraint is at its ''upper bound '', and <math>-\sigma \le \lambda_j
\le 1+\sigma</math> when the associated constraint  is at its ''lower bound ''. Lagrange multipliers  for equality constraints will satisfy

<math>
|\lambda_j| \le 1 + \sigma
</math>

If the reduced gradient is not zero, Lagrange multipliers need not be computed and the search direction ''p ''is given by ''Z<sub>R</sub> p<sub>R</sub>''. The step length is chosen to maintain feasibility with respect to the satisfied constraints. If ''H<sub>R</sub>'' is positive definite and ''x ''+ ''p ''is feasible, ''&alpha;'' is defined to be one. In this case, the reduced gradient at <math>\bar{x}</math> will be zero, and Lagrange multipliers are computed. Otherwise, ''&alpha;'' is set to ''&alpha;<sub>M</sub> '', the step to the "nearest" constraint (with index Jadd; see [[#The Summay File]]). This constraint is added to the working set at the next iteration.

If the reduced Hessian ''H<sub>R</sub>'' is not positive definite and ''a<sub>M</sub>'' does not exist (i.e., no positive step ''a<sub>M</sub>'' reaches the boundary of a constraint not in the working set), then QPOPT  terminates at ''x'' and declares the problem to be unbounded.

==Further  Details of the Method==

The following sections are not essential knowledge for normal users. They give background on the active-set strategy and the anti-cycling procedure.

===Treatment of simple upper and lower bounds===

Bound constraints <math>\ell \le x \le u</math> are treated specially by qpopt.  The presence of a bound constraint in the working set has the effect  of fixing the corresponding component  of the search direction to zero.  Thus, the associated variable is ''fixed '', and specification of the working set induces a partition  of ''x ''into ''fixed ''and ''free  ''variables. For some permutation ''P'', the working-set matrix satisfies

<math>
W P = \left( {\begin{array}{cc}
F & N  \\
& I_N
\end{array} } \right),
</math>

where ( ''F N'' ) is part of the matrix ''A'', and ''I<sub>N</sub>'' corresponds to some of the bounds. The matrices ''F'' and ''N'' contain the free and fixed columns of the general constraints in the working set. A ''T Q'' factorization ''F Q<sub>F</sub>'' = ( 0 ''T<sub>F</sub> '' ) of the smaller matrix ''F ''provides the required ''T ''and ''Q ''as follows:

<math>
Q = P \left( {\begin{array}{cc}
Q_F &  \\
& I_N
\end{array} } \right),
</math>

<math>
T = \left( {\begin{array}{cc}
T_F & N  \\
& I_N
\end{array} } \right),
</math>

The matrix ''Q<sub>F</sub>'' is implemented as a dense ''orthogonal ''matrix.  Each change in the working set leads to a simple change to ''F '': if the status of a general constraint changes, a ''row ''of ''F ''is altered; if a bound constraint enters or leaves the working set, a ''column ''of ''F ''changes. The matrices ''T<sub>F</sub> '', ''Q<sub>F</sub>   ''and ''R ''are held explicitly; together with the vectors ''Q<sup>T</sup>g'', and ''Q<sup>T</sup>c''. Products of plane rotations are used to update ''Q<sub>F</sub>'' and ''T<sub>F</sub>'' as the working set changes. The triangular factor ''R ''associated with the reduced Hessian is updated only during the optimality  phase.

===The  initial  working set===

For a cold start, the initial  working set includes equality constraints and others that are close to being satisfied at the starting point. ("Close" is defined under Crash tolerance.) For a warm start, the initial working is specified by the user (and possibly revised to improve the condition of ''W '').

At the start of the optimality  phase, QPOPT  must ensure that the initial  reduced Hessian ''H<sub>R</sub>'' is positive-definite. It does so by including a suitably large number of constraints (real or artificial)  in the initial  working set. (When ''W ''contains ''n ''constraints, ''H<sub>R</sub>  ''has no rows and columns. Such a matrix is positive definite by definition.)

Let ''H<sub>Z</sub>'' denote the first ''n<sub>Z</sub>'' rows and columns of ''H<sub>Q</sub> ''='' Q<sup>T</sup>HQ'' at the beginning of the optimality  phase. A partial Cholesky factorization with interchanges is used to find an upper-triangular matrix ''R ''that is the factor of the largest positive-definite leading submatrix of ''H<sub>Z</sub>''.  The use of interchanges tends to maximize the dimension of ''R''.  (The condition of ''R ''may be controlled by setting the Rank Tolerance.)  Let ''Z<sub>R</sub>  ''denote the columns of ''Z ''corresponding to ''R'', and let ''Z ''be partitioned as ''Z ''=  ''Z<sub>R</sub>     Z<sub>A</sub>    ''. A working set for which ''Z<sub>R</sub> ''defines the null space can be obtained by including ''the rows of Z<sub>A</sub><sup>T</sup>  ''as "artificial constraints" (with bounds equal to the current value of ''Z<sub>A</sub><sup>T</sup>x'').  Minimization of the objective function then proceeds within  the subspace defined by ''Z<sub>R</sub> '', as described in [[#Introduction]].

The artificially augmented working set is given by

<math>
\bar{W} = \left( {\begin{array}{cc}
Z_A^T  \\
W
\end{array} } \right),
</math>

so that ''p'' will satisfy ''W p '' = 0 ''and Z<sub>A</sub><sup>T</sup>p ''= 0. By definition of the ''T Q ''factors of ''W '', we have

<math>
\bar{W}Q = \left( {\begin{array}{cc}
Z_A^T  \\
W
\end{array} } \right),

Q = \left( {\begin{array}{cc}
Z_A^T  \\
W
\end{array} } \right)

\left( {\begin{array}{ccc}
Z_R & Z_A & Y  \\
\end{array} } \right)
= 
\left( {\begin{array}{cc}
0 & \bar{T}
\end{array} } \right),
</math>

where

<math>
\bar{T} = \left( {\begin{array}{cc}
I & 0 \\
0 & T
\end{array} } \right).
</math>

Hence the ''T Q ''factors of <math>\bar{W}</math> are available trivially.

The matrix ''Z<sub>A</sub>'' is not kept fixed, since its role is purely to define an appropriate null space; the ''T Q ''factorization can therefore be updated in the normal fashion as the iterations proceed. No work is required to "delete" the artificial constraints associated with ''Z<sub>A</sub> ''when ''Z<sub>R</sub><sup>T</sup>g ''= 0, since this simply involves repartitioning ''Q''. The "artificial" multiplier  vector associated with the rows of ''Z<sub>A</sub><sup>T</sup>'' is equal to ''Z<sub>A</sub><sup>T</sup>g'', and the multipliers corresponding to the rows of the "true" working set are the multipliers that would be obtained if the artificial constraints were not present. If an artificial constraint is "deleted" from the working set, an A appears  alongside  the entry in the Jdel  column of the printed output (see [[#The Summary File]]). The multiplier  may have either sign.

The number of columns in ''Z<sub>A</sub>''and ''Z<sub>R</sub>'', the Euclidean norm of ''Z<sub>R</sub><sup>T</sup>g'', and the condition estimator of ''R'' appear in the printed output as Art, Zr, Norm  gZ and Cond Rz (see [[#The Summary File]]).

Under some circumstances, a different type of artificial constraint is used when solving a linear program. Although the algorithm of qpopt does not usually perform simplex steps (in the traditional  sense), there is one exception: a linear program with  fewer general constraints than variables (i.e., ''m<sub>L</sub>   <= n'').  (Use of the simplex method in this situation leads to savings in storage.) At the starting point, the "natural" working set (the set of constraints exactly or nearly satisfied at the starting point) is augmented with a suitable number of "temporary" bounds, each of which has the effect of temporarily fixing a variable at its current value. In subsequent iterations, a temporary bound is treated similarly to normal constraints until it is deleted from the working set, in which case it is never added again. If a temporary bound is "deleted" from the working set, an F (for "Fixed") appears alongside the entry in the Jdel column of the printed output (see [[#The Summary File]]). Again, the multiplier may have either sign.

===The  anti-cycling  procedure===

The EXPAND procedure is used to reduce the possibility of cycling at a point where the active constraints are nearly linearly dependent. The main feature of EXPAND  is that the feasibility tolerance is increased slightly at the start of every iteration.  This allows a positive step to be taken every iteration, perhaps at the expense of violating the constraints slightly.

Suppose that the Feasibility tolerance is &delta;. Over a period of ''K ''iterations (where ''K ''is defined by the Expand frequency), the feasibility tolerance actually used by QPOPT-the ''working ''feasibility tolerance-increases from 0.5&delta; to &delta; (in steps of 0.5&delta;/K).

At certain stages the following "resetting procedure" is used to remove constraint infeasibilities.  First, all variables whose upper or lower bounds are in the working set are moved exactly onto their bounds. A count is kept of the number of nontrivial adjustments made. If the count is positive, iterative refinement is used to give variables that satisfy the working set to (essentially) machine precision. Finally, the working feasibility tolerance is reinitialized to 0''.''5''&delta;''.

If a problem requires more than ''K ''iterations, the resetting procedure is invoked and a new cycle of iterations is started with ''K ''incremented by 10. (The decision to resume the feasibility phase or optimality  phase is based on comparing any constraint infeasibilities with ''&delta;''.)

The resetting procedure is also invoked when QPOPT  reaches an apparently optimal, infeasible or unbounded solution, unless this situation has already occurred twice.  If any nontrivial  adjustments are made, iterations are continued.

The EXPAND  procedure not only allows a positive step to be taken at every iteration, but also provides a potential ''choice ''of constraints to be added to the working set. Let ''aM  ''denote the maximum step at which ''x ''+ ''&alpha;<sub>M</sub>p ''does not violate any constraint by more than its feasibility tolerance. All constraints at distance ''&alpha; ''(''&alpha; <= &alpha;<sub>M</sub> '') along ''p'' from the current point are then viewed as acceptable candidates for inclusion in the working set. The constraint whose normal makes the largest angle with the search direction is added to the working set. This strategy helps keep the working-set matrix ''W ''well-conditioned.

==The Options File==

Observe that options are normally set in ''Prob.SOL.optPar''.

Several choices in QPOPT's algorithm logic may be defined by various ''optional parameters ''(more briefly known as ''options ''or ''parameters'').

In  order to reduce the number of subroutine parameters for qpopt, the options have ''default values'' that  are appropriate for most problems. Options need be specified only if their values should be different from the default.

===Format  of option strings===

Each optional parameter is defined by an ''option string'' of up to 72 characters, containing one or more ''items'' separated by spaces or equal signs (=). Alphabetic characters may be in upper or lower case. An example option string is Print level = 5. In general, an option string contains the following items:

#A ''keyword'' such as Print.
#A ''phrase'' such as level that qualifies the keyword. (Typically  0, 1 or 2 words.)
#A ''number'' that specifies either an integer or a real value (only for some options). Such numbers may be up to 16 contiguous characters in Fortran 77's F, E or D formats, terminated by a space.

Blank strings and comments may be used to improve readability.  A ''comment'' begins with an asterisk (*) and all subsequent characters are ignored. Synonyms are recognized for some of the keywords, and abbreviations may be used if there is no ambiguity.

The following are examples of valid option strings for QPOPT:

<pre>
NOLIST
COLD START
Warm start
Problem type  = LP
Problem type  = Quadratic Program        * Same as QP or QP2
Problem Type    QP4
Min sum         Yes
Feasibility Phase iteration limit   100
Feasibility tolerance            1.0e-8  * for IEEE double precision
Crash tolerance                   0.002
Defaults
* This string will be ignored.             So will a blank line.
</pre>

==Description of the optional parameters==

Permissible options are defined below in alphabetical order. For each option, we give the keyword, any essential qualifiers, the default value, and the definition.   The  minimum abbreviation of each keyword and qualifier is underlined. If no characters of a qualifier are underlined, the qualifier may be omitted. The letters ''i ''and ''r ''denote integer and real values required for certain options. The letter ''a ''denotes a character string value. The number '''u '''represents unit roundoff for floating-point arithmetic (typically about 10<sup>''-''16</sup>).

{| cellpadding="10"
|<tt>Check frequency</tt>||<tt>i</tt>||<tt>Default = 50</tt>
|}

Every ''i''th iteration,  a numerical test is made to see if the current  solution ''x ''satisfies the constraints in the working set. If the largest residual of the constraints in the working set is judged to be too large, the working-set matrix  is refactorized and the variables are recomputed to satisfy the constraints more accurately.

{| cellpadding="10"
|<tt>Cold start</tt>||||<tt>Default = Coldstart</tt>
|-
|<tt>Warm start</tt>
|}

This option specifies how the initial working set is chosen. With a cold start, QPOPT chooses the initial working set based on the values of the variables and constraints at the initial  point. Broadly speaking, the first working set will include all equality constraints and also any bounds or inequality constraints that are "nearly" satisfied (to within the Crash tolerance).

With a warm start, the user must provide a valid definition of every element of the array istate.  The specification of istate will  be overridden if necessary, so that  a poor choice of the working set will not cause a fatal error. A warm start will be advantageous if a good estimate of the initial working set is available-for example, when qpopt is called repeatedly to solve related problems.

{| cellpadding="10"
|<tt>Crash tolerance</tt>||<tt>r</tt>||<tt>Default = 0.01</tt>
|}

This value is used for cold starts when QPOPT selects an initial working set. Bounds and inequality constraints are selected if they are satisfied to within ''r''. More precisely, a constraint of the form ''aTx = l '' will be included in the initial working set if <math>| a_j^T x - l | \le r(1 +
|l|)</math>.  If ''r < ''0 or ''r > ''1, the default value is used.

{| cellpadding="10"
|<tt>Defaults</tt>
|}

This is a special option to reset all options to their default values.

{| cellpadding="15"
|<tt>Expand frequency</tt>||<tt>i</tt>||<tt>Default = 5</tt>
|}

This defines the initial value of an integer ''K ''that  is used in an anti-cycling procedure designed to guarantee progress even on highly degenerate problems. See [[#The anti-cycling procedure]].

If ''i = ''9999999, no anti-cycling procedure is invoked.

{| cellpadding="15"
|<tt>Feasibility tolerance</tt>||<tt>r</tt>||<tt>Default = <math>\sqrt{u}</math></tt>
|}
	 		
This defines the maximum acceptable ''absolute ''violation in each constraint at a "feasible" point.  For example, if the variables and the coefficients in the general constraints are of order unity, and the latter are correct to about 6 decimal digits, it would be appropriate to specify ''r ''as 10<sup>''-''6</sup>. If ''r < '''''u''', the default value is used.

Before optimizing the objective  function, QPOPT must find a feasible point for the constraints. If the sum of infeasibilities cannot be reduced to zero and <tt>Min sum  = Yes</tt> is requested, QPOPT will find the minimum value of the sum. Let <tt>sinf</tt> be the corresponding sum of infeasibilities. If <tt>sinf</tt> 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.
 
{| cellpadding="15"
|<tt>Feasibility Phase Iteration Limit</tt>||<tt>i<sub>1</sub></tt>||<tt>Default = max(50'', ''5(''n ''+ ''m<sub>L</sub>''))</tt>
|-
|<tt>Optimality	Phase Iteration Limit</tt>||<tt>i<sub>2</sub></tt>||<tt>Default = Default = max(50'', ''5(''n ''+ ''m<sub>L</sub> ''))</tt>
|}

The scalars ''i''<sub>1</sub> and ''i''<sub>2</sub> specify the maximum number of iterations allowed in the feasibility and optimality phases. Optimality Phase iteration limit is equivalent to Iteration limit.   Setting ''i''<sub>1</sub>  = 0 and PrintLevel ''> ''0 means that the workspace needed will be computed  and printed, but no iterations will be performed.

{| cellpadding="15"
|<tt>Hessian rows</tt>||<tt>i</tt>||<tt>Default = 0 or ''n''</tt>
|}

This specifies ''m'', the number of rows in the Hessian matrix ''H ''or its trapezoidal factor ''G ''(as used by the default subroutine qpHess).

For problem type FP or LP, the default value is ''m ''= 0.

For problems QP1 or QP2, the first ''m ''rows and columns of ''H ''are obtained from H, and the remainder are assumed to be zero. For problems QP3 or QP4, the factor ''G ''is assumed to have ''m ''rows and ''n ''columns. They are obtained from the associated rows of H.

If a nonstandard subroutine qpHess is provided, it may access the problem type and ''m ''via the lines

<pre>
integer              lqptyp, mHess 
common	    /sol1qp/ lqptyp, mHess
</pre>

For example, Problem type FP, LP or QP4 sets lqptyp = 1, 2 or 6 respectively, and Hessian rows 20 sets mHess = 20. 

{| cellpadding="15"
|<tt>Infinite Bound size</tt>||<tt>r</tt>||<tt>Default = 1020</tt>
|}

If ''r > ''0, ''r ''defines the "infinite" bound bigbnd in the definition of the problem constraints.  Any upper bound greater than or equal to bigbnd will be regarded as plus infinity  (and similarly for a lower bound less than or equal to ''-''bigbnd).  If ''r <= ''0, the default value is used.

{| cellpadding="15"
|<tt>Infinite Step size</tt>||<tt>r</tt>||<tt>Default = max(bigbnd'', ''10<sup>20</sup> )</tt>
|}

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 Infinite Step, the objective function is considered to be unbounded  below in the feasible region.  If ''r <= ''0, the default value is used.

{| cellpadding="15"
|<tt>Iteration limit</tt>||<tt>i</tt>||<tt>Default = max(50'', ''5(''n ''+ ''m<sub>L</sub> ''))</tt>
|-
|<tt>Iters</tt>
|-
|<tt>Itns</tt>
|}

This is equivalent to Optimality Phase iteration limit. See Feasibility Phase.
{| cellpadding="15"
|<tt>List</tt>
|}

If Nolist was previously specified, List restores output to the Print file whenever an optional parameter is reset.

{| cellpadding="15"
|<tt>Maximum  degrees of freedom</tt>||<tt>i</tt>||<tt>Default = ''n''</tt>
|}

This places a limit on the storage allocated for the triangular factor ''R ''of the reduced Hessian ''H<sub>R</sub> ''. Ideally, ''i ''should be set slightly larger than the value of ''n<sub>R</sub>  ''expected at the solution.  (See [[#The working set]] and [[#The reduced Hessian]].) It need not be larger than ''m<sub>N</sub>   ''+ 1, where ''m<sub>N</sub>   ''is the number of variables that appear nonlinearly in the quadratic objective function. For many problems it can be much smaller than ''m<sub>N</sub> ''.

For quadratic problems, a minimizer may lie on any number of constraints, so that ''n<sub>R</sub>  ''may vary between 1 and ''n''. The default value of ''i ''is therefore the number of variables ''n''. If Hessian  rows ''m ''is specified, the default value of ''i ''is the same number, ''m''.

{| cellpadding="15"
|<tt>Min sum</tt>||a||<tt>Default = No</tt>
|}

This option comes into effect if the constraints cannot be satisfied. If Min sum  = No, QPOPT terminates as soon as it is evident that  no feasible point exists. The final point will  generally not be the point at which the sum of infeasibilities is minimized.  If  Min sum  = Yes, QPOPT  will  continue until either the sum of infeasibilities is minimized or the iteration limit  is reached, whichever occurs first.

{| cellpadding="15"
|<tt>Nolist</tt>
|}

This suppresses output to the Print file whenever an optional parameter is reset.

{| cellpadding="15"
|<tt>Optimality tolerance</tt>||<tt>r</tt>||<tt>Default = <math>\sqrt{u}</math></tt>
|}

This affects the tolerance used to determine if the Lagrange multipliers associated with the bounds and general constraints have the right "sign" for the solution to be judged optimal. Increasing ''r ''tends to cause earlier termination. For example, if ''r ''= 1''.''0e ''- ''4, the final objective value will probably agree with the true optimum to about 4 digits.

{| cellpadding="15"
|<tt>Print level</tt>||<tt>i</tt>||<tt>Default = 10</tt>
|}

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

{|class="wikitable"
!i!!
|-
|0||No output.
|-
|1||The final solution only, sent to the Print file.
|-
|5||One line of output for each iteration (no printout  of the final solution).
|-
|''>= ''10||The final solution and one line of output for each iteration (Print file only).
|-
|''>= ''20||At each iteration,  the Lagrange multipliers,  the variables ''x'', the constraint  values ''Ax  ''and the constraint status (Print file only).
|-
|''>= ''30||At each iteration, the diagonal elements of the upper-triangular matrix ''T ''associated with the ''T Q ''factorization of the working set, and the diagonal elements of the upper-triangular matrix ''R'' (Print file only).
|}

{| cellpadding="15"
|<tt>Problem type</tt>||<tt>a</tt>||<tt>Default = QP2</tt>
|}

This option specifies the type of objective function to be minimized during the optimality  phase. The following are the six values of ''a ''and the dimensions of the arrays that must be specified to define the objective function:

<pre>
FP		H and cvec not accessed;
LP		H not accessed, cvec(n) required;
QP1H(ldH,*) 	symmetric, cvec not referenced;
P2H(ldH,*) 	symmetric, cvec(n);
QP3H(ldH,*) 	upper-trapezoidal, cvec not referenced;
QP4H(ldH,*) 	upper-trapezoidal, cvec(n);
</pre>

Linear program is equivalent to LP. Quadratic program and QP are equivalent to the default option QP2.  For the QP options, the default subroutine qpHess requires array H(ldH,*) as shown. If a non-standard qpHess is provided, H(*,*) may be used in any convenient way.

{| cellpadding="15"
|<tt>Rank</tt>||<tt>r</tt>||<tt>Default = 100'''u'''</tt>
|}

This parameter enables the user to control the condition number of the triangular factor ''R ''(see [[#Introduction]]). If <math>\rho_i</math> denotes the function <math>\rho_i = \max{\{|R_{11}|, |R_{22}|, \dots, |R_{ii}|\}}</math>, the dimension of ''R ''is defined to be smallest index ''i ''such that <math>|R_{i+1,i+1}| \le \sqrt{r}|\rho_{i+1}|</math>.  If ''r <= ''0, the default value is used.

{| cellpadding="15"
|<tt>Summary  file</tt>||<tt>i</tt>||<tt>Default = 6</tt>
|}

This specifies the unit number for the Summary file (see [[#The Summary File]]).

If ''i > ''0 and PrintLevel ''> ''0, a brief log in 80-column format is output to unit ''i''.  On many systems, the default value refers to the screen.  Summary file = 0 suppresses output, ''including error messages ''.

{| cellpadding="15"
|<tt>Warm start</tt>
|}

See <tt>Cold start</tt>.

==Optional parameter checklist and default values==

For easy reference,  the following list shows all valid options and their default values. The quantity '''u '''represents floating-point precision (&asymp;''1''.''1 ''× ''10''<sup>-16</sup> in IEEE double-precision arithmetic).

{|
|Check frequency||50||* 
|-
|Cold start||||* 
|-
|Crash tolerance||.01||* 
|-
|Expand frequency||5||*
|-
|Feasibility  tolerance||1.1e-8||*||<math>\sqrt{u}</math>
|-
|Feasibility Phase iteration limit||50||*||or 5(''n ''+ ''m<sub>L</sub>'') 
|-
|Optimality Phase iteration limit||50||*||or 5(''n ''+ ''m<sub>L</sub>'') 
|-
|Hessian rows||n||*
|-
|Infinite bound size||1.0e+20||*||Plus infinity
|-
|Infinite step size||1.0e+20||* 
|-
|Iteration limit||50||*||or 5(''n ''+ ''m<sub>L</sub>'')
|-
|List||||* 
|-
|Maximum degrees of freedom||n||* 
|-
|Min sum||No||*
|-
|Optimality tolerance||1.1e-8||*||<math>\sqrt{u}</math>
|-
|Print file||9||* 
|-
|Print level||10||* 
|-
|Problem type||QP||*||or QP2
|-
|Rank tolerance||1.1e-14||*||100'''u'''
|-
|Summary file||6||*
|}

Other options may be set as follows:

<pre>
Defaults
Nolist
Warm start
</pre>

==The Summary File==

The Summary file records an iteration log and error messages. The file name is set in ''Prob.SOL.SummFile''.

===Constraint numbering and status===

For items Jdel and Jadd in the iteration log, indices 1 through n refer to the bounds on the variables, and indices n + 1 through n + nclin refer to the general constraints.

When the status of a constraint changes, the index of the constraint is printed, along with the designation L (lower bound), U (upper bound), E (equality), F (temporarily fixed variable) or A (artificial constraint).

===The iteration log===

The following items are printed ''after ''each iteration.

{| class="wikitable"
|Itn||is the iteration count (including those from the feasibility phase).
|-valign="top"
|Jdel||is the index of the constraint deleted from the working set. If Jdel is zero, no constraint was deleted.
|-valign="top"
|Jadd||is the index of the constraint added to the working set. If Jadd is zero, no constraint was added.
|-valign="top"
|Step||is the step taken along the computed search direction.   If  a constraint  is added during the current iteration (i.e., Jadd is positive), Step will be the step to the nearest constraint. During the optimality phase, the step can be greater than one only if the reduced Hessian is not positive definite.
|-valign="top"
|Ninf||is the number of violated constraints (infeasibilities).   This number will  be zero during the optimality  phase.

Sinf/Objective is the value of the current objective function. If x is not feasible, Sinf gives a weighted sum of the magnitudes of constraint violations. If x is feasible, Objective is the value of the objective function.  The output line for the final iteration of the feasibility phase (i.e., the first iteration for which Ninf is zero) will give the value of the true objective at the first feasible point.

During the feasibility phase, the number of constraint infeasibilities will not increase until either a feasible point is found, or the optimality of the multipliers implies that no feasible point exists. Note that the ''sum ''of the infeasibilities may increase or decrease during this part of the feasibility phase. However, once optimal phase-one multipliers are obtained, the number of infeasibilities can increase, but the sum of infeasibilities must either remain constant or be reduced until the minimum sum of infeasibilities is found.

In the optimality  phase, the value of the objective is non-increasing.
|-valign="top"
|Norm gZ||is <math>||Z_R^Tg||</math>, the Euclidean norm of the reduced gradient with respect to ''Z<sub>R</sub> ''. During the optimality phase, this norm will be approximately zero after a unit step.
|-valign="top"
|Zr||is the number of columns of ''Z<sub>R</sub>  ''(see [[#Introduction]]). Zr is the dimension of the subspace in which the objective is currently being minimized.  The value of Zr is the number of variables minus the number of constraints in the working set.
|-valign="top"
|Art||is the number of artificial constraints in the working set, i.e., the number of columns of ''ZA  ''(see [[#Further Details of the Method]]). At the start of the optimality  phase, Art  provides an estimate of the number of nonpositive eigenvalues in the reduced Hessian.
|}

===Summary  file from the example problem===

Following is a Summary file example.

<pre>  
                     QPOPT  ---  Version 1.0-10     Sep  1995
                     ========================================

 Itn Jdel  Jadd     Step Ninf  Sinf/Objective Norm gZ   Zr  Art
   0    0     0  0.0E+00    0  0.00000000E+00 0.0E+00    0    6
 Itn     0 -- Feasible point found.
   0    0     0  0.0E+00    0  1.51638000E+03 9.8E+01    1    5
   1    0     8U 2.8E-01    0  1.72380000E+02 0.0E+00    0    5
   2    1L   10L 3.1E-03    0  1.68083225E+02 0.0E+00    0    5
   3    5A   11L 1.2E-02    0  1.57176475E+02 0.0E+00    0    4


 Itn Jdel  Jadd     Step Ninf  Sinf/Objective Norm gZ   Zr  Art
   4    4A   12L 3.2E-02    0  1.38528925E+02 0.0E+00    0    3
   5    3A   13L 6.9E-02    0  1.11295925E+02 0.0E+00    0    2
   6    2A   14L 1.3E-01    0  7.41228000E+01 0.0E+00    0    1
   7    1A    1U 8.4E-01    0 -5.85162625E+01 0.0E+00    0    0
   8   13L    0  1.0E+00    0 -8.72144740E+01 1.3E-15    1    0


 Itn Jdel  Jadd     Step Ninf  Sinf/Objective Norm gZ   Zr  Art
   9    1U    6U 2.5E+00    0 -3.12744888E+02 1.4E+02    1    0
  10    0     1L 1.4E-01    0 -5.62265012E+02 0.0E+00    0    0
  11   14L    7U 1.3E-01    0 -6.21487825E+02 0.0E+00    0    0

 Exit from QP problem after   11 iterations.  Inform =  0


                     QPOPT  ---  Version 1.0-10     Sep  1995
                     ========================================

 Itn Jdel  Jadd     Step Ninf  Sinf/Objective Norm gZ   Zr  Art
   0    0     0  0.0E+00    3  2.35500000E+01 1.7E+00    0    3
   1    2U   10L 4.0E+00    2  1.96000000E+01 1.4E+00    0    3
   2    4U   12L 7.8E+00    1  1.17500000E+01 1.0E+00    0    3
   3    6U   14L 1.2E+01    0  0.00000000E+00 0.0E+00    0    3
 Itn     3 -- Feasible point found.
   3    0     0  0.0E+00    0  8.66526437E+02 1.5E+02    1    2


 Itn Jdel  Jadd     Step Ninf  Sinf/Objective Norm gZ   Zr  Art
   4    0     9L 1.0E-01    0  4.98244375E+01 0.0E+00    0    2
   5    2A   11L 4.5E-01    0 -5.62265013E+02 0.0E+00    0    1
   6    1A    6U 5.7E-13    0 -5.62265013E+02 0.0E+00    0    0
   7   14L    7U 1.3E-01    0 -6.21487825E+02 0.0E+00    0    0

 Exit from QP problem after    7 iterations.  Inform =  0
</pre>

==The Print File==

The Print file records specified options, error messages, a detailed iteration log, and the final solution. The print file is specified in ''Prob.SOL.PrintFile''.

===Constraint numbering and status===

Items Jdel and Jadd in the iteration log are the same as in the Summary file. Please see [[#Constraint numbering and status]].

===The iteration log===

When PrintLevel ''>= ''5, a line of output is produced at every iteration. The quantities printed are those in effect ''on completion ''of the iteration. Several items are the same as in the Summary file. Please see [[#The iteration log]].

{|class="wikitable"
|Itn||Same as Summary file. 
|-valign="top"
|Jdel||Same as Summary file. 
|-valign="top"
|Jadd||Same as Summary file. 
|-valign="top"
|Step||Same as Summary file. 
|-valign="top"
|Ninf||Same as Summary file. 
|-valign="top"
|Sinf/Objective||Same as Summary file.
|-valign="top"
|Bnd||is the number of simple bound constraints in the current working set.
|-valign="top"
|Lin||is the number of general linear constraints in the current working set. 
|-valign="top"
|Art||Same as Summary file.
|-valign="top"
|Zr||Same as Summary file. Zr = n ''- ''(Bnd + Lin + Art).

The number of columns of ''Z ''(see [[#Introduction]]) can be calculated as Nz = n''-''(Bnd+Lin) = Zr+Art.

If Nz is zero, ''x ''lies at a vertex of the feasible region.
|-valign="top"
|Norm gZ||Same as Summary file.
|-valign="top"
|NOpt||is the number of nonoptimal Lagrange multipliers at the current point.  NOpt is not printed if the current x is infeasible or no multipliers have been calculated. At a minimizer, NOpt will be zero.
|-valign="top"
|Min LM||is the value of the Lagrange multiplier  associated with  the deleted constraint.  If the Min LM is negative, a lower bound constraint has been deleted, if Min LM is positive, an upper bound constraint has been deleted. If no multipliers are calculated during a given iteration, Min LM will be zero.
|-valign="top"
|Cond T||is a lower bound on the condition number of the working-set matrix ''W ''.
|-valign="top"
|Cond Rz||is a lower bound on the condition number of the triangular factor ''R ''(the Cholesky factor of the current reduced Hessian ''HR '', whose dimension is Zr).  If the problem type is LP, Cond Rz is not printed.
|-valign="top"
|Rzz||is the last diagonal element ''&omega;'' of the matrix ''D ''associated with the ''R<sup>T</sup>DR ''factorization of the reduced Hessian ''H<sub>R</sub>  ''(see [[#Introduction]]). Rzz is only printed if ''H<sub>R</sub>  ''is not positive definite (in which case  ''&omega; ''= 1).  If the printed value of Rzz is small in absolute value, then ''H<sub>R</sub>  ''is approximately singular. A negative value of Rzz implies that the objective function has negative curvature on the current working set.
|}

===Printing the solution===

When PrintLevel = 1 or PrintLevel ''>= ''10, the final output from qpopt includes a listing of the status of every variable and constraint. Numerical values that are zero are printed as ".".  In the "Variables" section, the following output is given for each variable ''x<sub>j</sub>  ''(''j ''= 1 to n).

{|class="wikitable"
|Variable||gives ''j'', the number of the variable.
|-valign="top"
|State||gives the state of the variable. The possible states are as follows, where ''&delta;''is the Feasibility tolerance.

{|class="wikitable"
|FR||The variable lies between its upper and lower bound.
|-valign="top"
|EQ||The variable is a fixed variable, with ''x<sub>j</sub>'' equal to its upper and lower bound.
|-valign="top"
|LL||The variable is active at its lower bound (to within ''&delta;''). 
|-valign="top"
|UL||The variable is active at its upper bound (to within ''&delta;''). 
|-valign="top"
|TF||The variable is temporarily fixed at its current value.
|-valign="top"
|<nowiki>--</nowiki>||The lower bound is violated by more than ''&delta;''.
|-valign="top"
|<nowiki>++</nowiki>||The upper bound is violated by more than ''&delta;''.
|}

A key is sometimes printed before the State  to give some additional information about the state of a variable.

{|class="wikitable"
|-valign="top"
|A||''Alternative optimum possible. ''The variable is active at one of its bounds, but its Lagrange multiplier is essentially zero. This means that if the variable were allowed to start moving away from its bound, there would be no change to the objective function. The values of the other free variables ''might ''change, giving a genuine alternative solution. However, if there are any degenerate variables (labeled D), the actual change might prove to be zero, since one of them could encounter a bound immediately. In either case, the values of the Lagrange multipliers might also change.
|-valign="top"
|D||''Degenerate. ''The variable is free, but it is equal to (or very close to) one of its bounds.
|-valign="top"
|I||''Infeasible. ''The variable is currently violating one of its bounds by more than ''&delta;''.
|}
|-valign="top"
|Value||is the final value of the variable ''x<sub>j</sub> ''.
|-valign="top"
|Lower bound||is the lower bound specified for ''x<sub>j</sub> ''. "None" indicates that bl(''j'') ''<= -''bigbnd.
|-valign="top"
|Upper bound||is the upper bound specified for ''x<sub>j</sub> ''. "None" indicates that bu(''j'') ''>= ''bigbnd.
|-valign="top"
|Lagr multiplier||is the Lagrange multiplier  for the associated bound. This will be zero if State  is FR. If  x is optimal, the multiplier  should be non-negative if State  is LL, and non-positive if State  is UL.
|-valign="top"
|Slack||is the difference between the variable "Value" and the nearer of its (finite) bounds bl(''j'') and bu(''j'').   A  blank entry  indicates that  the associated  variable is not bounded (i.e., bl(''j'')  ''<='' ''-''bigbnd and bu(''j'') ''>= ''bigbnd). 
|}

In the "Constraints" section, similar output is given for each constraint ''a<sub>i</sub><sup>T</sup>x'', ''i ''= 1 to nclin.  The word "variable" must be replaced by "constraint", and ''x<sub>j</sub>  ''should be changed to ''a<sub>i</sub><sup>T</sup>x'', and (''j'') should be changed to (nclin + ''i''). "Movement off a constraint" means allowing the entry in the slack  column to become positive.

===Interpreting the printout===

The input data for qpopt should always be checked (even if it terminates with inform  = 0!). Two common sources of error are uninitialized variables and incorrectly dimensioned array arguments. The user should check that all components of A, bl, bu and x are defined on entry to qpopt, and that qpHess computes all relevant components of Hx.

In the following, we list the different ways in which qpopt terminates abnormally and discuss what further action may be necessary.

{|class="wikitable"
|Underflow||A single underflow will always occur if machine constants are computed automatically (as in the dis- tributed version of QPOPT). Other floating-point underflows may occur occasionally, but can usually be ignored.
|-valign="top"
|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 Feasibility tolerance. If the message recurs, the offending linearly dependent constraint (with index "''j''") must be removed from the problem. If a warning message did not precede the fatal overflow, contact the authors.
|-valign="top"
|inform  = 3||The problem appears to have no feasible point. Check that there are no conflicting constraints, such as ''x''<sub>1</sub>  ''= ''1, ''x''<sub>2</sub>  ''= ''2 and ''x''<sub>1</sub> + ''x''<sub>2</sub>  = 0. If the data for the constraints are accurate to the absolute precision ''s'', make sure that the Feasibility tolerance is ''greater ''than ''s''. For example, if all elements of A are of order unity and are accurate to only three decimal places, the Feasibility tolerance should be at least 10<sup>''-''3</sup>.
|-valign="top"
|inform  = 4||One of the iteration  limits  may be too small.  (See Feasibility Phase and Optimality Phase.) Increase the appropriate limit  and rerun qpopt.
|-valign="top"
|inform  = 5||The Maximum  Degrees of  Freedom is too small. Rerun qpopt with a larger value (possibly using the warm start facility to specify the initial  working set).
|-valign="top"
|inform  = 6||An input parameter is invalid. The printed output will indicate which parameter(s) must be redefined.

Rerun with corrected values.
|-valign="top"
|inform  = 7||The specified problem type was not FP, LP, QP1, QP2, QP3, or QP4.  Rerun qpopt with Problem type set to one of these values.
|}