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

Data: 1997
Resum: 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. .
Llengua: Anglès.
Document: Article ; recerca ; article ; publishedVersion
Matèria: Linear programming ; Path following ; Volumetric barrier ; Self-concordancy
Publicat a: Mathematical Programming, vol. 76 n. 1 (1997) p. 245-263, ISSN 0025-5610

19 p, 866.9 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2017-10-28

   Favorit i Compartir