Convergence of the non-uniform Physarum dynamics

The Physarum computing model is an analog computing model motivated by the network dynamics of the slime mold Physarum Polycephalum. In previous works, it was shown that it can solve a class of linear programs. We extend these results to a more general dynamics motivated by situations where the slime mold operates in a non-uniform environment. Let c is an element of Z(>0)(m) , A is an element of Z (nxm), and b is an element of Z(n). We show under fairly general conditions that the non-uniform Physarum dynamics (x) over dot(e) = a(e)(x,t) (vertical bar q(e)vertical bar - x(e)) converges to the optimum solution x* of the weighted basis pursuit problem minimize c(T)x subject to Af = b and vertical bar f vertical bar <= x. Here, f and x are m-dimensional vectors of real variables, q minimizes the energy Sigma(e) (c(e)/x(e))q(e)(2) subject to the constraints Aq = b and supp(q) subset of supp(x), and a(e) (x, t) > 0 is the reactivity of edge e to the difference vertical bar q(e)vertical bar - 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 (x) over dot(e) = x(e) (g(e) (vertical bar q(e)vertical bar/x(e))-1), where each g e is an increasing differentiable function with g(e) (1) =1 (satisfying some mild conditions). 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. (C) 2020 Elsevier B.V. All rights reserved.