[SciPy-dev] Abstract vectors in optimization

Ben FrantzDale benfrantzdale@gmail....
Fri Jan 9 08:34:08 CST 2009


On Thu, Jan 8, 2009 at 3:39 PM, Robert Kern <robert.kern@gmail.com> wrote:

> On Thu, Jan 8, 2009 at 09:59, Ben FrantzDale <benfrantzdale@gmail.com>
> wrote:
> > On Tue, Jan 6, 2009 at 10:56 PM, Robert Kern <robert.kern@gmail.com>
> wrote:
>
> >> 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.
>
> You basically need to define a move(x0, dx, alpha) function.
>

I think if you are moving a finite distance you need transport your gradient
vector as well, otherwise you'll wind up (at least in CG) taking the inner
product of a vector from the tangent space of x_i with a vector from the
tangent space of x_i+1, which doesn't make much sense.

With that in mind, the code could easily be generalized by adding the
following:

   def move(self, dx, alpha, *tangentVectorsToTransport): # Moves self,
transport any vectors passed in.

This interface be provided by an abstract ManifoldPoint class and
HilbertVector could inherit it and provide move as self += dx*alpha with the
identity operation for transport. (Since Python is dynamically typed, is it
recommended to provide an "abstract" base class that just raises exceptions.
On the one hand it would be helpful to show what interface someone needs to
implement; on the other hand, creating a ManifoldPoint class with methods
that just raise exceptions essentially adds nothing. What's the Python Way?)

I'll read up on this and post an updated version of the code.

--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.
>
> http://www-math.mit.edu/~lippert/sgmin.html<http://www-math.mit.edu/%7Elippert/sgmin.html>
>
> Also look at the code I posted for an example of a particular manifold.
>
> --
> 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@scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.scipy.org/pipermail/scipy-dev/attachments/20090109/8c4f3a08/attachment.html 


More information about the Scipy-dev mailing list