Kybernetika 61 no. 1, 18-31, 2025

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

Imene Touil and Sajad Fathi-HafshejaniDOI: 10.14736/kyb-2025-1-0018

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.

Keywords:

linear programming, complexity analysis, primal-dual interior point methods, kernel functions, large- and small-update methods

Classification:

90C05, 90C51

paper.pdf

References:

  1. M. Achache: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006), 1, 97-110.   DOI:10.1590/S0101-82052006000100005
  2. F. Alizadeh: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995), 13-51.   DOI:10.1137/0805002
  3. Y. Q. Bai and C. Roos: 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.   CrossRef
  4. Y. Q. Bai, M. El Ghami and C. Roos: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004), 101-128.   DOI:10.1137/S1052623403423114
  5. M. Bouafia, D. Benterki and A. Yassine: 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.   DOI:10.1007/s10957-016-0895-0
  6. N. Boudjellal, H. Roumili and D. Benterki: A primal-dual interior point algorithm for convex quadratic programming based on a new parametric kernel function. Optimization 70 (2020) 8, 1-22.   DOI:10.1080/02331934.2020.1751156
  7. Y. Bouhenache, W. Chikouche, I. Touil and S. Fathi-Hafshejani: 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.   CrossRef
  8. B. K. Choi and G. M. Lee: On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function. Nonlinear Anal. 71 (2009), 2628-2640.   DOI:10.1016/j.na.2009.05.078
  9. 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 (2012), 3613-3623.   DOI:10.1016/j.cam.2011.05.036
  10. S. Guerdouh, W. Chikouche and I. Touil: 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.   CrossRef
  11. S. Fathi-Hafshejani, H. Mansouri, M. R. Peyghami and S. Chen: Primal-dual interior-point method for linear optimization based on a kernel function with trigonometric growth term. Optimization (2018), 1029-4945.   DOI:10.1080/02331934.2018.1482297
  12. S. Fathi-Hafshejani and Z. Moaberfard: An interior-point algorithm for linearly constrained convex optimization based on kernel function and application in non-negative matrix factorization. Optim. Engrg. 21 (2020), 1019-1051.   DOI:10.1007/s11081-020-09514-x
  13. N. K. Karmarkar: A new polynomial-time algorithm for linear programming. In: Proc. 16th Annual ACM Symposium on Theory of Computing 4 (1984), 373-395.   CrossRef
  14. R. E. Nesterov and A. S. Nemirovskii: Interior-Point Ploynomial Methods in Convex Programming. Society for Industrial and Applied Mathematics 1994.   CrossRef
  15. J. Peng, C. Roos and T. Terlaky: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002), 129-171.   DOI:10.1007/s101070200296
  16. M. R. Peyghami, S. Fathi-Hafshejani and S. Chen: A primal-dual interior-point method for semidefinite optimization based on a class of trigonometric barrier functions. Oper. Res. Lett. 44 (2016), 319-323.   DOI:10.1016/j.orl.2016.02.013
  17. C. Roos, T. Terlaky and J. Ph. Vial: Theory and algorithms for linear optimization. In: An interior point Approach. John Wiley and Sons, Chichester 1997.   CrossRef
  18. I. Touil, D. Benterki and A. Yassine: A feasible primal-dual interior point method for linear semidefinite programming. J. Comput. Appl. Math. 312 (2017), 216-230.   DOI:10.1016/j.cam.2016.05.008
  19. 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), Article ID 25.   CrossRef
  20. I. Touil and W. Chikouche: Primal-dual interior point methods for semidefinite programming based on a new type of kernel functions. Filomat. 34 (2020), 12, 3957-3969.   DOI:10.2298/FIL2012957T
  21. I. Touil and W. Chikouche: Polynomial-time algorithm for linear programming based on a kernel function with hyperbolic-logarithmic barrier term. PJM 11 (2022), 127-135.   CrossRef
  22. I. Touil and W. Chikouche: Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for SDP problems. Acta Math. Sinica (Engl. Ser.) 38 (2022), 1, 44-67.   DOI:10.1007/s10255-022-1061-0
  23. G. Q. Wang, Y. Q. Bai and C. Roos: Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms Oper. Res. 4 (2005), 4, 409-433.   DOI:10.1007/s10852-005-3561-3