ANZIAM J. 49 (2007), no. 2, pp. 259–270.
A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods
Keyvan Amini† Arash Haseli
Department of Sciences
Razi University
Kermanshah
Iran
keyvanamini1353@yahoo.com
kamini@razi.ac.ir		 Islamic Azad University
Kermanshah branch
Kermanshah
Iran
arhaseli@yahoo.com
Received 16 December, 2006; revised 6 August, 2007

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

  1. 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
  2. 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
  3. 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.
  4. 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
  5. 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
  6. 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
  7. C. Roos, T. Terlaky and J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior Point Approach (John Wiley & Sons, Chichester, 1997). MR1450094