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

Simple item page
dc.contributor.authorTits, Andre L.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T10:07:19Z
dc.date.available2007-05-23T10:07:19Z
dc.date.issued1999en_US
dc.description.abstractIt 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.en_US
dc.format.extent276516 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/6027
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1999-47en_US
dc.subjectoptimizationen_US
dc.subjectlinear programmingen_US
dc.subjectinterior-point methodsen_US
dc.subjectactive seten_US
dc.subjectIntelligent Control Systemsen_US
dc.titleAn Interior Point Method for Linear Programming, with n Active Set Flavoren_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_99-47.pdf
Size:
270.04 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports