Instytut Matematyczny Polskiej Akademii Nauk / pl / Wydawnictwa / Czasopisma IMPAN / Applicationes Mathematicae / Wszystkie zeszyty

Streszczenie

The aim of this work is to improve the complexity result for the large-update method. First, we present a new bi-parametric kernel function with a hyperbolic barrier term. Then using simple tools, we show that the complexity bound of the algorithm based on the proposed kernel function for the large-update method is $\mathcal O\big(\sqrt {n}\log n\log \frac{n}{\epsilon}\big)$ iterations. This result coincides with the current best known iteration bounds for interior point methods based on all existing types of kernel functions. To illustrate the effectiveness of the algorithm developed, we give some numerical tests.