Re: [R] Quadratic programming

From: Berwin A Turlach <berwin_at_maths.uwa.edu.au>
Date: Wed, 5 Dec 2007 20:37:43 +0800

G'day Serge,

On Wed, 5 Dec 2007 11:25:41 +0100
"de Gosson de Varennes Serge (4100)"
<serge.de.gosson.de.varennes_at_forsakringskassan.se> wrote:

> I am using the quadprog package and its solve.QP routine to solve and
> quadratic programming problem with inconsistent constraints, which
> obviously doesn't work since the constraint matrix doesn't have full
> rank.

I guess it will help to fix some terminology first. In my book, "inconsistent constraints" are constraints that cannot be fulfilled simultaneously, e.g. something like "x_1 <= 3" and "x_1 >= 5" for an obvious example. Thus, a problem with inconsistent constraints cannot be solved, regardless of the rank of the constraint matrix. (Anyway, that matrix is typically not square, so would be be talking about full column rank or full row rank?)

Of course, it can happen that the constraints are consistent but that there are some redundancy in the specified constraints, e.g. a simply case would be "x_1 >= 0", "x_2 >= 0" and "x_1+x_2 >= 0"; if the first two constraints are fulfilled, then the last one is automatically fulfilled too. In my experience, it can happen that solve.QP comes to the conclusion that a constraint that ought to be fulfilled, given the constraints that have already been enforced, is deemed to be violated and to be inconsistent with the constraints already enforced. In that case solve.QP stops, rather misleadingly, with the message that the constraints are inconsistent.

I guess the package should be worked over by someone with a better understanding of the kind of fudges that do not come back to bite and of finite precision arithmetic than the original author's appreciation of such issues when the code was written. ;-))

> A way to solve this is to "perturb" the objective function and
> the constraints with a parameter that changes at each iteration (so
> you can dismiss it), but that's where it gets tricky! Solve.QP
> doesn't seem to admitt constant terms, it need Dmat (a matrix) and
> dvec (a vector) as defined in the package description. Now, some
> might object that a constant is a vector but the problem looks like
> this
>
> Min f(x) = (1/2)x^t Q x + D^t x + d

It is a bit unclear to me what you call the constant term. Is it `d'? In that case, it does not perturb the constraints and it is irrelevant for the minimizer of f(x); also for the minimizer of f(x) under linear constraints. Regardless of d, the solution is always the same. I do not know of any quadratic programming solver that allows `d' as input, probably because it is irrelevant for determining the solution of the problem.

> Can anyone help me, PLEASEEEEEEE?

In my experience, rescaling the problem might help, i.e. use Q* = Q/2 and D*=D/2 instead of the original Q and D; but do not forget to rescale the constraints accordingly.

Or you might want to try another quadratic program solver in R, e.g. ipop() in package kernlab.

Hope this helps.

Best wishes,

        Berwin


R-help_at_r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. Received on Wed 05 Dec 2007 - 12:42:59 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Wed 05 Dec 2007 - 13:30:17 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.