Probabilistic analysis of a differential equation for linear programming

DOI10.1016/S0885-064X(03)00032-3zbMATH Open1229.90078arXivcs/0110056WikidataQ58455278 ScholiaQ58455278MaRDI QIDQ652446FDOQ652446

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• On the convergence time of a natural dynamics for linear programming
• 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
• A theory of complexity for continuous time systems

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)