Volumetric path following algorithms for linear programming
Anstreicher, Kurt M.

Fecha: 1997
Resumen: We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n^1/4m^1/4L) iteration algorithm for linear programs with n variables and m inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n^2m), as opposed to O(nm^2), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. .
Derechos: Tots els drets reservats.
Lengua: Anglès
Documento: Article ; recerca ; Versió publicada
Materia: Linear programming ; Path following ; Volumetric barrier ; Self-concordancy
Publicado en: Mathematical Programming, vol. 76 n. 1 (1997) p. 245-263, ISSN 0025-5610



19 p, 866.9 KB
 Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2006-03-13, última modificación el 2023-06-03



   Favorit i Compartir