Probabilistic analysis of condition numbers for linear programming

DOI10.1023/A:1015460004163MaRDI QIDQ700762zbMATH OpenOpenAlexWikidataFDO

Authors Dennis Cheung, Felipe Cucker

Publication date 8 October 2002

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1015460004163

zbMATH Keywords

linear programmingcondition numbersprobabilistic analysis of algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Sensitivity, stability, parametric optimization (90C31) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the expected condition number of linear programming problems
• Solving linear programs with finite precision. I: Condition numbers and random programs
• Smoothed analysis of condition numbers and complexity implications for linear programming
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• A new condition number for linear programming

Cites work

• scientific article; zbMATH DE number 193944 (Why is no real title available?)
• A new condition number for linear programming
• A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
• A primal-dual interior point method whose running time depends only on the constraint matrix
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• Condition numbers for polyhedra with real number data
• Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Linear programming, complexity theory and elementary functional analysis
• On the complexity of linear programming under finite precision arithmetic
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• Some perturbation theory for linear programming
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming

Cited in

(17)

• Smoothed analysis of condition numbers and complexity implications for linear programming
• scientific article; zbMATH DE number 4197740 (Why is no real title available?)
• Probabilistic analysis of the Grassmann condition number
• scientific article; zbMATH DE number 2109417 (Why is no real title available?)
• Robust smoothed analysis of a condition number for linear programming
• The expected number of extreme points of a random linear program
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• Metric regularity of semi-infinite constraint systems
• Coverage processes on spheres and condition numbers for linear programming
• High probability analysis of the condition number of sparse polynomial systems
• Smoothed analysis of complex conic condition numbers
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• Perturbation analysis of linear programming problems with random parameters
• A new condition number for linear programming
• Solving linear programs with finite precision. I: Condition numbers and random programs
• On the expected condition number of linear programming problems
• On the average condition of random linear programs

This page was built for publication: Probabilistic analysis of condition numbers for linear programming

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