Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming

DOI10.1287/MOOR.24.1.176zbMath0977.90019OpenAlexW2086040751MaRDI QIDQ2757589

Yinyu Ye, Jun Ji, Florian A. Potra, Kurt M. Anstreicher

Publication date: 26 November 2001

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e7f3961cd393f041bb6a69355c7e6a891d35fdc6

zbMATH Keywords

linear programminginfeasible-interior-point algorithmaverage-case behavior

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51)

Related Items (9)

Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure. ⋮ Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Probabilistic analysis of a differential equation for linear programming ⋮ On the probabilistic complexity of finding an approximate solution for linear programming ⋮ New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction ⋮ A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points ⋮ Conditioning of random conic systems under a general family of input distributions ⋮ Average number of iterations of some polynomial interior-point -- algorithms for linear programming

This page was built for publication: Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming