An Interior Point Method for Linear Programming, with n Active Set Flavor
Tits, Andre L.
MetadataShow full item record
It is now well established that, especially on large linearprogramming problems, the simplex method typically takes upa number of iterations considerably larger than recentinterior-points methods in order to reach a solution.On the other hand, at each iteration, the size of thelinear system of equations solved by the formercan be significantly less than that of the linearsystem solved by the latter.The algorithm proposed in this paper can be thought ofas a compromise between the two extremes: conceptuallyan 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, inthis first attempt, an affine scaling algorithm is usedand strong assumptions are made on the problem. Globaland local quadratic convergence is proved.