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

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^k generated by a primal interior point algorithm, say, we associate an indicator vector q^k with the property that if x^k converges to a nondegenerate vertex x*, then q^k converges to the 0-1 vector sign (x*). More interestingly, we show that the convergence of q^k is quadratically faster than that of x^k in the sense that q^k-q* = O (x^k-x*)^2. 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