Geodesic
Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions
Kybernetika, Tome 59 (2023) no. 6, pp. 827-860 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 hyperbolic-logarithmic 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.
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 hyperbolic-logarithmic 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.
DOI : 10.14736/kyb-2023-6-0827
Classification : 90C05, 90C51
Keywords: linear programming; primal-dual interior-point methods; kernel function; complexity analysis; large and small-update methods 
@article{10_14736_kyb_2023_6_0827,
     author = {Guerdouh, Safa and Chikouche, Wided and Touil, Imene and Yassine, Adnan},
     title = {Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions},
     journal = {Kybernetika},
     pages = {827--860},
     year = {2023},
     volume = {59},
     number = {6},
     doi = {10.14736/kyb-2023-6-0827},
     mrnumber = {4712965},
     zbl = {07830567},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-6-0827/}
}
TY  - JOUR
AU  - Guerdouh, Safa
AU  - Chikouche, Wided
AU  - Touil, Imene
AU  - Yassine, Adnan
TI  - Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions
JO  - Kybernetika
PY  - 2023
SP  - 827
EP  - 860
VL  - 59
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-6-0827/
DO  - 10.14736/kyb-2023-6-0827
LA  - en
ID  - 10_14736_kyb_2023_6_0827
ER  - 
%0 Journal Article
%A Guerdouh, Safa
%A Chikouche, Wided
%A Touil, Imene
%A Yassine, Adnan
%T Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions
%J Kybernetika
%D 2023
%P 827-860
%V 59
%N 6
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2023-6-0827/
%R 10.14736/kyb-2023-6-0827
%G en
%F 10_14736_kyb_2023_6_0827
Guerdouh, Safa; Chikouche, Wided; Touil, Imene; Yassine, Adnan. Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions. Kybernetika, Tome 59 (2023) no. 6, pp. 827-860. doi: 10.14736/kyb-2023-6-0827

Cité par Sources :