On a Natural Dynamics for Linear Programming

On the "Off the convex path" blog, the recent entry entitled "Nature, Dynamical Systems and Optimization" features Nisheeth Vishnoi's writing and his work on the connection between a dynamical system and a linear programing problem:

The main contribution of this paper is to provide answers to all of these questions: We show that Physarum dynamics can be seen as a steepest-descent type algorithm, however, not in Euclidean space, rather in a space endowed with a Riemannian metric obtained from an entropy-like function

I wonder how this way of looking at nonnegative linear programs can be used to speed up reconstruction solvers in compressive sensing....all this while using molds. This nature/physics based example is eerily similar to the example borrowed from spin glass physics used to design the magic matrices in Compressive Sensing.  Here is the attendant paper: On a Natural Dynamics for Linear Programming by Damian Straszak, Nisheeth K. Vishnoi

In this paper we study dynamics inspired by Physarum polycephalum (a slime mold) for solving linear programs [NTY00, IJNT11, JZ12]. These dynamics are arrived at by a local and mechanistic interpretation of the inner workings of the slime mold and a global optimization perspective has been lacking even in the simplest of instances. Our first result is an interpretation of the dynamics as an optimization process. We show that Physarum dynamics can be seen as a steepest-descent type algorithm on a certain Riemannian manifold. Moreover, we prove that the trajectories of Physarum are in fact paths of optimizers to a parametrized family of convex programs, in which the objective is a linear cost function regularized by an entropy barrier. Subsequently, we rigorously establish several important properties of solution curves of Physarum. We prove global existence of such solutions and show that they have limits, being optimal solutions of the underlying LP. Finally, we show that the discretization of the Physarum dynamics is efficient for a class of linear programs, which include unimodular constraint matrices. Thus, together, our results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.

 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.