An optimal-basis identification technique for interior-point linear programming algorithms

AbstractThis work concerns a method for identifying an optimal basis for linear programming problems in the setting of interior-point methods. To each iterate xk generated by a primal interior-point algorithm, say, we associate an indicator vector qk with the property that if xk converges to a nondegenerate vertex x∗, then qk converges to the 0–1 vector sign(x∗). More interestingly, we show that the convergence of qk is quadratically faster than that of xk in the sense that ||qk−q7ast;||=O(||xk−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