Accession Number:

ADA231903

Title:

An Adaptive Primal-Dual Method for Linear Programming

Descriptive Note:

Technical rept

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s):

Report Date:

1991-01-01

Pagination or Media Count:

13.0

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.

Descriptors:

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE