Journal article
Near boundary behavior of primal-dual potential reduction algorithms for linear programming
Mathematical programming, Vol.58(2), pp.243-255
01/1993
DOI: 10.1007/BF01581269
Abstract
This paper is concerned with selection of the p-parameter in the primal-dual potential reduction algorithm for linear programming. Chosen from [n +,fn, ~), the level of p determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, p must be set close to n +x/~. This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate that p can be sometimes chosen in a wide range In +~ff, co) while still guaranteeing the currently best convergence rate of o(,fn L) iterations. This finding is encouraging since in practice large values of p have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.
Details
- Title: Subtitle
- Near boundary behavior of primal-dual potential reduction algorithms for linear programming
- Creators
- K. O Kortanek - University of IowaJ Kaliski - University of IowaS Huang - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.58(2), pp.243-255
- DOI
- 10.1007/BF01581269
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Publisher
- Springer
- Number of pages
- 13
- Language
- English
- Date published
- 01/1993
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963220602771
Metrics
1 Record Views