Title | ||
---|---|---|
Theoretical convergence of large-step primal-dual interior point algorithms for linear programming |
Abstract | ||
---|---|---|
Abstract: This paper proposes two sets of rules, Rule G and Rule P, for controllingstep lengths in a generic primal-dual interior point method for solving the linear programmingproblem in standard form and its dual. Theoretically, Rule G ensures the globalconvergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iterationpolynomial-time computational complexity. Both rules depend only on the lengths of thesteps from the current iterates in the primal and dual spaces to the... |
Year | DOI | Venue |
---|---|---|
1993 | 10.1007/BF01581234 | Math. Program. |
Keywords | Field | DocType |
theoretical convergence,large step,linear program,linear programming,global convergence,poly- nomial-time convergence.,primal-dual interior point algorithm,large-step primal-dual interior point,dual space,computational complexity | Convergence (routing),Mathematical optimization,Algorithm,Line search,Duality (optimization),Linear programming,Time complexity,Iterated function,Interior point method,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
59 | 1 | 1436-4646 |
Citations | PageRank | References |
18 | 1.74 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Masakazu Kojima | 1 | 1603 | 222.51 |
Nimrod Megiddo | 2 | 4244 | 668.46 |
Shinji Mizuno | 3 | 792 | 153.37 |