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-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 sign(x*). More interestingly, we show that the convergence of q-superscript-k is quadratically faster than that of x- superscript-k in the sense that.