Smoothed Analysis of Interior-Point Algorithms: Termination

Daniel Spielman (spielmanmath.mit.edu)
Shang-Hua Teng (stengcs.bu.edu)

Abstract: We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound on the worst-case complexity of linear programming is $O (m^{3} L)$, where $L$ could be as large as $m$. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses.

Keywords: smoothed analysis, condition number, linear programming, interior-point methods

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation:

Download: [Postscript][PDF]

Entry Submitted: 01/21/2003
Entry Accepted: 01/21/2003
Entry Last Modified: 01/21/2003

Modify/Update this entry