Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions

Le résumé fourni par la source

In this paper, we first present a polynomial-time primal-dual interior-point method (IPM) for solving linear programming (LP) problems, based on a new kernel function (KF) with a hyperbolic-logarithmic barrier term.To improve the iteration bound, we propose a parameterized version of this function.We show that the complexity result meets the currently best iteration bound for large-update methods by choosing a special value of the parameter.Numerical experiments reveal that the new KFs have better results comparing with the existing KFs including log t in their barrier term.To the best of our knowledge, this is the first IPM based on a parameterized hyperboliclogarithmic KF.Moreover, it contains the first hyperbolic-logarithmic KF (Touil and Chikouche in Filomat 34:3957-3969, 2020) as a special case up to a multiplicative constant, and improves significantly both its theoretical and practical results.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.