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

[Olaf Till]

On Wed, Feb 25, 2015 at 09:12:59PM +0100, Olaf Till wrote:
> On Wed, Feb 25, 2015 at 07:56:15PM +0000, Nir Krakauer wrote:
> > <snip>
> > In terms of algorithms, it looks like the Optimization package has
> >  __lm_svd__, which offers a Levenberg-Marquardt algorithm for least squares
> > (with arbitrary constraints allowed, if I understand it correctly?). The
> > other algorithm Matlab offers in lsqcurvefit and  lsqnonlin is a
> > trust-region one[1] which supposedly can be more efficient for
> > high-dimensional problems -- is anything like that implemented in Octave?
> > 
> > [1] 
> > *http://www.mathworks.com/help/optim/ug/least-squares-model-fitting-algorithms.html#broz0i4
> > <http://www.mathworks.com/help/optim/ug/least-squares-model-fitting-algorithms.html#broz0i4>*
> 
> We have no trust region algorithm. But to be answerable for trust
> region algorithms I'd need to do some studying first.

After a quick glance at a description of trust region algorithms it
seems to me that a LM algorithm actually could also be called a trust
region algorithm, since it follows the same concept. Since the LM
algorithm reputedly works quite well, I wouldn't expect a large
improvement by using an explicitely so called trust region algorithm.

After an similarly short glance at:

Coleman, T.F. and Li, Y. 1994, Mathematical Programming 67, 189-224,

referenced by Matlab with its title slightly wrong ("large scale"
seemingly introduced by Matlab) and the reference contained therein:

Coleman, T.F. and Li, Y., internal research paper TR92-1315, 1992,

the notion of suitablility for large scale problems seems to be based
on numerical experiments with a "reflective" Newton method, seeing no
substantial increase in the number of iterations with an increase of
dimension (up to 2744). But I've seen no comparison with different
methods in these papers, so I'd have no reason to assume the method is
better than our LM with respect to this.

For high dimensionality, there is a speed problem due to the
decomposition. But this problem is not specific to either LM or "trust
region" algorithm. I'd guess it's possible to improve speed for high
dimensionality in __lm_svd__ (currently no alternative to svd() is
used there, and svd (rand (3000, 2744)) needs 7 min for me).

BTW the second reference states the respective algorithm was written
in Matlab.

The "trust region" algorithm is now Matlabs default, I'd guess because
it supports bounds, while their LM algorithm doesn't. BTW our
__lm_svd__ supports arbitrary constraints.

I'd conclude it's probably not worth providing Matlabs "trust region"
algorithm in Octave, but maybe worth to provide alternatives to svd()
for large scale in our existing algorithm (but the latter I'd probably
try myself, it isn't worth a project).

Olaf

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

signature.asc
Description: Digital signature