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.

On January 1, 2017, there will be a new release of MINQ called MINQ8.

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/

For the global optimization of indefinite quadratic programs, one may try to use MINQ releatedly with multiple random starting points. Alternatively, try [not developed by us] SCIP (free for academics) or Gurobi (commercial).

Global (and Local) Optimization

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

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