On the convergence time of a natural dynamics for linear programming

DOI10.4230/LIPICS.ISAAC.2017.17zbMATH Open1457.90092arXiv1611.06729OpenAlexW2963201244MaRDI QIDQ5136233FDOQ5136233

Authors: Vincenzo Bonifaci 

Publication date: 25 November 2020

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.

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

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

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)

Cites Work

• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Evolutionary Games and Population Dynamics
• Rhythmic contraction and its fluctuations in an amoeboid organism of the \textit{physarum} plasmodium
• Title not available (Why is that?)
• A mathematical model for adaptive transport network in path finding by true slime mold
• Rules for biologically inspired adaptive network design
• The multiplicative weights update method: a meta-algorithm and applications
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• Physarum can compute shortest paths: a short proof
• Natural Algorithms for Flow Problems
• Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds
• Title not available (Why is that?)
• Information geometry and its applications
• The Information Geometry of Mirror Descent
• A Slime Mold Solver for Linear Programming Problems

Cited In (2)

• On the convergence time of a natural dynamics for linear programming
• 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)