« Previous « Start » Next »
5 QPOPT details
5.1 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). The method follows Gill and
Murray [
13] and is described in [
34]. Here we
briefly summarize the main features of the method.
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 L ≤
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 [
35]). 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 2.8
x is defined by
where the
step length α 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.)
5.1.2 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
mw denote the number of
constraints in the working set (including bounds), and let
W
denote the associated
mw×
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,
In order to compute
p, a
TQ factorization of
W is used:
where
T is a nonsingular
mw ×
mw upper-triangular matrix,
and
Q is an
n ×
n nonsingular matrix constructed from a
product of orthogonal transformations(see [
29]). If the columns of
Q are partitioned so that
Q = ( Z Y ),
where
Y is
n×
mw and
Z is
n ×
n Z (where
n Z =
n
−
mw), then the columns of
Z form a basis for the null space of
W. Let
n R be an integer such that 0 ≤
n R ≤
n Z, and let
Z R denote a matrix whose
n R columns are a subset of the
columns of
Z. (The integer
n R is the quantity “
Zr” in the
printed output from
qpopt). In many cases,
Z R will include
all the columns of
Z. The direction
p will satisfy
(
26) if
where
p R is any
n R-vector.
5.1.3 The reduced Hessian
Let
g Q and
H Q denote the
transformed gradient and
transformed Hessian:
g Q = QT g(x) and H Q = QT H Q.
The first
n R elements of the vector
g Q will be denoted by
g R,
and the first
n R rows and columns of the matrix
H Q will be
denoted by
H R. The quantities
g R and
H R are known as the
reduced gradient and
reduced Hessian of
q(
x),
respectively. Roughly speaking,
g R and
H R describe the first
and second derivatives of an
unconstrained problem for the
calculation of
p R.
At each iteration, a triangular factorization of
H R is available.
If
H R is positive definite,
H R =
RT R, where
R is the
upper-triangular Cholesky factor of
H R. If
H R is not positive
definite,
H R =
RT DR, where
D =
diag(1, 1, ..., 1,
ω), with ω ≤ 0.
In QPOPT, the computation is arranged so that the reduced-gradient
vector is a multiple of
e R, a vector of all zeros except in the
last (
n Rth) position. This allows
p R in (
28) to be
computed from a single back-substitution,
where γ 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 R is not positive definite,
p R satisfies
p RT H R p R < 0 and
g RT p R ≤ 0,
allowing the objective function to be reduced by any step of the
form
x + α
p, α > 0.
5.1.4 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 λ are
defined from the equations
A Lagrange multiplier λ
j corresponding to an inequality
constraint in the working set is said to be
optimal if
λ
j ≤ σ when the associated constraint is at its
upper bound, or if λ
j ≥ − σ when the associated
constraint is at its
lower bound, where σ 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 (with index
Jdel; see
Section
5.6).
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 λ
j corresponding to
an inequality constraint in the working set will be such that
−(1+σ) ≤ λ
j ≤ σ when the associated
constraint is at its
upper bound, and −σ ≤ λ
j
≤ 1+σ when the associated constraint is at its
lower
bound. Lagrange multipliers for equality constraints will satisfy
|λ
j| ≤ 1 + σ.
If the reduced gradient is not zero, Lagrange multipliers need not
be computed and the search direction
p is given by
Z R p R (see
(
29)). The step length is chosen to maintain
feasibility with respect to the satisfied constraints. If
H R is
positive definite and
x+
p is feasible, α is defined to be
one. In this case, the reduced gradient at 2.8
x will be zero,
and Lagrange multipliers are computed. Otherwise, α is set to
α
M, the step to the “nearest” constraint (with index
Jadd; see Section
5.6). This constraint is
added to the working set at the next iteration.
If the reduced Hessian
H R is not positive definite and α
M
does not exist (i.e., no positive step α
M reaches the
boundary of a constraint not in the working set), then QPOPT
terminates at
x and declares the problem to be unbounded.
5.2 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.
5.2.1 Treatment of simple upper and lower bounds
Bound constraints ℓ ≤
x ≤
u 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
where
( F N ) is part of the matrix
A, and
I N 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
TQ
factorization
F Q F =
( 0
T F ) of the smaller matrix
F
provides the required
T and
Q as follows:
The matrix
Q F 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 F,
Q F and
R are
held explicitly; together with the vectors
QT g, and
QT c.
Products of plane rotations are used to update
Q F and
T F as
the working set changes. The triangular factor
R associated with
the reduced Hessian is updated only during the optimality phase.
5.2.2 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 R 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 R has no rows and columns. Such a matrix is
positive definite by definition.)
Let
H Z denote the first
n Z rows and columns of
H Q =
QT 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 Z. 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 R denote the
columns of
Z corresponding to
R, and let
Z be partitioned as
Z =
( Z R Z A ). A working set for which
Z R defines the
null space can be obtained by including
the rows of Z AT as
“artificial constraints” (with bounds equal to the current value
of
Z AT x). Minimization of the objective function then proceeds
within the subspace defined by
Z R, as described in
Section
5.1.
The artificially augmented working set is given by
so that
p will satisfy
W p = 0
and Z AT p = 0. By
definition of the
TQ factors of
W, we have
3 W Q
= |
|
|
|
|
|
Q
= |
|
|
|
|
|
( Z R Z A Y )
= ( 0 T ),
|
where
Hence the
TQ factors of 3
W are available trivially.
The matrix
Z A is not kept fixed, since its role is purely to
define an appropriate null space; the
TQ 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 A when
Z RT g = 0, since
this simply involves repartitioning
Q. The “artificial”
multiplier vector associated with the rows of
Z AT is equal to
Z AT 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 Section
5.6). The multiplier may have
either sign.
The number of columns in
Z A and
Z R, the Euclidean norm of
Z RT g, and the condition estimator of
R appear in the printed
output as
Art,
Zr,
Norm gZ and
Cond Rz (see
Section
5.6).
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 L ≤
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 Section
5.6). Again, the multiplier may
have either sign.
5.2.3 The anti-cycling procedure
The EXPAND procedure [
32] 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 δ. 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δ to
δ (in steps of 0.5δ/
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δ.
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 δ.)
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
α
M denote the maximum step at which
x +α
M p does not
violate any constraint by more than its feasibility tolerance. All
constraints at distance α (α ≤ α
M) 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.
5.3 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.
5.3.1 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:
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.
5.4 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
−16).
Option: Check frequency i 50 Every
ith
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.
Option: Cold start Cold start
Option: Warm start
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.
Option: Crash tolerance r 0.01 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
ajT x ≥
l will
be included in the initial working set if |
ajT x −
l | ≤
r(1 +
|
l|). If
r < 0 or
r > 1, the default value is used.
Option: Defaults This is a special option to reset all
options to their default values.
Option: Expand frequency i 5 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 Section
5.2.3.
If
i ≥ 9999999, no anti-cycling procedure is invoked.
Option: Feasibility tolerance r √
u 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
−6. 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
Min sum = Yes is requested,
QPOPT will find the minimum value of the sum. 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.
Option: Feasibility Phase Iteration Limit i1 max(50, 5(
n +
m L))
Option: Optimality Phase Iteration Limit i2 max(50, 5(
n +
m L))
The scalars
i1 and
i2 specify the maximum number of iterations
allowed in the feasibility and optimality phases.
Optimality
Phase iteration limit is equivalent to
Iteration limit.
Setting
i1=0 and
Print Level > 0 means that the workspace
needed will be computed and printed, but no iterations will be
performed.
Option: Hessian rows i 0 or
n 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
integer lqptyp, mHess
common /sol1qp/ lqptyp, mHess
For example,
Problem type FP,
LP or
QP4 sets
lqptyp
= 1, 2 or 6 respectively, and
Hessian rows 20 sets
mHess =
20.
Option: Infinite Bound size r 10
20
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.
Option: Infinite Step size r max(
bigbnd,10
20)
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.
Option: Iteration limit i max(50, 5(
n +
m L))
Option: Iters
Option: Itns
This is equivalent to
Optimality Phase iteration limit.
See
Feasibility Phase.
Option: List If
Nolist was previously specified,
List restores output to the Print file whenever an optional
parameter is reset.
Option: Maximum degrees of freedom i n
This places a limit on the storage allocated for the triangular
factor
R of the reduced Hessian
H R. Ideally,
i should be set
slightly larger than the value of
n R expected at the solution.
(See Sections
5.1.2 and
5.1.3.) It
need not be larger than
m N + 1, where
m N is the number of
variables that appear nonlinearly in the quadratic objective
function. For many problems it can be much smaller than
m N.
For quadratic problems, a minimizer may lie on any number of
constraints, so that
n R 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.
Option: Min sum a No 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.
Option: Nolist This suppresses output to the Print file
whenever an optional parameter is reset.
Option: Optimality tolerance r √
u
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.
Option: Print level i 10 This controls the
amount of printing produced by QPOPT as follows.
-
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 TQ factorization
(27) of the working set, and the diagonal elements of the
upper-triangular matrix R (Print file only).
Option: Problem type a QP2
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:
|
|
FP |
|
H and cvec not accessed; |
|
LP |
|
H not accessed, cvec(n) required; |
|
QP1 |
|
H(ldH,*) symmetric, cvec not referenced; |
|
QP2 |
|
H(ldH,*) symmetric, cvec(n); |
|
QP3 |
|
H(ldH,*) upper-trapezoidal, cvec not referenced; |
|
QP4 |
|
H(ldH,*) upper-trapezoidal, cvec(n); |
|
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.
Option: Rank tolerance r 100
u This parameter
enables the user to control the condition number of the triangular
factor
R (see Section
5.1). If ρ
i
denotes the function ρ
i = max{ |
R11|, |
R22|, ...,
|
Rii|}, the dimension of
R is defined to be smallest index
i such that |
Ri+1,i+1| ≤ √
r|ρ
i+1|. If
r ≤
0, the default value is used.
Option: Summary file i 6 This
specifies the unit number for the Summary file (see Section
5.6).
If
i > 0 and
Print Level > 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.
Option: Warm start (See Cold start) .
5.5 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 (≈ 1.1 × 10
−16 in IEEE double-precision
arithmetic).
Check frequency |
|
50 |
|
|
Cold start |
|
|
|
|
Crash tolerance |
|
.01 |
|
|
Expand frequency |
|
5 |
|
|
Feasibility tolerance |
|
1.1e-8 |
|
√u |
Feasibility Phase iteration limit |
|
50 |
|
or 5(n+m L) |
Optimality Phase iteration limit |
|
50 |
|
or 5(n+m L) |
Hessian rows |
|
n |
|
|
Infinite bound size |
|
1.0e+20 |
|
Plus infinity |
Infinite step size |
|
1.0e+20 |
|
|
Iteration limit |
|
50 |
|
or 5(n+m L) |
List |
|
|
|
|
Maximum degrees of freedom |
|
n |
|
|
Min sum |
|
No |
|
|
Optimality tolerance |
|
1.1e-8 |
|
√u |
Print file |
|
9 |
|
|
Print level |
|
10 |
|
|
Problem type |
|
QP |
|
or QP2 |
Rank tolerance |
|
1.1e-14 |
|
100u |
Summary file |
|
6 |
|
Other options may be set as follows:
Defaults |
|
|
|
|
Nolist |
|
|
|
|
Warm start |
|
|
|
|
5.6 The Summary File
The Summary file records an iteration log and error messages. The
file name is set in
Prob.SOL.SummFile.
5.6.1 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).
5.6.2 The iteration log
The following items are printed
after each iteration.
-
Itn
- is the iteration count (including those from the feasibility
phase).
- Jdel
- is the index of the constraint deleted from the
working set. If Jdel is zero, no constraint was deleted.
- Jadd
- is the index of the constraint added to the working
set. If Jadd is zero, no constraint was added.
- 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.
- 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.
- Norm gZ
- is Z RT g, the Euclidean norm
of the reduced gradient with respect to Z R. During the
optimality phase, this norm will be approximately zero after a unit
step.
- Zr
- is the number of columns of Z R (see
Section 5.1). 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.
- Art
- is the number of artificial constraints in the
working set, i.e., the number of columns of Z A (see
Section 5.2). At the start of the optimality
phase, Art provides an estimate of the number of nonpositive
eigenvalues in the reduced Hessian.
5.6.3 Summary file from the example problem
Following is a Summary file example.
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
5.7 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.
5.7.1 Constraint numbering and status
Items
Jdel and
Jadd in the iteration log are the same as in
the Summary file. Please see Section
5.6.1.
5.7.2 The iteration log
When
Print Level ≥ 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 Section
5.6.2.
-
Itn
- Same as Summary file.
- Jdel
- Same as Summary file.
- Jadd
- Same as Summary file.
- Step
- Same as Summary file.
- Ninf
- Same as Summary file.
- Sinf/Objective
- Same as Summary file.
- Bnd
- is the number of simple bound constraints in the
current working set.
- Lin
- is the number of general linear constraints in the
current working set.
- Art
- Same as Summary file.
- Zr
- Same as Summary file.
Zr = n − (Bnd + Lin + Art).
-
-
The number of columns of Z (see Section 5.1)
can be calculated as Nz = n−(Bnd + Lin)
= Zr + Art.
-
-
If Nz is zero, x lies at a vertex of the feasible region.
- Norm gZ
- Same as Summary file.
- 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.
- 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.
- Cond T
- is a lower bound on the condition number of the
working-set matrix W.
- Cond Rz
- is a lower bound on the condition number of the
triangular factor R (the Cholesky factor of the current reduced
Hessian H R, whose dimension is Zr). If the problem type is
LP, Cond Rz is not printed.
- Rzz
- is the last diagonal element ω of the matrix D
associated with the RTDR factorization of the reduced Hessian
H R (see Section 5.1). Rzz is only
printed if H R is not positive definite (in which case ω
1). If the printed value of Rzz is small in absolute value,
then H R is approximately singular. A negative value of Rzz
implies that the objective function has negative curvature on the
current working set.
5.7.3 Printing the solution
When
Print Level = 1 or
Print Level ≥ 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
xj (
j=1 to
n).
-
Variable
- gives j, the number of the variable.
- State
-
gives the state of the variable. The
possible states are as follows, where δ is the Feasibility
tolerance.
- State = FR
-
The variable lies between its upper and lower bound.
- State = EQ
-
The variable is a fixed variable, with xj equal to its
upper and lower bound.
- State = LL
-
The variable is active at its lower bound (to within
δ).
- State = UL
-
The variable is active at its upper bound (to within
δ).
- State = TF
-
The variable is temporarily fixed at its current value.
- State = −−
-
The lower bound is violated by more than δ.
- State = ++
-
The upper bound is violated by more than δ.
-
-
A key is sometimes printed before the State to give some
additional information about the state of a variable.
- State key = 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.
- State key = D
-
Degenerate. The variable is free, but it is equal to (or
very close to) one of its bounds.
- State key = I
-
Infeasible. The variable is currently violating one of
its bounds by more than δ.
- Value
-
is the final value of the variable xj.
- Lower bound
-
is the lower bound specified for xj. “None”
indicates that bl(j) ≤ −bigbnd.
- Upper bound
-
is the upper bound specified for xj. “None”
indicates that bu(j) ≥ bigbnd.
- 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.
- 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
aiT x,
i=1 to
nclin. The word “variable” must
be replaced by “constraint”, and
xj should be changed to
aiT
x, and (
j) should be changed to (
nclin +
i). “Movement
off a constraint” means allowing the entry in the
slack column
to become positive.
5.7.4 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.
-
Underflow
-
A single underflow will always occur if machine constants are
computed automatically (as in the distributed version of QPOPT).
Other floating-point underflows may occur occasionally, but can
usually be ignored.
- Overflow
-
If the printed output before the overflow error contains a
warning about serious ill-conditioning in the working set when
adding the jth 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.
- inform = 3
-
The problem appears to have no feasible point.
Check that there are no conflicting constraints, such as x1 ≥
1, x2 ≥ 2 and x1 + x2 = 0. If the data for the constraints
are accurate to the absolute precision σ, make sure that the
Feasibility tolerance is greater than σ. 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−3.
- inform = 4
-
One of the iteration limits may be too small.
(See Feasibility Phase and Optimality Phase.) Increase the
appropriate limit and rerun qpopt.
- 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).
- inform = 6
-
An input parameter is invalid. The printed output will
indicate which parameter(s) must be redefined. Rerun with corrected
values.
- 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.
« Previous « Start » Next »