Probabilistic analysis of the phase space flow for linear programming

Abstract

The phase space flow of a dynamical system leading to the solution of Linear Programming (LP) problems is explored as an example of complexity analysis in an analog computation framework. An ensemble of LP problems with $n$ variables and $m$ constraints ($n>m$), where all elements of the vectors and matrices are normally distributed is studied. The convergence time of a flow to the fixed point representing the optimal solution is computed. The cumulative distribution ${\cal F}^{(n,m)}(Δ)$ of the convergence rate $Δ_{min}$ to this point is calculated analytically, in the asymptotic limit of large $(n,m)$, in the framework of Random Matrix Theory. In this limit ${\cal F}^{(n,m)}(Δ)$ is found to be a scaling function, namely it is a function of one variable that is a combination of $n$, $m$ and $Δ$ rather then a function of these three variables separately. From numerical simulations also the distribution of the computation times is calculated and found to be a scaling function as well.

8 pages, latex, 2 eps figures; final published version