[SciPy-dev] Abstract vectors in optimization

[Ben FrantzDale]

On Tue, Jan 6, 2009 at 10:56 PM, Robert Kern <robert.kern at gmail.com> wrote:

> 2009/1/6 Ben FrantzDale <benfrantzdale at gmail.com>:
> > David, Robert, et al.
> >
> > I think you understand what I am talking about. This is just about
> > optimization (although in general I would argue that functions should
> take
> > as general an interface as possible for the same reasons).
>
> I'm not sure I would push it that far. Premature generalization can be
> just as bad as premature optimization. I find that a use case-based
> approach is a better principle. Write the code for the problem in
> front of you. Generalize when you have a use case for doing so.
>

I completely agree; I was just speculating :-)


> Now, we do have a handful of use cases here, but I think we should
> have some care before modifying the functions in place. Generalization
> could cost us performance in the typical case.
>
> > Attached is all the code I changed to make fmin_cg work with a
> > SimpleHilbertVector class.
>
> Hmm, can you show us a .diff of the changes that you made? I'd like to
> see more clearly exactly what you changed.
>

See attached.
Run this:
$ patch Hilbert_cg_example_original.py Hilbert_cg_example.diff -o
Hilbert_cg_example.py
to get Hilbert_example.py. (I can't fit all the files in one email to this
list.)

I cleaned it up a bit and included all the functions I changed, all in one
file to make a diff make sense. The diff lines are almost all just
numpy.dot(u,v) -> inner_product(u,v) and vecnorm(v,norm) -> v.norm(norm).


> > If people are receptive to this approach, I have a few next questions:
> > 1. What is the right interface to provide? Is the interface I described
> the
> > right (Pythonic) way to do it, or is there a better interface? (If it
> were
> > Templated C++, I'd do it with overloaded free functions, but I think it
> > needs to/should be done with class methods.)
>
> I still don't think this interface supports the manifold-optimization
> use case. The inner product and norm implementations need more
> information than just the vectors.
>

Good point. I've been focused on optimizing within a vector space not on a
manifold. For nonlinear CG, I suppose the gradient needs to be a vector in
the tangent space, which itself must be a Hilbert space, but the state
"vector" can be in an affine space or on a manifold. What is the
mathematically-correct operation for moving such a "vector" on its manifold?
That operation would take the place of the line
    xk += alpha_k * pk
where pk is a vector in the tangent space.

--Ben

PS
If you have references for optimizing on a manifold, I would be very curious
to read more about it. Wikipedia suggests I should look into Development
(differential geometry), Geodesics, Affine connection, and Parallel
transport, and Retraction.



> > 2. Which functions should be changed? (fmin_cg, clearly; what else? The
> full
> > list in optimize.py is fmin, fmin_powell, fmin_bfgs, fmin_ncg, fmin_cg,
> and
> > fminbound.)
> > 3. How would one deal with numpy arrays? Is it best to wrap them in the
> > interface (as shown in the attached code) or is it better to add methods
> to
> > them?
>
> We're not going to add methods to them.
>
> > If the right way is to wrap them, should all the optimization
> > functions have that as a first step -- check for numpy arrays and wrap as
> > needed?
>
> Possibly, but that could have a significant performance hit that will
> need to be tested.
>
> > Given an appropriate interface, the changes to optimize.py are
> essentially
> > search-and-replace and I would be happy to do it.
> >
> > Does Travis Oliphant (whose name is on optimize.py) read this list?
>
> Yeah. He's pretty busy this week, though.
>
> --
> Robert Kern
>
> "I have come to believe that the whole world is an enigma, a harmless
> enigma that is made terrible by our own mad attempt to interpret it as
> though it had an underlying truth."
>  -- Umberto Eco
> _______________________________________________
> Scipy-dev mailing list
> Scipy-dev at scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090108/517977ff/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Hilbert_cg_example_original.py
Type: text/x-python
Size: 11799 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090108/517977ff/attachment.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Hilbert_cg_example.diff
Type: application/octet-stream
Size: 3152 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090108/517977ff/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testit.py
Type: text/x-python
Size: 1371 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090108/517977ff/attachment-0001.py>