An efficient 2-parameter hyperbolic kernel-function-based interior-point method for linear programming
Tom 53 / 2026
Applicationes Mathematicae 53 (2026), 13-35
MSC: Primary 90C05; Secondary 90C51
DOI: 10.4064/am2560-3-2025
Opublikowany online: 2 February 2026
Streszczenie
The aim of this work is to improve the complexity result for the large-update method. First, we present a new 2-parameter 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}\ln n\ln \frac{n}{\epsilon }\big)$ iterations. This result matches the best-known iteration bounds for interior-point methods based on all existing types of kernel functions. Finally, to illustrate the effectiveness of the algorithm, we provide numerical tests.
