Accession Number:

ADA455258

Title:

An Optimal Basis Identification Technique for Interior-Point Linear Programming Algorithms

Descriptive Note:

Technical rept.

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES

Personal Author(s):

• Tapia, R. A.
• Zhang, Yin

Report Date:

1990-09-01

Pagination or Media Count:

23.0

Abstract:

This work concerns a method for identifying an optimal basis for linear programming problems in the setting of interior point methods. To each iterate x-superscript-k generated by a primal interior point algorithm, say, we associate an indicator vector q-superscript-k with the property that if x-superscript-k converges to a nondegenerate vertex x, then q-superscript-k converges to the 0-1 vector signx. More interestingly, we show that the convergence of q-superscript-k is quadratically faster than that of x-superscript-k in the sense that q-superscript-k - q Ox-superscript-k - x-sq. This clear-cut separation and rapid convergence allow one to infer at an intermediate stage of the iterative process which variables will be zero at optimality and which will not. We also show that under suitable assumptions this method is applicable to dual as well as primal-dual algorithms and can be extended to handle certain types of degeneracy. Numerical examples are included to corroborate the convergence properties of the indicators. The practical limitations of the indicator technique are also discussed.

Descriptors:

• *LINEAR PROGRAMMING
• ALGORITHMS
• CONVERGENCE
• INDICATORS
• SEPARATION
• OPTIMIZATION

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE