[R] Quadratic programming

[Berwin A Turlach]

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

=========================== Full address =============================
Berwin A Turlach                            Tel.: +65 6516 4416 (secr)
Dept of Statistics and Applied Probability        +65 6516 6650 (self)
Faculty of Science                          FAX : +65 6872 3919       
National University of Singapore     
6 Science Drive 2, Blk S16, Level 7          e-mail: statba at nus.edu.sg
Singapore 117546                    http://www.stat.nus.edu.sg/~statba