Natural Dynamics in Linear Programming and Physarum Computations
Explore the intriguing connection between linear programming dynamics and Physarum computations, shedding light on optimization viewpoints, solution existence, and algorithmic convergence.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On a Natural Dynamics for Linear Programming Damian Straszak, EPFL Joint work with Nisheeth K. Vishnoi, EPFL
Linear Programming Fundamental problem in computer science ???. ? ? ?.?. ? ?? ?? ?? Many applications ? ?? Algorithms: Simplex - Dantzig 47 Ellipsoid Method - Khachiyan 79 Interior Point Methods Affine scaling - Dikin 67 Projective scaling - Karmarkar 84 ... ?? ? ? More efficient methods?
Slime Mold LP-Solver? Physarum polycephalum Physarum can compute shortest paths. Nakagaki- Yamada-Toth 00 Mathematical model evolving graph. Tero- Kobayashi-Nakagaki 07 Convergence to shortest path, Bonifaci et al. 12 Physarum Dynamics for LP - Johansson, Zou 12 If ? - incidence matrix of ? = (?,?) ? ? - electrical flow in ?! ?(?) ???. ? ? ?.?. ? ? = ??? , ,??? , ? ? > ? ?? = ? ? ? ?? ? ?? = ? ? ?(?) ? ? ?? ??? ?? ? ? ? ?(?) ??(?) ?? , ,??(?) ? ???? ??
Questions around Physarum Dynamics ?? ? ?? = ?? ??? ?? ?(?) Convergence ? ? ? Optimization viewpoint Existence of solution ? ?: ?, >? Discretization, algorithms
Our Results 1) Convergence. For every initial condition ? ? > ? there exists an optimal solution ? such that ? ? ? ? ??, for some ? > ? depending on ?,? and ?(?). 2) Optimization viewpoint. The update is a gradient descent on a Riemannian manifold. Physarum is a continuous IPM with entropy barrier. 3) Existence of solution. For every initial condition ? ? > ? there exists a unique global solution ?: ?, >? ?. 4) Algorithms. The natural discretization of Physarum converges.
Existence of Solution ?? ? ?? ? = ? ? ? ? , ? ? >? ?. Can extend to ?: ?, >? ?? Easy - ?: ?,? >? Thm. Let [?,?) be the maximal interval of existence ? = LP is feasible ?(?) ?(?) ?? = ? ?? = ? infeasible feasible
Optimization Viewpoint ???. ?? ?.?. ?? = ? ? ? ?? (?) ?? = ??????? ?? ?(?) Gradient descent? MWU? Newton method? ... Gradient Descent Minimize ?: ? Current point ? ? ? ? + ? ? ? + ? ?? ? Optimal direction ? minimizes ? ?? ? ? = ? ???(?)
Riemannian Descent Physarum walks on a Riemannian manifold! ? = ?:?? = ?,? > ? with the Riemannian metric ? ? ?,??:= ? ? ?? ? ?? = ??????? ?? ? Natural gradient in machine learning - Amari 98 ? ?- lucky guess? ???(?| ? := ? ? ? ? ?? ? (? ?) ? ? ??????? ???(?| ? + ? ? ??? ? ? = ? ? ?? Example ?= ?,? ?} ??= {?: ?? ??= ?: ??= ?,? ? ? ? ? ?
IPM with Entropy Barrier Def. For a starting point ? ? = ?:?? = ?,? > ? and a parameter ? > ? define ? ? := ?????? {? ??+ ???? ? ???(?| ? := ?????? ?.?. ?? = ?,? ? ??+ ?? ?? Fact. If ? then ??? ??? Thm. ? ? is a solution to the dynamics!
Conclusion Physarum dynamics can solve linear programming Nature inspires real algorithms Physarum is an Interior Point Method Similarity to Affine Scaling Entropy barrier Physarum dynamics is very fast in practice Can we prove it? Thank You!
