An Efficient Hyperbolic Kernel Function Yielding the Best Known Iteration Bounds for Linear Programming

Abstract

Interior-point methods (IPMs) for linear programming (LP) are generally based on the logarithmic barrier function. Peng et al. (J. Comput. Technol. 6: 61–80, 2001) were the first to propose non-logarithmic kernel functions (KFs) for solving IPMs. These KFs are strongly convex and smoothly coercive on their domains. Later, Bai et al. (SIAM J. Optim. 15(1): 101–128, 2004) introduced the first KF with a trigonometric barrier term. Since then, no new type of KFs were proposed until 2020, when Touil and Chikouche (Filomat. 34(12): 3957–3969, 2020; Acta Math. Sin. (Engl. Ser.), 38(1): 44–67, 2022) introduced the first hyperbolic KFs for semidefinite programming (SDP). They established that the iteration complexities of algorithms based on their proposed KFs are $$\mathcal{O}(n^{\frac{2}{3}}\log \frac{n}{ϵ})$$ and $$\mathcal{O}(n^{\frac{3}{4}}\log \frac{n}{ϵ})$$ for large-update methods, respectively. The aim of this work is to improve the complexity result for large-update method. In fact, we present a new parametric KF with a hyperbolic barrier term. By simple tools, we show that the worst-case iteration complexity of our algorithm for the large-update method is $$\mathcal{O}(\sqrt{n}\log n\log \frac{n}{ϵ})$$ iterations. This coincides with the currently best-known iteration bounds for IPMs based on all existing kind of KFs.

The algorithm based on the proposed KF has been tested. Extensive numerical simulations on test problems with different sizes have shown that this KF has promising results.