|
Article information
2001 , Volume 6, ¹ 4, p.61-80
Peng J., Roos C., Terlaky T.
A new and efficient large-update interior-point method for linear optimization
Recently the authors presented a new large-update primal-dual method for Linear Optimization, whose iteration bound substantially improved the classical bound for such methods. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools, partially developed in [11], where we consider a whole family of interior-point methods which contains the method considered in this paper. The new analysis yields an iteration bound for large-update methods. Since we concentrate on one specific member of the family considered in [11], the analysis is significantly simpler than in [11]. 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. Hence, the existing gap between the iteration bounds for small-update and large-update methods is substantially narrowed.
[full text] Classificator Msc2000:- *90C05 Linear programming
- 90C33 Complementarity problems
- 90C51 Interior-point methods
Keywords: primal-dual algorithm, updating the barrier parameter, polynomial barrier function, small-update method
Author(s):
Peng J
Office: Delft University of Technology
Address: Netherlands, Delft
E-mail: J.Peng@its.tudelft.nl
Roos C
Office: Delft University of Technology
Address: Netherlands, Delft
E-mail: c.roos@its.tudelft.nl
Terlaky T
Office: McMaster University, Hamilton, Ontario,
Address: Canada, Hamilton
E-mail: c.roos@its.tudelft.nl
Bibliography link:
Peng J., Roos C., Terlaky T. A new and efficient large-update interior-point method for linear optimization // Computational technologies. 2001. V. 6. ¹ 4. P. 61-80
|
