Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions

• Autores: Y.B. Zhao
• Localización: Applied numerical mathematics, ISSN-e 0168-9274, Vol. 57, Nº. 9, 2007, págs. 1033-1049
• Idioma: inglés
• DOI: 10.1016/j.apnum.2006.09.009
• Texto completo no disponible (Saber más ...)
• Resumen

  • It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than its small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far best known iteration complexity and superlinear (or quadratic) convergence of the original interior-point algorithms. The idea of our methods is to use the global minimizers of proximity measure functions.