Exploiting Symmetry
A recent article by Coleman on exploiting structure for
portfolio optimization is an eyeopener for realtime
optimization. The article talks about decomposing a dense matrix into
a diagonal matrix and a linear term. The diagonal matrix can be solved
in linear time 
as opposed to polynomial time
for the full dense matrix.
Symmetry can also be used in speeding up particle dynamics. Routines like
molecular and celestial dynamics propagate in time
by solving Newton’s equations of motion. If every body interacts with
every other body in the system, the interaction graph of N bodies will
be a complete graph 
, ie with 
edges. Simple implementations will store the interactions in the
graph’s square adjacency matrix of size N, with 
entries. The use of Newton’s third law
allows us to populate just half the matrix. This results in a huge increase in speed (either for simulation or control.) I’ve created a contour plot of a symmetric random matrix with zeros along the diagonal to demonstrate the fact.
Further reductions can be made in mechanical systems with symmetry. If the set of canonical transformations on the phase space is a symmetry group, leaving the Hamiltonian invariant, then the equations of motion can be brought down to a lower dimension space of orbits of the symmetry group. Why re-calculate something that isn’t going to change?
Further, if the equations of motion are invariant under a set of transformations (either in space or time), then conservation laws are realized. This is Noether’s Theorem.
In conclusion, though disguised most times, structure and symmetry show up in problems all the time. This post was inspired by rod’s post on the fenews article. Thanks!
November 20th, 2006 at 5:52 am
I am glad you appreciated my post on numerical methods for fast optimization. Thanks for linking to my blog.
Congrats for an interesting blog, I will probably be visiting often.
November 20th, 2006 at 11:13 pm
You’re welcome rod. You have an amazing blog - you post stuff I haven’t read about or seen elsewhere on the web. Good job!
December 10th, 2006 at 10:36 pm
[...] Let’s say you have an optimization problem that makes use of a cost function that needs to be computed over a set of discrete variables. For the sake of argument, assume that there is some sort of sub-structure or symmetry. How would you speed up the computation? [...]
December 20th, 2006 at 8:56 pm
Hi Ganesh!
Last time I visited your blog was about a month ago, and I made a big mistake: I forgot to add your blog to my feed reader. As a result, I have been missing a lot of exciting posts.
Last time I commented, I commented your blog as “interesting” and that wasn’t totally accurate; the truth is: your blog is fantastic!!
I have found stuff here that is really, really, really interesting… and that it’s also very, very, very hard to find elsewhere.
I have now added your blog to the reader. I will probably use the upcoming hollidays to catch up on the posts I’ve missed over the past few weeks. Once again, congratulations for the great work! Really cool blog that you have here… and these plug-ins as pretty sweet as well, I should get some stuff like this so I could embed math expressions in my blog’s posts.
I will probably be visiting quite often… and I will probably be linking often to your posts. I am very glad I remembered to check your blog again, it was the finding of the month!
keep up the good work!
rod.
December 20th, 2006 at 9:04 pm
A bit off topic now…
I am now doing research in optimal control theory, robotics and stuff.
One of the problems I am interested in is to generate feasible trajectories for the robots to follow. This is quite easy to state, but quite hard to solve, since all robots have nonlinear dynamics, and hence I get some really nasty ODEs and PDEs to solve.
Dynamic programming is quite a powerful tool in control theory, as it allows one to compute the optimal control (at discrete time instants) that will steer a given robot (for instance) from a given region in state space to another “target” region in state space (engineers say “state space”, mathematicians say “phase space” sometimes).
Dynamic programming is also used in the famous Viterbi algorithm (which is instrumental in digital communications), a maximum-likelihood decoder for digital communications. In fact, I’m almost 100% sure that most mobile phones run the Viterbi algorithm, so dynamic programming is pretty much everywhere!
December 21st, 2006 at 1:02 pm
Hi Rod,
Thank you for your kind words.
I’ve done a fair bit of robotic motion planning myself, though this was motivated by general trajectories in an arbitrary manifold. My project was to generate a trajectory for a small molecule (which is just a kinematic chain) to “dock” into an active site. The control law for the trajectory has to be thermodynamically and kinetically feasible. I’ll make a detailed post about this project soon.
Just curious, is the PDE that you get the Euler-Lagrange equation? I did briefly look into deriving the EL equation from the Lagrangian, but numerically solving the EL equation for eight or nine dimensions was pushing the limits, computationally.
The approach I finally took was the method of probabilistic roadmaps, by Kavraki et. al. This builds a graph in the free space of the configuration space and does planning over the graph. This in some ways is a method to discretize the configuration space.
Last week was the first time I came across dynamic programming, so thanks for those pointers. I have quite a bit of reading to do to familiarize myself with the field!
December 21st, 2006 at 1:08 pm
Another motivation behind this post is my interest in studying the properties of the graph that you build in the free configuration space. If there’s some kind of symmetry in some dimension, that’ll simply your task considerably.
I was thinking if I could extract something from the spectral properties of the graph, I could somehow deform the C-space into something equivalent that shows symmetry. Think of diagonalizing the inertia matrix along the principle axes - the mathematics becomes so much easier.
So far, I’ve only been able to come up with theoretical models that exhibit symmetrical properties. All of my “real world” tasks are quite unsymmetrical. Nature is quite a complex beast!
December 29th, 2006 at 9:58 am
Hi Ganesh!
I am fairly new to robotics research. A couple of years ago I spent the summer writing navigation software for a hovercraft-like robot and that was it (I didn’t work on the trajectory generation nor control, just the C++ code). I started in robotics a couple of months ago, and I am enjoying it. Yes, the nasty PDEs I have encountered are indeed the Euler-Lagrange equations and some other ODEs which arise in optimal control when one uses Pontryagin’s maximum principle.
Trajectory generation for mollecular dynamics sounds very, very cool. I have been interested in mollecular dynamics for a long time, and I was somewhat surprised to acknowledge that there’s still an enormous amount of work to be done in this field. It’s always the same thing: 99% of the work is to try to accelerate the computations so that we don’t have to wait another million years for the computer to give us some answers.
I am glad I found your blog. A lot of interesting stuff around here and which I can’t really find elsewhere in the blogosphere.
have fun
rod.
March 4th, 2007 at 4:47 pm
Hey!
It’s me again…
I am now studying some problems in Calculus of Variations and trying to formulate them as Optimal Control Problems. I recalled reading here that you had used the Euler-Lagrange equations for mollecular dynamics, and I was curious to know how the problem is formulated and how one can solve it. Of course, I am always looking for ways to increase efficiency by exploiting the problem structure. Overall, I love doing this.
Do you have any papers or reports on using E-L equations for mollecular dynamics that you could reccomend to me?
Thanks in advance! Any hints would be very warmly welcome!
cheers mate!
rod.
March 8th, 2007 at 1:25 am
Hey rod,
Sorry for the delay in getting back to you. I’ve been really busy lately.
The central problem in molecular dynamics is that of sampling, ie get as many as thermodynamically relevant samples of configuration space as possible. This is eventually to build a good approximation to the partition function. I can’t think of a use of optimal control here…
On the other hand, molecular docking is the motion of a small molecule of an active site of an enzyme. Optimal control hasn’t been used here yet. The closest I can think of is Latombe’s, Apayadin’s and Singh’s Probabilistic and Stochastic Roadmaps. What we need is a formulation of the dynamics over these probabilistic spaces in the variational sense.
Here are the relevant links:
A Motion Planning Approach to Flexible Ligand Binding and Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion.
March 10th, 2007 at 5:16 pm
Thanks a ton, Ganesh!
I know that my idea is highly speculative: in many problems of calculus problems, there’s no chance of having optimal control into it… but in some, there’s a slight chance. Well, I will read the papers and think of possibilities!
Thanks once again!
March 17th, 2007 at 6:22 pm
I’ve written a comprehensive review of what I’ve done with computational biology and robotics here. Hope it’s useful!
Cheers.