Paper Info

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 |

Authors (3 rows)

Cited by (18 rows)

References (18 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Masakazu Kojima | 1 | 1603 | 222.51 |

Nimrod Megiddo | 2 | 4244 | 668.46 |

Shinji Mizuno | 3 | 792 | 153.37 |