MINQ: General Definite and Bound Constrained Indefinite Quadratic Programming


MINQ is a Matlab program for bound constrained indefinite quadratic programming based on rank 1 modifications. It finds a local optimizer of the optimization problem

     min    fct = c^T x + 0.5 x^T G x 
     s.t.   x in [xu,xo]   (componentwise)
where G is a symmetric n x n matrix, not necessarily semidefinite, and infinite bounds are allowed. (If G is positive semidefinite, any local optimizer is global, so it finds the global optimum.)

The method consists of a combination of coordinate searches and subspace minimization steps (safeguarded equality-constrained QP-steps when the coordinate searches no longer change the active set). Rank 1 updates (in a format suited for both the dense and sparse case) are used to keep the linear algebra cheap.

In the sparse case, it is assumed that the variables are already ordered such that the symbolic factorization of G is sparse.

MINQ can also be used for general definite quadratic programming since the dual is simply constrained. Based on this, the Matlab program MINQDEF solves the optimization problem

    min    fct = c^T x + 0.5 x^T G x 
    s.t.   A x >= b, with equality at indices with eq=1
where G is a positive definite symmetric n x n matrix, and the Matlab program MINQSEP solves the same problem with definite diagonal G. (In the sparse case, it is now assumed that the variables are already ordered such that the symbolic factorizations of G and AG^(-1)A^T are sparse.)

As an application, a robust least squares solver RLS is included. RLS solves a linear least squares problem

    min    ||Ax-b||_2^2  
    s.t.   |x-x0|<=r
If r has the default value, RLS it can be used to regularize least squares problems. In ill-conditioned cases, it yields much better approximate solutions than x=A\b, though at a time penalty.

The required m-files can be downloaded as the gzipped tar file minq5.tar.gz (for Matlab 5; 8K). This version was revised on August 2, 2000 to improve the behavior for sparse problems, taking out some slow Matlab constructs, on November 30, 2000 to add RLS, and on July 5, 2001 to improve the subspace step. The individual files may be viewed from the minq5 directory.

The Matlab 4 version (minq.tar.gz; 8K; no sparse facilities, no RLS) is no longer supported.


Source: http://www.mat.univie.ac.at/~neum/software/minq/

If you want to reference MINQ, you may use the following format:

Arnold Neumaier, MINQ - General Definite and Bound Constrained Indefinite Quadratic Programming, WWW-Document, 1998. http://www.mat.univie.ac.at/~neum/software/minq/


Global (and Local) Optimization

my home page (http://www.mat.univie.ac.at/~neum)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)