polynomial complexity

A Dynamic Large-Update Primal-Dual Interior-Point Method for Linear Optimization

  • Jiming Peng
  • Tamás Terlaky
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results, with respect to the strategies of updating the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy … Read more

    A New and Efficient Large-Update Interior-Point Method for Linear Optimization

  • Jiming Peng
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently, the authors presented a new large-update primal-dual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of … Read more