A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods

• Autores: Keyvan Amini, Arash Haseli
• Localización: Anziam journal: The Australian & New Zealand industrial and applied mahtematics journal, ISSN 1446-1811, Vol. 49, Nº 2, 2007, págs. 259-270
• Idioma: inglés
• DOI: 10.1017/s1446181100012827
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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 logn . 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.