An Interior Point Method for Linear Programming, with an Active Set Flavor

It is now well established that, especially on large linear programming problems, the simplex method typically takes up a number of iterations considerably larger than recent interior-points methods in order to reach a solution. On the other hand, at each iteration, the size of the linear system of equations solved by the former can be significantly less than that of the linear system solved by the latter. The algorithm proposed in this paper can be thought of as a compromise between the two extremes: conceptually an interior-point method, it ignores, at each iteration, all constraints except those in a small "active set" (in the dual framework). For sake of simplicity, in this first attempt, an affine scaling algorithm is used and strong assumptions are made on the problem. Global and local quadratic convergence is proved. 1 Introduction and Algorithm Statement Consider the problem the linear programming problem (in dual form) (P ) minimize hc; xi s.t. Ax b; x 2 IR n ; with A a..