Convergence of the Non-Uniform Physarum Dynamics
share
Let c ∈Z^m_> 0, A ∈Z^n× m, and b ∈Z^n. We show under fairly general conditions that the non-uniform Physarum dynamics ẋ_e = a_e(x,t) (|q_e| - x_e) converges to the optimum solution x^* of the weighted basis pursuit problem minimize c^T x subject to A f = b and |f| < x. Here, f and x are m-vectors of real variables, q minimizes the energy ∑_e (c_e/x_e) q_e^2 subject to the constraints A q = b and supp(q) ⊆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 ẋ_e = x_e ·( g_e (|q_e|/x_e) - 1), 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.
READ FULL TEXT