[ top | up ]

Solve a Quadratic Programming Problem

Usage

solve.QP(Dmat, dvec, Amat, bvec, meq=0, miter=1000, factorized=F)

Arguments

Dmat an n times n matrix appearing in the quadratic function to be minimized.
dvec a vector of length n appearing in the quadratic function to be minimized.
Amat an n times q matrix defining the q constraints under which we want to minimize the quadratic function.
bvec a vector of length q holding the values of b0 (defaults to zero).
meq the first meq constraints are treated as equality constraints, all further as inequality constraints. 0 <= meq <= q, defaults to 0.
miter maximum number of iteration allowed in the algorithm. (Actually not necessary since the algorithm is guaranteed to converge if D is positive definite and the constraints are consistent. Failure of either is detected, but miter is kept as additional safeguard.)
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.
solution a vector of length n containing the solution of the quadratic programming problem.
value scalar, the value of the quadratic function at the solution
unconstrained.solution a vector of lenth n containing the unconstrained minimizer of the quadratic function.
iterations a vector of length 2, the first component contains the number of iterations the algorithm needed, the second indicates how often constraints became inactive again after becoming active first. vector of length p containing the indices of the active constraints at the solution.

Description

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

Value

a list with the following components:

References

Goldfarb, D. and Idnani, A. (1982). Dual and Primal-Dual Methods for Solving Strictly Convex Quadratic Programs, in J.P. Hennart (ed.), Numerical Analysis, Proceedings, Cocoyoc, Mexico 1981, Vol. 909 of Lecture Notes in Mathematics, 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

solve.QP.compact

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)
Amat       <- matrix(c(-4,-3,0,2,1,0,0,-2,1),3,3)
bvec       <- c(-8,2,0)
solve.QP(Dmat,dvec,Amat,bvec=bvec)