Probabilistic analysis of a differential equation for linear programming

DOI10.1016/S0885-064X(03)00032-3MaRDI QIDQ652446zbMATH OpenWikidataFDO

Authors Asa Ben-Hur, Joshua Feinberg, Shmuel Fishman, Hava T. Siegelmann

Publication date 14 December 2011

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0110056

zbMATH Keywords

linear programmingdynamical systemsrandom matrix theoryscalingtheory of analog computation

Mathematics Subject Classification ID

Linear programming (90C05) Random matrices (probabilistic aspects) (60B20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find that the distribution of the convergence rate is a scaling function, namely it is a function of one variable that is a combination of three parameters: the number of variables, the number of constraints and the convergence rate, rather than a function of these parameters separately. We also estimate numerically the distribution of computation times, namely the time required to reach a vicinity of the attracting fixed point, and find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times.

Recommendations

• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• On the probabilistic complexity of finding an approximate solution for linear programming
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• A universal scaling theory for complexity of analog computation
• Random matrix theory for the analysis of the performance of an analog computer: a scaling theory

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3956145 (Why is no real title available?)
• scientific article; zbMATH DE number 3459634 (Why is no real title available?)
• scientific article; zbMATH DE number 1324524 (Why is no real title available?)
• scientific article; zbMATH DE number 735099 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 194534 (Why is no real title available?)
• scientific article; zbMATH DE number 830380 (Why is no real title available?)
• scientific article; zbMATH DE number 1409619 (Why is no real title available?)
• scientific article; zbMATH DE number 3090543 (Why is no real title available?)
• A theory of complexity for continuous time systems
• Analog computation with dynamical systems
• Complexity of linear programming
• Dynamical Systems which Solve Optimization Problems with Linear Constraints
• Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Large rectangular random matrices
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On the average number of steps of the simplex method of linear programming
• Planar diagrams
• Probabilistic Models for Linear Programming
• Probabilistic analysis of an infeasible-interior-point algorithm for linear programming
• The Efficiency of the Simplex Method: A Survey
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming

Cited in

(9)

• A theory of complexity for continuous time systems
• On the convergence time of a natural dynamics for linear programming
• scientific article; zbMATH DE number 4197740 (Why is no real title available?)
• A Survey on Analog Models of Computation
• A universal scaling theory for complexity of analog computation
• Perturbation analysis of linear programming problems with random parameters
• Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
• Analog-symbolic memory that tracks via reconsolidation
• Scaling and universality of the complexity of analog computation

This page was built for publication: Probabilistic analysis of a differential equation for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652446)