# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Convergence of the Non-Uniform Physarum Dynamics

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1901.07231.pdf

(Preprint), 381KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Karrenbauer, A., Kolev, P., & Mehlhorn, K. (2019). Convergence of the Non-Uniform Physarum Dynamics. Retrieved from http://arxiv.org/abs/1901.07231.

Cite as: https://hdl.handle.net/21.11116/0000-0002-F39F-9

##### Abstract

Let $c \in \mathbb{Z}^m_{> 0}$, $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^*$ of the weighted basis pursuit problem minimize

$c^T x$ subject to $A f = 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 $A q = 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.

\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^*$ of the weighted basis pursuit problem minimize

$c^T x$ subject to $A f = 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 $A q = 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.