Journal article
A New Infinity-Norm Path Following Algorithm for Linear Programming
SIAM journal on optimization, Vol.5(2), pp.236-246
05/01/1995
DOI: 10.1137/0805013
Abstract
We devise a new primal-dual path following algorithm for linear programming that is based entirely on an infinity-norm centering measure. The algorithm makes reductions in a path parameter $\mu $, each of which is followed by a sequence of centering steps. The algorithm has similarities with both long step path following and predictor-corrector methods. We also consider a "modified" version of the algorithm that uses partial updating of the projection equations. The analysis of the modified algorithm has some interesting differences compared with previously devised partial updating methods. In particular, partial updating obtains a factor-of-$\sqrt{n}$ complexity reduction even though the permissible relative error in the approximate scaling factors is extremely small -- only $O( 1/ \sqrt{n})$.
Details
- Title: Subtitle
- A New Infinity-Norm Path Following Algorithm for Linear Programming
- Creators
- Kurt M AnstreicherRobert A Bosch
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.5(2), pp.236-246
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/0805013
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 05/01/1995
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380591502771
Metrics
4 Record Views