Convergence of the Non-Uniform Directed Physarum Model

Abstract

The directed Physarum dynamics is known to solve positive linear programs: minimize $c^{T}x$ subject to $Ax=b$ and $x\ge 0$ for a positive cost vector $c$. The directed Physarum dynamics evolves a positive vector $x$ according to the dynamics $\dot{x}=q(x)-x$. Here $q(x)$ is the solution to $Af=b$ that minimizes the "energy" ${\sum }_i{c}_i{f}_i^2/x_i$. In this paper, we study the non-uniform directed dynamics $\dot{x}=D(q(x)-x)$, where $D$ is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with $D$ being the identity matrix), as it allows each component of $x$ to react with different speed to the differences between $q(x)$ and $x$. Our contribution is to show that the non-uniform directed dynamics solves positive linear programs.

References in corpus (7)

• Physarum Can Compute Shortest Paths
• Numerical Solution of Monge-Kantorovich Equations via a dynamic formulation
• Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
• Convergence Properties for the Physarum Solver
• IRLS and Slime Mold: Equivalence and Convergence
• Two Results on Slime Mold Computations
• Physarum Dynamics and Optimal Transport for Basis Pursuit

Cited by in corpus (1)

• Community Detection in networks by Dynamical Optimal Transport Formulation