Re: help in modifying __qp__.cc

[Claude Lacoursière]

[If one wants to remove redundant constraints then one has to solve "nin"
[LPs (where "nin" is the number of rows of Ain). This preprocessing in
[most cases would take more time then solving the QP itself.

I solve QP problems with redundant constraints all the time,
both in my research work and inside a commercial package.
The technique I use is similar that of interior point
method, namely, to perturb the system matrix along the
diagonal with a small scalar. The active set matrix A is
replaced with A + eps*eye(size(A)) or A +
eps*speye(size(A)).  This perturbation is then removed
iteratively to correctly identify the active set of the
original QP.  This amounts to relaxing constraints so
conflicting ones can be active at the same time with slight
violations.  The theory for this is found in:

@Article{dunlap:1993:sml,
  author =       "K. L. Dunlap and M. M. Kostreva",
  title =        "Solving More Linear Complementarity
  Problems with
                 {Murty}'s {Bard-}Type Algorithm",
  journal =      j-optimization-theory-and-applications,
  volume =       "77",
  number =       "3",
  pages =        "497--522",
  year =         "1993",
}

The paper cited considers the context of LCPs but it applies
particularly well to QPs.  

I could put some time collaborating on this.

For the rest of the discussion on the interface, I agree
with JWE that extra abstraction would help.  Gabriella is
right also that rank evaluation is not the right way to go
since there might be several constraints on the same
equations, which brings rank deficiency if the active set is
not properly identified and both constraints end up active
at the same time. 

/C

-- 
Claude Lacoursière
HPC2N/VRlab, MIT Huset C240, Umeå Universitet, 901 87 Umeå,  SWEDEN
MOBILE: +46 (0)70 675 42 42 Tél: +46 90 786 92 33 FAX: +46 (0)90 786 61 26