Abstract
InteriorPoint Methods (IPMs) are not only very effective in practice for solving linear optimization problems but also have polynomialtime complexity. Despite the practical efficiency of largeupdate algorithms, from a theoretical point of view, these algorithms have a weaker iteration bound with respect to smallupdate algorithms. In fact, there is a significant gap between theory and practice for largeupdate algorithms. By introducing selfregular barrier functions, Peng, Roos and Terlaky improved this gap up to a factor of \log n. However, checking these selfregular functions is not simple and proofs of theorems involving these functions are very complicated. Roos et al. by presenting a new class of barrier functions which are not necessarily selfregular, achieved very good results through some much simpler theorems. In this paper we introduce a new kernel function in this class which yields the best known complexity bound, both for largeupdate and smallupdate methods.
Download the article in PDF format (size 124 Kb)
2000 Mathematics Subject Classification:
primary 90C05; secondary 90C51

(Metadata: XML, RSS, BibTeX) 
MathSciNet:
MR2376??? 
^{†}indicates author for correspondence 
References

Y. Q. Bai, M. El Ghami and C. Roos, “A new efficient largeupdate primal–dual interiorpoint method based on a finite barrier”, SIAM J. Optim. 13 (2003) 766–782 (electronic).
MR1972215

Y. Q. Bai, M. El Ghami and C. Roos, “A comparative study of new barrier functions for primal–dual interiorpoint algorithms in linear optimization”, SIAM J. Optim. 15 (2004) 101–128.
MR2112978

Y. Q. Bai, J. Guo and C. Roos, “A new kernel function yielding the best known iteration bounds for primaldual interiorpoint algorithms”, 2006, working paper, available at http://www.isa.ewi.tudelft.nl/~roos/wpapers.html.

N. Megiddo, “Pathways to the optimal set in linear programming”, in Progress in Mathematical Programming: Interior Point and Related Methods (ed. N. Megiddo), (Springer Verlag, New York, 1989), 131–158.
(Identical version in: Proceedings of the 6th Mathematical Programming Symposium of Japan, Nagoya, Japan, pages 1–35, 1986).
MR982720

J. Peng, C. Roos and T. Terlaky, “Selfregular functions and new search directions for linear and semidefinite optimization”, Math. Program. 93 (2002) 129–171.
MR1912271

J. Peng, C. Roos and T. Terlaky, SelfRegularity. A New Paradigm for Primal–Dual InteriorPoint Algorithms (Princeton University Press, Princeton, New Jersey, 2002).
MR1938497

C. Roos, T. Terlaky and J.Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior Point Approach (John Wiley & Sons, Chichester, 1997).
MR1450094
