NHSE Software Catalog

BQPD

description

http://www.mcs.anl.gov/home/otc/Guide/blurbs/bqpd.html

abstract

Linear and Quadratic programming. Allows upper/lower
bounds on all the variables and constraints.

The code solves quadratic programming (minimization of a
quadratic function subject to linear constraints) and linear
programming problems. If the Hessian matrix Q is positive definite,
then a global solution is found. A global solution is also found in the
case of linear programming (Q=0). When Q is indefinite, a
Kuhn-Tucker point that is usually a local solution is found.

The code implements a null-space active set method with a
technique for resolving degeneracy that guarantees that cycling does
not occur even when round-off errors are present. Feasibility is
obtained by minimizing a sum of constraint violations. The Devex
method for avoiding near-zero pivots is used to promote stability.
The matrix algebra is implemented so that the algorithm can take
advantage of sparse factors of the basis matrix. Factors of the
reduced Hessian matrix are stored in a dense format, an approach
that is most effective when the number of free variables is relatively
small. The user must supply a subroutine to evaluate the Hessian
matrix $Q$, so that sparsity in $Q$ can be exploited. An extreme
case occurs when $Q=0$ and the QP reduces to a linear program.
The code is written to take maximum advantage of this situation, so
that it also provides an efficient method for linear programming.
G2a. linear programming;
G2e. quadratic programming

keywords

numerical library

method

null-space active set method; Devex method

contact

Professor Roger Fletcher
Department of Mathematics and Computer Science
University of Dundee
Dundee DD1 4HN
Scotland, U.K.

reference

R. Fletcher, Resolving degeneracy in quadratic programming,
Numerical Analysis Report NA/135, University of Dundee,
Dundee, Scotland, 1991.