quadratic programming

[Dirk Eddelbuettel]

  "John" == John W Eaton <address@hidden> writes:
  John> We could definitely use a good free QP solver.

I forgot to add earlier that I often use solve.QP from the GNU R package
'quadprog'  (on cran.r-project.org and its mirrors).  If someone wanted to
port this, it might be a good start -- and it is GPL'ed according to
DESCRIPTION file included with the R package. 

I include its help page below.

Dirk


solve.QP              package:quadprog              R Documentation

Solve a Quadratic Programming Problem

Description:

     This routine implements the dual method of Goldfarb and Idnani
     (1982, 1983) for solving quadratic programming problems.

Usage:

     solve.QP        (Dmat, dvec, Amat,       bvec, meq=0, factorized=FALSE)
     solve.QP.compact(Dmat, dvec, Amat, Aind, bvec, meq=0, factorized=FALSE)

Arguments:

    Dmat: matrix appearing in the quadratic function to be minimized.

    dvec: vector appearing in the quadratic function to be minimized.

    Amat: For `solve.QP()':
          matrix defining the constraints under which we want to
          minimize the quadratic function.

          For `solve.QP.compact()':
          matrix containing the non-zero elements of the matrix A that
          defines the constraints.  If mi denotes the number of
          non-zero elements in the i-th column of A then the first mi
          entries of the i-th column of `Amat' hold these non-zero
          elements. (If maxmi denoted the maximum of all mi, then each
          column of `Amat' may have arbitrary elements from row mi+1 to
          row maxmi in the i-th column) 

    Aind: matrix of integers.  The first element of each column gives
          the number of non-zero elements in the corresponding column
          of the matrix A.  The following entries in each column
          contain the indexes of the rows in which these non-zero
          elements are. 

    bvec: vector holding the values of b0 (defaults to zero).

     meq: the first `meq' constraints are treated as equality
          constraints, all further as inequality constraints (defaults
          to 0). 

factorized: logical flag: if `TRUE', then we are passing R^{-1} (where
          D = R^T R) instead of the matrix D  in the argument `Dmat'.

Value:

     a list with the following components: 

solution: vector containing the solution of the quadratic programming
          problem.

   value: scalar, the value of the quadratic function at the solution.

References:

     Goldfarb, D. and Idnani, A.  (1982). Dual and Primal-Dual Methods
     for Solving Strictly Convex Quadratic Programs.  In Numerical
     Analysis J.P. Hennart, ed. Springer-Verlag, Berlin. pp. 226-239.

     Goldfarb, D. and Idnani, A. (1983). A numerically stable dual
     method for solving strictly convex quadratic programs.
     Mathematical Programming 27, 1-33.

See Also:

     Matrix Inversion with `solve'.

Examples:

     # Assume we want to minimize: -(0 5 0) %*% b + 1/2 b^T b
     # under the constraints:      A^T b >= b0
     # with b0 = (-8,2,0)^T
     # and      (-4  2  0)
     #      A = (-3  1 -2)
     #          ( 0  0  1)
     # we can use solve.QP as follows:
     #
     Dmat       <- matrix(0,3,3)
     diag(Dmat) <- 1
     dvec       <- c(0,5,0)
     bvec       <- c(-8,2,0)

     Amat0       <- matrix(c(-4,-3,0, 2,1,0, 0,-2,1),3,3)
     solve.QP(Dmat,dvec, Amat0, bvec=bvec)

     # Now with solve.QP.compact :
     #
     Aind <- rbind(c(2,2,2),
                   c(1,1,2),
                   c(2,2,3))
     Amat <- rbind(c(-4,2,-2),
                   c(-3,1, 1))
     solve.QP.compact(Dmat,dvec,Amat,Aind,bvec=bvec)


-- 
According to the latest figures, 43% of all statistics are totally worthless.



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------