Document Open Access Logo

On the Convergence Time of a Natural Dynamics for Linear Programming

Author Vincenzo Bonifaci

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.17.pdf
  • Filesize: 420 kB
  • 12 pages

Document Identifiers

Author Details

Vincenzo Bonifaci

Cite AsGet BibTex

Vincenzo Bonifaci. On the Convergence Time of a Natural Dynamics for Linear Programming. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.17

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 LP instances. 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.
Keywords
  • linear programming
  • natural algorithm
  • Physarum polycephalum
  • relative entropy
  • Mirror Descent

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Amari. Information Geometry and Its Applications. Springer, 2016. Google Scholar
  2. S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012. Google Scholar
  3. D. A. Bayer and J. C. Lagarias. The nonlinear geometry of linear programming, I. Affine and projective scaling trajectories. Trans. of the American Mathematical Society, 314:499-526, 1989. Google Scholar
  4. L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, and K. Mehlhorn. Physarum can compute shortest paths: Convergence proofs and complexity bounds. In Proc. of the 40th Int. Colloquium on Automata, Languages and Programming, volume 7966 of Lecture Notes in Computer Science, pages 472-483. Springer, 2013. Google Scholar
  5. A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3):167-175, 2003. Google Scholar
  6. B. Bollobás. Modern Graph Theory. Springer, New York, 1998. Google Scholar
  7. V. Bonifaci. Physarum can compute shortest paths: A short proof. Inf. Process. Lett., 113(1-2):4-7, 2013. Google Scholar
  8. V. Bonifaci, K. Mehlhorn, and G. Varma. Physarum can compute shortest paths. In Proc. of the 23rd ACM-SIAM Symposium on Discrete Algorithms, pages 233-240. SIAM, 2012. Google Scholar
  9. B. Chazelle. Natural algorithms and influence systems. Communications of the ACM, 55(12):101-110, 2012. Google Scholar
  10. J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998. Google Scholar
  11. K. Ito, A. Johansson, T. Nakagaki, and A. Tero. Convergence properties for the Physarum solver. arXiv:1101.5249v1, Jan 2011. Google Scholar
  12. A. Johannson and J. Y. Zou. A slime mold solver for linear programming problems. In How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, pages 344-354. Springer, 2012. Google Scholar
  13. N. K. Karmarkar. Riemannian geometry underlying interior-point methods for linear programming. In J. C. Lagarias and M. J. Todd, editors, Mathematical Developments Arising from Linear Programming, volume 114 of Contemporary Mathematics, pages 51-75. American Mathematical Society, 1990. Google Scholar
  14. T. Nakagaki, H. Yamada, and Á. Tóth. Maze-solving by an amoeboid organism. Nature, 407:470, 2000. Google Scholar
  15. S. Navlakha and Z. Bar-Joseph. Algorithms in nature: the convergence of systems biology and computational thinking. Molecular Systems Biology, 7:546, 2011. Google Scholar
  16. A. S. Nemirovski and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley, 1983. Google Scholar
  17. G. Raskutti and S. Mukherjee. The information geometry of mirror descent. IEEE Trans. Information Theory, 61(3):1451-1457, 2015. Google Scholar
  18. D. Straszak and N. K. Vishnoi. Natural algorithms for flow problems. In Proc. of the 27th ACM-SIAM Symposium on Discrete Algorithms, pages 1868-1883. SIAM, 2016. Google Scholar
  19. D. Straszak and N. K. Vishnoi. On a natural dynamics for linear programming. In Proc. of the 2016 ACM Conf. on Innovations in Theoretical Computer Science, page 291. ACM, 2016. Google Scholar
  20. A. Tero, R. Kobayashi, and T. Nakagaki. Physarum solver: A biologically inspired method of road-network navigation. Physica A, 363:115-119, 2006. Google Scholar
  21. A. Tero, R. Kobayashi, and T. Nakagaki. A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology, 244:553-564, 2007. Google Scholar
  22. A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki, R. Kobayashi, and T. Nakagaki. Rules for biologically inspired adaptive network design. Science, 327:439-442, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact