In this paper we are generalizing the efficient kernel function with trigonometric barrier term given by (M. Bouafia, D. Benterki and A. Yassine, J. Optim. Theory Appl. 170 (2016) 528–545). Using an elegant and simple analysis and under some easy to check conditions, we explore the best complexity result for the large update primal-dual interior point methods for linear optimization. This complexity estimate improves results obtained in (X. Li and M. Zhang, Oper. Res. Lett. 43 (2015) 471–475; M.R. Peyghami and S.F. Hafshejani, Numer. Algo. 67 (2014) 33–48; M. Bouafia, D. Benterki and A. Yassine, J. Optim. Theory Appl. 170 (2016) 528–545). Our comparative numerical experiments on some test problems consolidate and confirm our theoretical results according to which the new kernel function has promising applications compared to the kernel function given by (M. Bouafia and A. Yassine, Optim. Eng. 21 (2020) 651–672). Moreover, the comparative numerical study that we have established favors our new kernel function better than other best trigonometric kernel functions (M. Bouafia, D. Benterki and A. Yassine, J. Optim. Theory Appl. 170 (2016) 528–545; M. Bouafia and A. Yassine, Optim. Eng. 21 (2020) 651–672).
Keywords: Linear optimization, Kernel function, Interior point methods, Complexity bound
@article{RO_2022__56_2_731_0,
author = {Mousaab, Bouafia and Adnan, Yassine},
title = {Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient {Bi-parameterized} kernel function with a trigonometric barrier term},
journal = {RAIRO. Operations Research},
pages = {731--750},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {2},
doi = {10.1051/ro/2022032},
mrnumber = {4407593},
zbl = {1492.90080},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022032/}
}
TY - JOUR AU - Mousaab, Bouafia AU - Adnan, Yassine TI - Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term JO - RAIRO. Operations Research PY - 2022 SP - 731 EP - 750 VL - 56 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022032/ DO - 10.1051/ro/2022032 LA - en ID - RO_2022__56_2_731_0 ER -
%0 Journal Article %A Mousaab, Bouafia %A Adnan, Yassine %T Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term %J RAIRO. Operations Research %D 2022 %P 731-750 %V 56 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022032/ %R 10.1051/ro/2022032 %G en %F RO_2022__56_2_731_0
Mousaab, Bouafia; Adnan, Yassine. Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term. RAIRO. Operations Research, Tome 56 (2022) no. 2, pp. 731-750. doi: 10.1051/ro/2022032
[1] and , A primal-dual interior point method based on a new kernel function with linear growth rate. In Proceedings of the 9th Australian Optimization Day, Perth, Australia (2002).
[2] , and , A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization. SIAM J. Optim. 15 (2005) 101–128. | MR | Zbl | DOI
[3] and , An efficient twice parameterized trigonometric kernel function for linear optimization. Optim. Eng. 21 (2020) 651–672. | MR | Zbl | DOI
[4] , and , An efficient primal-dual Interior Point Method for linear programming problems based on a new kernel function with a trigonometric barrier term. J. Optim. Theory Appl. 170 (2016) 528–545. | MR | Zbl | DOI
[5] , , and , Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term. J. Comput. Appl. Math. 236 (2012) 3613–3623. | MR | Zbl | DOI
[6] , , and , Primal–dual interior-pointmethod for linear optimization based on a kernel function with trigonometric growth term. Optimization 67 (2018) 1605–1630. | MR | Zbl | DOI
[7] , A new polynomial-time algorithm for linear programming. In Vol. 4 of Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984) 373–395. | MR | Zbl
[8] and , Interior-point algorithm for linear optimization based on a new trigonometric kernel function. Oper. Res. Lett. 43 (2015) 471–475. | MR | Zbl | DOI
[9] , Pathways to the optimal set in linear programming. In Progress in Mathematical Programming: Interior Point and Related Methods, edited by , Springer-Verlag, New York (1989) 131–158. | MR | Zbl | DOI
[10] , and , Self-Regularity: A New Paradigm for Primal-Dual interior point Algorithms, Princeton University Press, Princeton, NJ (2002). | MR | Zbl
[11] and , Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function. Numer. Algo. 67 (2014) 33–48. | MR | Zbl | DOI
[12] , and , Complexity of interior point methods for linear optimization based on a new trigonometric kernel function. J. Comput. Appl. Math. 255 (2014) 74–85. | MR | Zbl | DOI
[13] , and , Theory and algorithms for linear optimization, In An interior point Approach, John Wiley & Sons, Chichester, UK (1997). | MR | Zbl
[14] , An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In Vol. 84 of System Modelling and Optimization: Proceedings of the 12th IFIP-Conference, Budapest, Hungary, 1985, in: Lecture Notes in Control and Inform. Sci., edited by , , . Springer-Verlag, Berlin (1986) 866–876. | MR | Zbl | DOI
[15] , Interior point algorithms. Theory and Analysis, John-Wiley Sons, Chichester, UK (1997). | MR | Zbl | DOI
Cité par Sources :
