Abstract
Interior-Point Methods (IPMs) are not only very effective in practice for solving linear optimization problems but also have polynomial-time complexity. Despite the practical efficiency of large-update algorithms, from a theoretical point of view, these algorithms have a weaker iteration bound with respect to small-update algorithms. In fact, there is a significant gap between theory and practice for large-update algorithms. By introducing self-regular barrier functions, Peng, Roos and Terlaky improved this gap up to a factor of \log n. However, checking these self-regular 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 self-regular, 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 large-update and small-update 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 large-update primal–dual interior-point 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 interior-point 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 primal-dual interior-point 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, “Self-regular functions and new search directions for linear and semidefinite optimization”, Math. Program. 93 (2002) 129–171.
MR1912271
-
J. Peng, C. Roos and T. Terlaky, Self-Regularity. A New Paradigm for Primal–Dual Interior-Point 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
|
