RFC: quadprog/lsqlin with __qp__ (Re: GSoC 2015, optim)

[Olaf Till]

Hi Asma,

On Thu, May 21, 2015 at 10:44:46AM -0700, AsmaA wrote:
> Hi Olaf,
> 
> 
> Olaf Till-2 wrote
> > In the future (GSoC?) quadprog and lsqlin should IMO be changed to
> > directly call __qp__, not qp.m. Among other things this should make
> > ordering of the 'lambda' output feasible.
> 
> I spent some time studying some quadratic programming basics (Lagrange
> multipliers, KKT conditions, active set algorithm), qp.m and __qp__.cc to
> see how lambda output is ordered.
> 
> I also checked a few different examples and compared the Lagrange
> multipliers from both quadprog (MATLAB) and  qp (Octave).
> 
> quadprog returns Lagrange multipliers in a structure (with fields upper,
> lower, eqlin, ineqlin) and the multipliers corresponding to the constraints
> not provided are left empty.  
> 
> In qp, lambda is a column vector with Lagrange multipliers associated to the
> constraints in the following order: equality constraints, lower bounds,
> upper bounds and other inequality constraints.
> The length of lambda vector output from qp depends on the number of
> different constraints provided as  input. (more specifically, active
> constraints- line 460 [1])

Only read lines 460 to 477 for now, but I'm pretty sure that the
number of _active_ conastraints is only important internally to
__qp__, to fill in the returned lambda. The length of the returned
lambda does not seem to depend on how many of the inequality
constraints are active, for inactive constraints the elements of
lambda remain zero. So your first statement (before the parantheses)
on the length should be true.

> To put the multipliers in their respective fields in a structure, the
> knowledge of inputs is required (size, inf check, etc.) and a function like
> qp that does the input processing to call __qp__ can make such ordering
> feasible. 
> 
> Have I got it right?

Yes, I think you got it right. Note that I didn't check the order
within the lambda of qp.m now.


RFC:

The problem with wrapping qp.m is that this order (e.g. the position
of the bounds constraints within the inequality constraints) is not
specified by qp.m and principally might change; also, as you
mentioned, qp.m seems to strip INF constraints before calling __qp__
but does not process the lambda (returned by __qp__) accordingly, and
this behaviour is also not specified and might change. So it could be
better to wrap __qp__ directly than considering how qp.m processes the
constraints.

On the other hand, __qp__ also does not specify whether equality or
inequality constraints come first in lambda, and __qp__ is an internal
function of Octave, potentially subject to interface changes without
notice. So one could argue that it would be safer to first change qp.m
(re-suppling zeros to lambda where INF constraints were stripped,
specifying the order within lambda in the documentation) and then to
wrap qp.m, not __qp__. But my influence on what is in qp.m is very
limited.

Maybe someone else has comments on this. A possibility is that either
you or me supplies a patch to qp.m, and the further 'strategy' is
decided depending on whether the patch will be applied in time or not.

Olaf

PS: We'd better mark different larger subtopics with different
'Subject:' lines (done for this).

-- 
public key id EAFE0591, e.g. on x-hkp://pool.sks-keyservers.net

signature.asc
Description: Digital signature