Probabilistic Analysis of a Differential Equation for Linear Programming

Title: Probabilistic Analysis of a Differential Equation for Linear Programming

Research Question: How does the convergence rate of a differential equation system used for linear programming change when the problem size increases?

Methodology: The researchers used a probabilistic model where the inputs are independently and identically distributed Gaussian variables. They applied the framework of Random Matrix Theory to derive a simple expression for the distribution of the convergence rate in the asymptotic limit of large problem size.

Results: They found that the distribution of the convergence rate is a scaling function of a single variable, which combines the convergence rate with the problem size. They also estimated numerically the distribution of the computation time to an approximate solution, finding it to be another scaling function. Using the problem size dependence of the distribution functions, they derived high probability bounds on the convergence rates and on the computation times to the approximate solution.

Implications: This study provides insights into the behavior of differential equation systems used for linear programming, particularly regarding their convergence rates and computation times. The results suggest that these systems exhibit scaling behavior, which can be used to predict and optimize their performance. This work contributes to the field of analog computation and has implications for the design and analysis of analog VLSI devices and neural network systems.

Link to Article: https://arxiv.org/abs/0110056v2 Authors: arXiv ID: 0110056v2