Re: GSoC 2015: Optimization Package: Non-linear and constrained least squares lsqcurvefit, lsqlin, lsqnonlin

[Asma Afzal]

Hi Olaf,

Thank-you for the detailed response.

On 2/24/2015 8:42 AM, Olaf Till wrote:
> Hi AsmaA,
>
> On Mon, Feb 23, 2015 at 02:10:29PM -0800, AsmaA wrote:
> > Hi,

...

> Although it is true that we havn't functions called 'lsqcurvefit' or
> 'lsqnonlin' in the optim package, the rest of the paragraph (when was
> it written?) does not adequately describe the situation. The wrapper
> functions 'nonlin_residmin' and 'nonlin_curvefit' already provide
> access to backends for least squares nonlinear constrained
> optimization. The wrappers provide a convenient interface similarly to
> 'lsqnonlin' and 'lsqcurvefit', but are differently named because there
> are some differences (not by chance, but by decision). Additionally,
> they provide some functionality which 'lsqnonlin' and 'lsqcurvefit'
> don't provide.

I was unaware of the existence of these functions and thought the wiki 
mentioned an updated situation as the diff was quite recent.

> > I am studying the Levenberg-Marquardt algorithm from [2].
>
> This seems to be a general introduction to LM. An actual algorithm
> must also, among others, take measures to be numerically stable. It is
> usually best to start from one of the several already existing
> algorithms (I know this is your intention). In the optim package we
> have, among others, an SVD-based algorithm.
>
> > I have taken a look at the levmar.c library [3].
>
> On this web-page no non-linear constraints seem to be mentioned, which
> would make the new algorithm inferior to the existing algorithm with
> respect to this. But it may still be worth having the new one.

[2] just explains the unconstrained case (which I was referring to for 
the basic understanding of how the LM algorithm works), but the 
non-linear constraints are considered in the levmar.c library [3].

--start quote

To deal with linear equation constraints, levmar employs variable 
elimination based on QR factorization, as described in ch. 15 of the 
book Numerical Optimization by Nocedal and Wright. For the 
box-constrained case, levmar implements the algorithm proposed by C. 
Kanzow, N. Yamashita and M. Fukushima, Levenberg-Marquardt methods for 
constrained nonlinear equations with strong local convergence 
properties, Journal of Computational and Applied Mathematics 172, 2004, 
pp. 375-397

--end quote

> >

...

> >
>
> A new, alternative, optimization algorithm can be useful. There might
> be problems better solvable by one algorithm than by the other. An
> example problem for such a case in favour of the new algorithm would
> be good, however.
>
> Such a new, alternative, algorithm should be integrated as a backend
> of 'nonlin_residmin' and 'nonlin_curvefit' (the latter is actually
> only a convenience-wrapper to the former).
>
> 'nonlin_residmin' provides configurable access to functions computing
> the Jacobian, so any new Jacobian-function should be treated
> separately from the new algorithm.

1) Adding a new algorithm to the opt package backend

> There is a somewhat outdated description of the backend interface of
> 'nonlin_residmin' in the optimization package. More can be learned
> from studying an existing backend. It is probably also advisable to
> co-ordinate the integration of a new backend with me.
>
> If anyone wants to exactly mimic the interface of 'lsqnonlin' and
> 'lsqcurvefit' (and personally I'd think this would not be the right
> way ... sorry) this can either be done by writing them as seperate
> wrappers for the existing backends, or by writing them as wrappers to
> 'nonlin_residmin' or 'nonlin_curvefit'. It would probably be wrong to
> write a new algorithm only for them.

2) Mimicking 'lsqnonlin' and 'lsqcurvefit' using same backend


> I'd think a project 'officially' supported by the Octave community
> should not be based on mex-files (use m-code and/or oct-files).

I agree that mex is not an ideal way for core functionality.

> I'm not sure, but it could be worth rewriting an algorithm of a
> C-library in m-code (or as an oct-file) so that Octaves native
> interfaces to e.g. decompostions and matrix operations are used, and
> modifications are more easily possible.

3) Rewriting levmar C library into m-code for Octave? Or is there a C 
library used by the optimization package that would benefit from porting 
into m-code?

What would you suggest as the most suitable contribution as part of GSoC?

I don't have a particular inclination. Whichever helps Octave best.

Regards,
Asma

> > References:
> >
> > [1]
> > http://wiki.octave.org/Summer_of_Code_Project_Ideas#Nonlinear_and_constrained_least_squares
> >
> > [2] http://www.imm.dtu.dk/pubdb/views/edoc_download.php/3215/pdf/imm3215.pdf
> >
> > [3] http://users.ics.forth.gr/~lourakis/levmar/index.html