Journal article
Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
Mathematical programming, Vol.62(1-3), pp.517-535
02/1993
DOI: 10.1007/BF01585181
Abstract
In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve {Mathematical expression} step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective. © 1993 The Mathematical Programming Society, Inc.
Details
- Title: Subtitle
- Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
- Creators
- Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.62(1-3), pp.517-535
- DOI
- 10.1007/BF01585181
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 02/1993
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984380513202771
Metrics
3 Record Views