Convergence of the Non-Uniform Physarum Dynamics

Abstract

Let $c\in {\mathbb{Z}}_{>0}^m$, $A\in {\mathbb{Z}}^{n\times m}$, and $b\in {\mathbb{Z}}^n$. We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_e = a_e(x,t) \left(|q_e| - x_e\right) \] converges to the optimum solution $x^{\ast }$ of the weighted basis pursuit problem minimize $c^{T}x$ subject to $Af=b$ and $|f|\le x$. Here, $f$ and $x$ are $m$-vectors of real variables, $q$ minimizes the energy ${\sum }_e(c_e/x_e)q_e^2$ subject to the constraints $Aq=b$ and $\mathrm{supp}(q)\subseteq \mathrm{supp}(x)$, and $a_e(x,t)>0$ is the reactivity of edge $e$ to the difference $|q_e|-x_e$ at time $t$ and in state $x$. Previously convergence was only shown for the uniform case $a_e(x,t)=1$ for all $e$, $x$, and $t$. We also show convergence for the dynamics \[ \dot{x}_e = x_e \cdot \left( g_e \left(\frac{|q_e|}{x_e}\right) - 1\right),\] where $g_e$ is an increasing differentiable function with $g_e(1)=1$. Previously convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges.

to appear in Theoretical Computer Science C