Re: help in modifying __qp__.cc

[Jaroslav Hajek]

On Mon, Nov 3, 2008 at 5:12 PM, John W. Eaton <address@hidden> wrote:
> I'm moving this discussion to the mailing list to see if anyone has
> comments or would like to help out with making a change like I'm
> proposing below.
>
> Thanks,
>
> jwe
>
>
> On 30-Oct-2008, John W. Eaton wrote:
>
> | On 30-Oct-2008, Gabriele Pannocchia wrote:
> |
> | | Hi John,
> | |
> | | after discussing with Steve Wright about the problem of redundant active
> | | constraints (i.e. rank deficient active set matrix) that is not
> | | correctly handled in the current __qp__.cc, I am ready to make a change
> | | which, I think, could improve the robustness of the algorithm
> | | significantly.
> | |
> | | The change requires to solve a linear program for computing the Lagrange
> | | multipliers when the current Aact is not full rank.
> | |
> | | Could you please give me some tips on how I can make a "direct" (i.e.
> | | without feval) call to glpk to solve a problem like:
> | |
> | | min c'*x s.t. C*x=d, D*x<=d
> | |
> | | or in the LP standard form.
> | |
> | | min c'*x s.t. C*x=d, x>=0
> |
> | I'm not an expert in using glpk.  I did not write the interface to it
> | for Octave.  The example in the Octave sources of using glpk directly
> | is in src/DLD-FUNCTIONS/__glpk__.cc in the Octave sources.  If you add
> | direct calls to glpk in __qp__.cc, then we will also need to modify
> | src/Makefile.in so that it links __qp__.o with the glpk library when
> | it creates __qp__.oct.
>
> After giving this some more thought and looking at the __glpk__.cc
> file, it might be best to create another level of abstraction that we
> can add to liboctave.  At the very least, it would probably be good to
> have a function like
>
>  ColumnVector
>  glpk (const ColumnVector& c, const Matrix& C, const ColumnVector& d,
>        const glpk_options& opt);
>
> and probably also
>
>  ColumnVector
>  glpk (const ColumnVector& c, const SparseMatrix& C, const ColumnVector& d,
>        const glpk_options& opt);
>
> to solve the standard problem as you've stated it above.  The
> glpk_options argument would be a class.
>
> We probably also need a way to detect errors/return an error code.
>
> Most of the work is done already in __glpk__.cc, but it would be much
> easier for you to use glpk in __qp__.cc if you could call functions
> with this interface.
>
> Perhaps we should discuss this on the maintainers list.  Someone else
> might be interested in helping out with this job.
>
> jwe
>

An alternative is to rewrite __qp__ as an m-file. It appears to me
that there are no "heavy" loops that would cause problems.

I think that we should make at least a "soft" decision about what
"level" of algorithms is supposed to be in liboctave, in DLD functions
(I think it was John who wanted them to be mostly wrappers), and in
m-files (the rest).

A good guide is, IMHO, the "call profile" of the algorithm. For
instance, in __qp__.cc (qp), I think most of the work per cycle of the
main loop is done by the calls to `null' and either CHOL or EIG.

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz