Journal article
Long steps in an O(n 3 L) algorithm for linear programming
Mathematical programming, Vol.54(1-3), pp.251-265
02/1992
DOI: 10.1007/BF01586053
Abstract
We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein-Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n3L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous "primal-only" initialization actually reduces the complexity to less than O(m1.5n1.5L). © 1992 The Mathematical Programming Society, Inc.
Details
- Title: Subtitle
- Long steps in an O(n 3 L) algorithm for linear programming
- Creators
- Kurt M. Anstreicher - Yale UniversityRobert A. Bosch - Yale University
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.54(1-3), pp.251-265
- DOI
- 10.1007/BF01586053
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 02/1992
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984380409902771
Metrics
1 Record Views