Journal article
Volumetric path following algorithms for linear programming
Mathematical programming, Vol.76(1), pp.245-263
01/02/1997
DOI: 10.1007/BF02614386
Abstract
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(n1/4m1/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(n2m), as opposed to O(nm2), 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.
Details
- Title: Subtitle
- Volumetric path following algorithms for linear programming
- Creators
- Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.76(1), pp.245-263
- DOI
- 10.1007/BF02614386
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 01/02/1997
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984380534202771
Metrics
3 Record Views