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

[Olaf Till]

On Tue, Feb 24, 2015 at 10:03:15PM +0000, Asma Afzal wrote:
> <snip>
> [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

Variable elimination should not be applicable if general non-linear
constraints are also present (one doesn't even know which variables
are referenced by the user function for general constraints). BTW if
variable elimination is applied (if applicable), it should be done
already in the frontend (the function providing the user interface),
so that it is available for all backend algorithms; it should be done
in the same way in the frontends for scalar optimization, not only in
the curve-fitting frontends. OTOH I'd think that the available
projection algorithms can trace linear equality constraints quite
efficiently, limiting the usefulness of variable elimination.

And box constraints are linear, or is something different meant here?

So no non-linear constraints ... (?)

> <snip>
> 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?

I meant the former. But as I said, I'm not sure.

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

I'm not sure at present.

- For my (current) opinion on providing 'lsqnonlin' et al. see my
  answer to Nir.

- Having a further algorithm for residual minimization (i.e. curve
  fitting) would be good, but actually I'd prefer an algorithm
  featuring also non-linear constraints, preferably an algorithm which
  honours the constraints only in the result (since the current
  algorithm honours them throughout optimization, which might not
  always be the best). (I havn't searched for such an algorithm as
  yet.) The potential advantage of the levmar.c algorithm is probably
  very limited.

Olaf

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

signature.asc
Description: Digital signature