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

Loading...
Thumbnail Image

Files

TR_99-47.pdf (270.04 KB)
No. of downloads: 396

Publication or External Link

Date

1999

Advisor

Citation

DRUM DOI

Abstract

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.

Notes

Rights