The quadratic programming problem involves minimization of a quadratic function subject to linear constraints. Most codes use the formulation
where is symmetric, and the
index sets
and
specify the inequality and equality
constraints, respectively.
The difficulty of solving the quadratic programming problem depends largely on the
nature of the matrix Q. In convex quadratic programs, which are
relatively easy to solve, the matrix Q is positive semidefinite. If Q
has negative eigenvalues-nonconvex quadratic programming-then the objective
function may have more than one local minimizer. An extreme example is the problem
which has a minimizer at any
with
for i = 1,..., n - a total of
local minimizers.
The codes in the BQPD, LINDO, LSSOL, PORT 3, and QPOPT packages are based on active set methods. After finding a feasible point during an initial phase, these methods search for a solution along the edges and faces of the feasible set by solving a sequence of equality-constrained quadratic programming problems. Active set methods differ from the simplex method for linear programming in that neither the iterates nor the solution need be vertices of the feasible set. When the quadratic programming problem is nonconvex, these methods usually find a local minimizer. Finding a global minimizer is a more difficult task that is not addressed by the software currently available.
Equality-constrained quadratic programs arise, not only as subproblems in solving the general problem, but also in structural analysis and other areas of application. Null-space methods for solving
find a full-rank matrix such
that
spans the null space of
. This matrix can be computed with
orthogonal factorizations or, in the case of sparse problems, by
factorization of a submatrix of
, just as in the simplex method
for linear programming. Given a feasible vector x0 , we can express any other
feasible vector
in the form
for some . Direct computation
shows that the equality-constrained subproblem (1.2) is
equivalent to the unconstrained subproblem
If the reduced Hessian matrix
is positive definite, then the unique solution
of this subproblem can be obtained by solving the
linear system
The solution of the
equality-constrained subproblem (1.2) is then recovered by
using (1.3). Lagrange multipliers can be computed from
by noting
that the first-order condition for optimality in (1.2) is
that there exists a multiplier vector
such that
If
has full rank, then
is the unique set of multipliers. Most codes uses null-space methods. Range-space
methods for (1.2) can be used when Q is
positive definite and easy to invert, for example, diagonal or block-diagonal. In this
approach, the solution and the multiplier vectors are calculated from the formulae
Although this approach works only for a subclass of problems, there are many applications in which it is useful.
Active set methods for the inequality-constrained problem (1.1) solve a sequence of equality-constrained problems. Given a
feasible , these methods find a
direction
by solving the
subproblem
where q is the objective function
and is a working set
of constraints. In all cases
is a subset of
the set of constraints that are active at . Typically,
either is equal to
or else has one fewer index than
.
The working set is updated at each iteration with the aim of determining the set
of active constraints at a solution
. When
is equal to
, a local
minimizer of the original problem can be obtained as a solution of the
equality-constrained subproblem. The updating of
depends on the solution of
subproblem (1.4).
Subproblem (1.4) has a solution if the reduced Hessian
matrix is positive definite.
This is always the case if Q is positive definite. If subproblem (1.4) has a solution
, we compute the largest possible
step
that does not violate any constraints, and we set
,
The step would take us to
the minimizer of the objective function on the subspace defined by the current working
set, but it may be necessary to truncate this step if a new constraint is encountered. The
working set is updated by including in
all constraints active at
.
If the solution to subproblem (1.4) is , then
is the minimizer of the objective
function on the subspace defined by
. First-order optimality
conditions for (1.4) imply that there are multipliers
such that
If
for
, then
is a local minimizer of problem (1.1). Otherwise, we obtain
by deleting one of the indices
for which
. As in the case of linear programming, various pricing
schemes for making this choice can be implemented.
If the reduced Hessian matrix is indefinite, then subproblem (1.4)
is unbounded below. In this case we need to determine a direction
such that
is unbounded below, using techniques based on
factorizations of the reduced Hessian matrix. Given
, we compute
as in (1.5) and define
.
The new working set is
obtained by adding to
all constraints active at
.
A key to the efficient implementation of active set methods is the reuse of information from solving the equality-constrained subproblem at the next iteration. The only difference between consecutive subproblems is that the working set grows or shrinks by a single component. Efficient codes perform updates of the matrix factorizations obtained at the previous iteration, rather than calculating them from scratch each time.
The LSSOL package (duplicated
in NAG) is specifically designed
for convex quadratic programs and linearly constrained linear least squares problems. It
is not aimed at large-scale problems; the constraint matrices and the Hessian Q are all specified in dense storage
format. The quadratic programming routine in NLPQL has the same properties. IMSL contains codes for dense
quadratic programs. If the matrix Q is not positive definite, it is replaced by
,
where is chosen large enough
to force convexity.
BQPD uses a null-space method
to solve quadratic programs that are not necessarily convex. The linear algebra operations
are performed in a modular way; the user is allowed to choose between sparse and dense
matrix algebra. The reduced Hessian matrix is, however, processed as a dense matrix, even
when sparse techniques are used to handle Q and the constraints. The code is
efficient for large-scale problems when the size of the working set is close to . LINDO also takes account of
sparsity, while MATLAB, and QPOPT (also available in the NAG library) are designed for dense
quadratic programs that are not necessarily convex.
Linear least squares problems are special instances of convex quadratic programs that
arise frequently in data-fitting applications. The linear least squares problem
where and
, is a special case of problem (1.1); we can see this by replacing
by
and
by
in (1.1). In general, it is
preferable to solve a least squares problem with a code that takes advantage of the
special structure of the least squares problem (for example, LSSOL).
Algorithms for solving linear least squares problems tend to rely on null-space active
set methods. For a least squares problem the null-space matrix can be obtained from the
decomposition of
; explicit formation of
is avoided, since
is usually
less well conditioned than
.
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Updated 28 March 1996
