An Adaptive Primal-Dual Method for Linear Programming
Abstract
The short-step interior-point methods that allow nice polynomial-time proofs of convergence for linear programming turn out to be much too slow for practical algorithms. Thus a number of long-step methods have been analyzed to date, most of which are aimed at proving the correctness of existing numerical implementations. In Section 3.1, however, we have presented a worst-case example in which the iterates x, y, z are not able to follow a long step in the reduction of the complementarity parameter microns. The possibility of such worst cases is responsible for the weak proofs of convergence for long-step methods. These proofs not only fail to explain the fast convergence of the implementations that has been observed for all numerical examples, but also exhibit a wore theoretical complexity than even the short-step methods. The adaptive method presented here is intended to close the gap between the oretical and practical complexity.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA231903
Entities
People
- Florian Jarre
- Michael Saunders
Organizations
- Stanford University