  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.
