Convergence of the Non-Uniform Directed Physarum Model
share
The directed Physarum dynamics is known to solve positive linear programs: minimize c^T x subject to Ax = b and x > 0 for a positive cost vector c. The directed Physarum dynamics evolves a positive vector x according to the dynamics ẋ = q(x) - x. Here q(x) is the solution to Af = b that minimizes the "energy" ∑_i c_i f_i^2/x_i. In this paper, we study the non-uniform directed dynamics ẋ = 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.
READ FULL TEXT