QPOPT

Sovles linear and quadratic programming problems of the following general form:

where A is an m_L x n matrix (m_L may be zero) and f(x)is one of the following: with c an n-vector. In QP1 and QP2, there is no restriction on H apart from symmetry. If the quadratic function is convex, a global minimum is found; otherwise, a local minimum is found. The method used is most efficient when many constraints or bounds are active at the solution. If H is positive semi-definite, it is usually more efficient to use the package LSSOL.

QPOPT uses a two-phase, active-set method based on an inertia-controlling method that maintains a Cholesky factorization of the reduced Hessian. QPOPT treats all matrices as dense and is not intended for sparse problems.

The QPOPT package contains approximately 14,700 lines of Fortran, of which about 75% are comments. The source code and example program for QPOPT are distributed on a floppy disk. The code is also available via Internet using ftp. A MATLAB interface for QPOPT is also available.

QPOPT includes calls to both Level-1 (vector) and Level-2 (matrix-vector) Basic Linear Algebra Subroutines (BLAS). They may be replaced by versions of the BLAS routines that have been tuned to a particular machine.

The method of QPOPT is similar to the method of QPSOL, which was distributed by Stanford University between 1983 and 1991. However, QPOPT is a substantial improvement over QPSOL in both functionality and reliability.

QPOPT is written in ANSI Fortran 77 and should run without alteration on any machine with a Fortran 77 compiler. QPOPT is essentially identical to the routine E04nff of the NAG Fortran Library. E04nff was introduced at Mark 16. The code was developed on a DECstation 3100 using the MIPS f77 compiler and has been installed on most types of PC, workstation, and mainframe.

Need more info?

Contact:

Prof. Walter Murray                   Prof. Philip E. Gill
Department of Operations Research     Department of Mathematics 
Terman Engineering Center             University of California, San Diego
Stanford University                   9500 Gilman Drive       
Stanford, CA 94305-4022 	      La Jolla, CA 92093-0112

References:

P.E. Gill and W. Murray, Numerically stable methods for quadratic programming, Math. Programming 14 (1978), pp. 349--372.

P.E. Gill, W. Murray, M.A. Saunders, and M.H. Wright, Inertia-controlling methods for general quadratic programming, SIAM Rev. 33 (1991), pp. 1--36.

NAG Fortran Library Manual, Mark 15, NAG Ltd., 1991.

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]