Polynomial-time algorithm for linear programming based on a kernel function with hyperbolic-logarithmic barrier term. (English) Zbl 1491.90098
Summary: In this work, we present an interior point algorithm for linear optimization problems based on a kernel function which has a hyperbolic-logarithmic function in its barrier term. This kernel function was first proposed by the authors themselves for semi-definite programming (SDP) problems in [the authors, Filomat 34, No. 12, 3957–3969 (2020; Zbl 1499.90148)]. By simple analysis tools, several properties of the proposed kernel function are used to compute the total number of iterations. We show that the worst-case iteration complexity of our algorithm for large-update methods improves the obtained iteration bounds based on the first trigonometric [M. El Ghami et al., J. Comput. Appl. Math. 236, No. 15, 3613–3623 (2012; Zbl 1242.90292)] as well as the classic kernel functions. For small-update methods, we derive the best known iteration bound. Numerical tests reveal that the proposed kernel function has promising results comparing with some existing kernel functions.
MSC:
| 90C05 | Linear programming |
| 90C51 | Interior-point methods |
| 90C31 | Sensitivity, stability, parametric optimization |
Keywords:
linear programming; primal-dual interior point methods; kernel functions; complexity analysis; large- and small-update methodsReferences:
| [1] | Y.Q. Bai, M. EL. Ghami and C. Roos, A comparative study of kernel functions for primal-dual interiorpoint algorithms in linear optimization,SIAM J. Optim.15, 101-128 (2004). · Zbl 1077.90038 |
| [2] | Y. Q. Bai, J. L. Guo and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithmsActa Math. Sin. Engl. Ser.25(12), 2169-2178 (2009). · Zbl 1184.90099 |
| [3] | M. Bouafia, D. Benterki and A. Yassine, An efficient parameterised logarithmic kernel function for linear optimization,Optim. Lett.12, 1079-1097 (2018). · Zbl 1423.90135 |
| [4] | M. Bouafia and A. Yassine, An efficient twice parameterized trigonometric kernel function for linear optimization,Optim. Eng.21, 651-672 (2020). · Zbl 1447.90018 |
| [5] | M. El Ghami, Z.A. Guennoun, S. Bouali and T. Steihaug, Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term,J. Comput. Appl. Math.236, 3613-3623 (2012). · Zbl 1242.90292 |
| [6] | M. El Ghami, I.D. Ivanov, C. Roos and T. Steihaug, A polynomial-time algorithm for LO based on generalized logarithmic barrier functions,Int. J. Appl. Math.21, 99-115 (2008). · Zbl 1142.90018 |
| [7] | S. Fathi-Hafshejani and A. Fakharzadeh Jahromi, An interior point method forP∗(K)-horizontal linear complementarity problem based on a new proximity function,J. Appl. Math. Comput.(2019). · Zbl 1475.90109 |
| [8] | S. Fathi-Hafshejani and Z. Moaberfard, A generic kernel function for interior point methods,Optim. Eng. 22, 261-291 (2021). · Zbl 1474.65164 |
| [9] | N.K. Karmarkar, A new polynomial-time algorithm for linear programming,In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing.4, 373-395 (1984). · Zbl 0557.90065 |
| [10] | A. Keraghel, Etude adaptative et comparative des principales variantes dans l’algorithme de karmarkar, Ph.D. thesis, Joseph Fourier University, Grenoble I, France, 1989. |
| [11] | M. Li, M. Zhang, K. Huang et al., A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function,Optim. Eng.22, 293-319 (2021). · Zbl 1474.90516 |
| [12] | 9. J. Peng, C. Roos and T. Terlaky, A new and efficient large-update interior point method for linear optimization,J. Comput. Technol.6, 61-80 (2001). · Zbl 0987.90089 |
| [13] | 10. J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization,Math. Program.93, 129-171 (2002). · Zbl 1007.90037 |
| [14] | 11. J. Peng, C. Roos and T. Terlaky, Self-regularity: A new Paradigm for Primal-Dual Interior-Point Algorithms,Princeton University Press,Princeton, NJ, 2002. · Zbl 1136.90045 |
| [15] | 12. M.R. Peyghami, S.F. Hafshejani and L. Shirvani, Complexity of interior point methods for linear optimization based on a new trigonometric kernel function,J. Comput. Appl. Math.255, 74-85 (2014). · Zbl 1291.90313 |
| [16] | C. Roos, T. Terlaky and J.Ph. Vial, Theory and algorithms for linear optimization, in: An interior point Approach,John Wiley & Sons,Chichester, UK (1997). · Zbl 0954.65041 |
| [17] | I. Touil and D. Benterki, A primal-dual interior-point method for the semidefinite programming problem based on a new kernel function,J. Nonlinear Funct. Anal.2019 (2019), Article ID 25. |
| [18] | I. Touil and W. Chikouche, Primal-dual interior point methods for semidefinite programming based on a new type of kernel functions,Filomat,34(12), (2020). · Zbl 1487.90518 |
| [19] | I. Touil and W. Chikouche, Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for SDP problems, To appear inActa Math. Appl. Sin. Engl. Ser.(2022). · Zbl 1487.90518 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
