An Active-Set Strategy in Interior Point Method for Linear Programming

We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks -active constraints- will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( √nL) iterations with the same polynomial bound with the full constraints case, where n is the number of variables and L is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration will be fairly reduced by the proposed strategy. As a special case of this strategy, we will show that the interior point method can be managed by the basis factorization techniques of the simplex method coupled with a sequence of rank-one changes to matrices.This research was partially done in June 1990 while the author was visiting Department of Mathematics, University of Pisa.departmental bulletin pape