There is growing evidence that several fundamental processes in nature are inherently computational and are best viewed from the standpoint of computation. Consider the case of Physarum polycephalum (slime mold), a single celled organism which has been the source of much excitement among biologists and computer scientists due to its ability to solve complex optimization problems. This started with an experiment (Nakagaki et al. in Nature 2000) that showed the slime mold could solve the shortest path problem on a maze. Subsequently, the time evolution of Physarum was captured by mathematical biologists using the language of dynamical systems giving rise to a broad class of dynamics for basic computational problems such as shortest paths, transshipment problems, and linear programs (Tero et al. in 2007, Ito et al. in 2011, Johannson and Zou in 2012. The Physarum dynamics are highly nonlinear and decentralized and, thus, there is no a priori reason for them to converge anywhere, let alone to solutions of problems, such as those listed above, where a global optima is sought. However, experiments and simulations suggest that the solution not only converges, it converges quickly. Two sets of questions arise naturally from a computational viewpoint: (1) While the dynamical system gives a mechanistic insight into the workings of a Physarum, it fails to explain what is going on globally. Can we explain Physarum dynamics from an optimization perspective? (2) Can we rigorously explain what experiments, simulations and partial results about the Physarum dynamics suggest, namely the (a) existence of a solution, (b) convergence to an optimal solution and (c) time to convergence of the (continuous and discretized) dynamics? We study these questions for the Physarum dynamics for linear programming proposed by (Johannson and Zou in 2012) which generalizes earlier models for shortest path and the transshipment problem. For question (1) there are no known answers even in the simplest setting of shortest path: on the one hand the Physarum dynamics resemble the gra-dient descent method; however, one can show that it is not. On the other hand, the dynamics are reminiscent of interior point methods; however, what makes the Physarum dynamics remarkable is that one can start from outside the feasible region of the linear program and yet converge to the optimal point. For question (2), the situation is slightly better. For various special cases such as shortest path (Bonifaci et al. in 2012, Becchetti et al. in 2013 and the transshipment problem (Ito et al. in 2011, a prior work of the current authors in SODA 2016) (a)-(c) have been answered. However, these results heavily rely on the special structure of the problem. For LPs, the prior results prove convergence assuming that (i) the solution exists (ii) the feasible region of the LP is bounded and (iii) the optimizer is unique. As we argue later, justifying or removing these ends up being quite hard. Current results do not bound the convergence time. We 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. As a consequence, we show that Physarum dynamics for linear programming are obtained by balancing two forces in this Riemannian manifold: the need to reduce cost and the need to be feasible. Moreover, we show that the continuous 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 establish the global existence of solutions of Physarum dynamics and show that they have limits, being optimal solutions of the underlying LP. Finally, we present a time-bound on a discretization of the dynamics to yield an algorithm that is provably efficient for a class of linear programs, which include unimodular constraint matrices. Our proofs synthesize concepts and tools from several distinct areas such as Riemannian manifolds, convex optimization and dynamical systems and should be of independent interest. The paper can be found here: http://arxiv.org/abs/1511.07020. 291
Most relevant to the current paper is the work of Straszak and Vishnoi REF , who initiated the rigorous study of the Physarum dynamics for LP problems of the form (1).