On the convergence time of a natural dynamics for linear programming

DOI10.4230/LIPICS.ISAAC.2017.17MaRDI QIDQ5136233zbMATH OpenOpenAlexFDO

Authors Vincenzo Bonifaci

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1611.06729

zbMATH Keywords

linear programmingrelative entropymirror descentPhysarum polycephalumnatural algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Animal behavior (92D50) Asymptotic properties of solutions to ordinary differential equations (34D05) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Abstract: We consider a system of nonlinear ordinary differential equations for the solution of linear programming (LP) problems that was first proposed in the mathematical biology literature as a model for the foraging behavior of acellular slime mold Physarum polycephalum, and more recently considered as a method to solve LPs. We study the convergence time of the continuous Physarum dynamics in the context of the linear programming problem, and derive a new time bound to approximate optimality that depends on the relative entropy between projected versions of the optimal point and of the initial point. The bound scales logarithmically with the LP cost coefficients and linearly with the inverse of the relative accuracy, establishing the efficiency of the dynamics for arbitrary LP instances with positive costs.

Recommendations

• On the convergence time of a natural dynamics for linear programming
• Convergence of the non-uniform directed physarum model
• Convergence of the non-uniform physarum dynamics
• Physarum can compute shortest paths: convergence proofs and complexity bounds
• Two results on slime mold computations

Cites work

• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 4197739 (Why is no real title available?)
• A Slime Mold Solver for Linear Programming Problems
• A mathematical model for adaptive transport network in path finding by true slime mold
• Evolutionary Games and Population Dynamics
• Information geometry and its applications
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Natural algorithms for flow problems
• Physarum can compute shortest paths: a short proof
• Physarum can compute shortest paths: convergence proofs and complexity bounds
• Rhythmic contraction and its fluctuations in an amoeboid organism of the \textit{physarum} plasmodium
• Rules for biologically inspired adaptive network design
• The Information Geometry of Mirror Descent
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The multiplicative weights update method: a meta-algorithm and applications
• \textit{Physarum} can compute shortest paths

Cited in

(3)

• On the convergence time of a natural dynamics for linear programming
• Convergence of the non-uniform physarum dynamics
• A Laplacian approach to \(\ell_1\)-norm minimization

This page was built for publication: On the convergence time of a natural dynamics for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136233)