A novel kernel function bridging iteration bounds in interior-point algorithms for linear programming

Imene Touil; Sajad Fathi-Hafshejani

Kybernetika (2025)

  • Issue: 1, page 18-31
  • ISSN: 0023-5954

Abstract

top
Kernel functions play an important role in designing and analyzing interior-point methods. They are not only used for determining search directions but also for measuring the distance between the given iterate and the $\mu$-center in the algorithms. Currently, interior-point methods based on kernel functions are among the most effective methods for solving different types of optimization problems and are very active research area in mathematical programming. Therefore, in this work, we introduce a novel kernel function that bridges the gap between the iteration bounds for large-update and small-update methods. To the best of our knowledge, we are the first to achieve these results.

How to cite

top

Touil, Imene, and Fathi-Hafshejani, Sajad. "A novel kernel function bridging iteration bounds in interior-point algorithms for linear programming." Kybernetika (2025): 18-31. <http://eudml.org/doc/299932>.

@article{Touil2025,
abstract = {Kernel functions play an important role in designing and analyzing interior-point methods. They are not only used for determining search directions but also for measuring the distance between the given iterate and the $\mu$-center in the algorithms. Currently, interior-point methods based on kernel functions are among the most effective methods for solving different types of optimization problems and are very active research area in mathematical programming. Therefore, in this work, we introduce a novel kernel function that bridges the gap between the iteration bounds for large-update and small-update methods. To the best of our knowledge, we are the first to achieve these results.},
author = {Touil, Imene, Fathi-Hafshejani, Sajad},
journal = {Kybernetika},
language = {eng},
number = {1},
pages = {18-31},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A novel kernel function bridging iteration bounds in interior-point algorithms for linear programming},
url = {http://eudml.org/doc/299932},
year = {2025},
}

TY - JOUR
AU - Touil, Imene
AU - Fathi-Hafshejani, Sajad
TI - A novel kernel function bridging iteration bounds in interior-point algorithms for linear programming
JO - Kybernetika
PY - 2025
PB - Institute of Information Theory and Automation AS CR
IS - 1
SP - 18
EP - 31
AB - Kernel functions play an important role in designing and analyzing interior-point methods. They are not only used for determining search directions but also for measuring the distance between the given iterate and the $\mu$-center in the algorithms. Currently, interior-point methods based on kernel functions are among the most effective methods for solving different types of optimization problems and are very active research area in mathematical programming. Therefore, in this work, we introduce a novel kernel function that bridges the gap between the iteration bounds for large-update and small-update methods. To the best of our knowledge, we are the first to achieve these results.
LA - eng
UR - http://eudml.org/doc/299932
ER -

References

top
  1. Achache, M., , Comput. Appl. Math. 25 (2006), 1, 97-110. MR2267615DOI
  2. Alizadeh, F., , SIAM J. Optim. 5 (1995), 13-51. MR1315703DOI
  3. Bai, Y. Q., Roos, C., A primal-dual interior-point method based on a new kernel function with linear growth rate., In: Proc. Industrial Optimization Symposium and Optimization Day 2002. MR1972215
  4. Bai, Y. Q., Ghami, M. El, Roos, C., , SIAM J. Optim. 15 (2004), 101-128. MR2112978DOI
  5. Bouafia, M., Benterki, D., Yassine, A., , J. Optim. Theory. Appl. 170 (2016), 528-545. MR3527709DOI
  6. Boudjellal, N., Roumili, H., Benterki, D., , Optimization 70 (2020) 8, 1-22. MR4293597DOI
  7. Bouhenache, Y., Chikouche, W., Touil, I., Fathi-Hafshejani, S., Complexity analysis of primal-dual interior-point methods for convex quadratic programming based on a new twice parameterized kernel function., J. Math. Model. 12 (2024), 2, 247-265. MR4777340
  8. Choi, B. K., Lee, G. M., , Nonlinear Anal. 71 (2009), 2628-2640. MR2672034DOI
  9. Ghami, M. El, Guennoun, Z. A., Bouali, S., Steihaug, T., , J. Comput. Appl. Math. 236 (2012), 3613-3623. MR2923494DOI
  10. Guerdouh, S., Chikouche, W., Touil, I., An efficient primal-dual interior point algorithm for linear optimization problems based on a novel parameterized kernel function with a hyperbolic barrier term., 2021. halshs-03228790. MR4601347
  11. Fathi-Hafshejani, S., Mansouri, H., Peyghami, M. R., Chen, S., , Optimization (2018), 1029-4945. MR3882993DOI
  12. Fathi-Hafshejani, S., Moaberfard, Z., , Optim. Engrg. 21 (2020), 1019-1051. MR4125721DOI
  13. Karmarkar, N. K., A new polynomial-time algorithm for linear programming., In: Proc. 16th Annual ACM Symposium on Theory of Computing 4 (1984), 373-395. MR0779900
  14. Nesterov, R. E., Nemirovskii, A. S., Interior-Point Ploynomial Methods in Convex Programming., Society for Industrial and Applied Mathematics 1994. MR1258086
  15. Peng, J., Roos, C., Terlaky, T., , Math. Program. 93 (2002), 129-171. Zbl1007.90037MR1912271DOI
  16. Peyghami, M. R., Fathi-Hafshejani, S., Chen, S., , Oper. Res. Lett. 44 (2016), 319-323. MR3503107DOI
  17. Roos, C., Terlaky, T., Vial, J. Ph., Theory and algorithms for linear optimization., In: An interior point Approach. John Wiley and Sons, Chichester 1997. MR1450094
  18. Touil, I., Benterki, D., Yassine, A., , J. Comput. Appl. Math. 312 (2017), 216-230. MR3557876DOI
  19. Touil, I., Benterki, D., A primal-dual interior-point method for the semidefinite programming problem based on a new kernel function., J. Nonlinear Funct. Anal. (2019), Article ID 25. 
  20. Touil, I., Chikouche, W., , Filomat. 34 (2020), 12, 3957-3969. MR4290825DOI
  21. Touil, I., Chikouche, W., Polynomial-time algorithm for linear programming based on a kernel function with hyperbolic-logarithmic barrier term., PJM 11 (2022), 127-135. MR4447022
  22. Touil, I., Chikouche, W., , Acta Math. Sinica (Engl. Ser.) 38 (2022), 1, 44-67. MR4375772DOI
  23. Wang, G. Q., Bai, Y. Q., Roos, C., , J. Math. Model. Algorithms Oper. Res. 4 (2005), 4, 409-433. MR2231552DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.