hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC
Abstract:
Physarum Polycephalum is a Slime mold that can solve the shortest path
problem. A mathematical model based on the Physarum's behavior, known as the
Physarum Directed Dynamics, can solve positive linear programs. In this paper,
we will propose a Physarum based dynamic based on the previous work and
introduce a new way to solve positive Semi-Definite Programming (SDP) problems,
which are more general than positive linear programs. Empirical results suggest
that this extension of the dynamic can solve the positive SDP showing that the
nature-inspired algorithm can solve one of the hardest problems in the
polynomial domain. In this work, we will formulate an accurate algorithm to
solve positive and some non-negative SDPs and formally prove some key
characteristics of this solver thus inspiring future work to try and refine
this method.
