A New and Efficient Large-Update Interior-Point Method for Linear Optimization

J Peng (pengjcas.mcmaster.ca)
C Roos (C.Roosits.tudelft.nl)
T Terlaky (terlakypop.cas.mcmaster.ca )

Abstract: Recently, the authors presented a new large-update primal-dual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of interior-point methods which contains the method considered in this paper. The new analysis yields an $O\br{\sqrt{n}\log n\,\log\frac{n}{\e}}$ iteration bound for large-update methods. Since we concentrate on one specific member of the family mentioned before, the analysis significantly simplifies. The new bound further improves the iteration bound for large-update methods, and is quite close to the currently best iteration bound known for interior-point methods, namely $O\br{\sqrt{n}\,\log\frac{n}{\e}}$. Hence, the existing gap between the iteration bounds for small-update and large-update methods is substantially narrowed.

Keywords: Linear optimization, interior-point method, primal-dual Newton method, large-update method, polynomial complexity

Category 1: Linear, Cone and Semidefinite Programming

Citation: TU Delft, NL/McMaster University, Hamilton January 2001

Download: [Postscript][PDF]

Entry Submitted: 01/31/2001
Entry Accepted: 01/31/2001
Entry Last Modified: 01/31/2001

Modify/Update this entry