-

 

 

 




Optimization Online





 

Smoothed Analysis of Interior-Point Algorithms: Termination

Daniel Spielman (spielman***at***math.mit.edu)
Shang-Hua Teng (steng***at***cs.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


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society