Kybernetika 62 no. 1, 55-76, 2026

An infeasible interior-point algorithm for monotone linear complementary problems based on a finite hyperbolic kernel function

Safa Guerdouh, Wided Chikouche and Behrouz KheirfamDOI: 10.14736/kyb-2026-1-0055

Abstract:

This paper concerns an infeasible kernel-based interior-point algorithm (IPA) for monotone linear complementarity problems (LCPs). Our algorithm differs from other existing algorithms in the literature since its feasibility step is induced by a finite hyperbolic barrier term. The convergence analysis shows that the proposed algorithm is well-defined and its complexity bound coincides with the currently best-known iteration bound of infeasible interior-point methods for monotone LCPs. Moreover, the practical performance of our algorithm is validated by some extensive numerical tests. To the best of our knowledge, this is the first full-Newton step infeasible IPA based on a hyperbolic kernel function for solving monotone LCPs.

Keywords:

polynomial complexity, infeasible interior-point method, kernel function, linear complementarity problems

Classification:

90C51, 90C33

paper.pdf

References:

  1. K. Amini and M. R. Peyghami: An interior-point method for linear programming based on a class of kernel functions. Bull. Austral. Math. Soc. 71 (2005), 139-153.   DOI:10.1017/S0004972700038090
  2. Y. Q. Bai, M. El Ghami and C. Roos: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13 (2002), 766-782.   DOI:10.1137/s1052623401398132
  3. 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
  4. Y. Bouhenache, W. Chikouche and S. Guerdouh: An interior-point algorithm for LCP based on a parameterized hyperbolic kernel function. Comput. Math. Math. Phys. 65 (2025), 1181-1194.   DOI:10.1134/S096554252570054X
  5. Y. Bouhenache, W. Chikouche and I. Touil: A large-update primal-dual interior-point algorithm for convex quadratic optimization based on a new bi-parameterized bi-hyperbolic kernel function. Lobach. J. Math. 45(3) (2024), 992-1007.   DOI:10.1134/S1995080224600560
  6. Y. Bouhenache, W. Chikouche, I. Touil and S. F. 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(2) (2024), 247-265.   DOI:10.22124/jmm.2024.25394.2257
  7. R. W. Cottle, J.-S. Pang and R. E. Stone: The Linear Complementarity Problem. Academic Press, Boston, MA 1992.   CrossRef
  8. M. El Ghami, I. D. Ivanov and T. Steihaug: Primal-dual interior-point methods solver based on kernel functions for linear optimization. In: Proc. International Multiconference on Computer Science and Information Technology, Mragowo 2009, pp. 743-749.   DOI:10.1109/IMCSIT.2009.5352756
  9. M. C. Ferris and J. S. Pang: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4) (1997), 669-713.   DOI:10.1137/S0036144595285130
  10. S. Guerdouh and W. Chikouche: A primal-dual large-update interior-point algorithm for symmetric cone optimization based on a new class of kernel functions. Palest. J. Math. 13(3) (2024), 320-332.  
  11. S. Guerdouh, W. Chikouche and B. Kheirfam: A full-Newton step infeasible interior-point algorithm based on a kernel function with a new barrier term. J. Appl. Math. Comput. 69 (2023), 2935-2953.   DOI:10.1007/s12190-023-01858-8
  12. 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. Preprint, HAL, 2021.   DOI:halshs-03228790
  13. S. Guerdouh, W. Chikouche and I. Touil: A primal-dual interior-point algorithm based on a kernel function with a new barrier term. Stat. Optim. Inf. Comput. 11 (2023), 773-784.   DOI:10.19139/soic-2310-5070-1381
  14. S. Guerdouh, W. Chikouche, I. Touil and A. Yassine: Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions. Kybernetika 59(6) (2023), 827-860.   DOI:10.14736/kyb-2023-6-0827
  15. C. Kanzow: Some non-interior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17(4) (1996), 851-868.   DOI:10.1137/S0895479894273134
  16. N. K. Karmarkar: A new polynomial-time algorithm for linear programming. In: Proc. 16th Annual ACM Symposium on Theory of Computing 4, 1984, pp. 373-395.   DOI:10.1145/800057.808695
  17. B. Kheirfam: Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer. Algorithms 61 (2012), 659-680.   DOI:10.1007/s11075-012-9557-y
  18. B. Kheirfam: A full-Newton step infeasible interior-point algorithm for linear complementarity problems based on a kernel function. Algorithmic Oper. Res. 7 (2013), 103-110.  
  19. B. Kheirfam and M. Haghighi: An infeasible interior-point method for the $P_*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step. Commun. Comb. Optim. 3(1) (2018), 51-70.   DOI:10.22049/CCO.2018.25801.1038
  20. B. Kheirfam and M. Haghighi: A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function. Optimization 65(4) (2016), 841-857.   DOI:10.1080/02331934.2015.1080255
  21. B. Kheirfam and M. Haghighi: A full-Newton step infeasible interior-point method based on a trigonometric kernel function without centering steps. Numer. Algorithms 85 (2020), 59-75.   DOI:10.1007/s11075-019-00802-x
  22. B. Kheirfam and M. Moslemi: A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term. Yugosl. J. Oper. Res. 25(2) (2015), 233-250.   DOI:10.2298/YJOR120904006K
  23. M. Kojima, N. Megiddo, T. Noma and A. Yoshise: A unified approach to interior-point algorithms for linear complementarity problems. In: Lecture Notes in Computer Science, vol. 538, Springer, Berlin 1991.   DOI:10.1007/3-540-54509-3
  24. M. Kojima, S. Mizuno and A. Yoshise: A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44 (1989), 1-26.   DOI:10.1007/BF01587074
  25. Z. Liu and W. Sun: A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions. Appl. Math. Comput. 217 (2011), 4990-4999.   DOI:10.1016/j.amc.2010.11.049
  26. T. De Luca, F. Facchinei and C. Kanzow: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75 (1996), 407-439.   DOI:10.1007/BF02592192
  27. I. J. Lustig: Feasibility issues in a primal-dual interior-point method for linear programming. Math. Program. 49(1-3) (1990), 145-162.   DOI:10.1007/BF01588785
  28. H. Mansouri and C. Roos: A new full-Newton step infeasible interior-point algorithm for semidefinite optimization. Numer. Algorithms 52(2) (2009), 225-255.   DOI:10.1007/s11075-009-9270-7
  29. H. Mansouri, M. Zangiabadi and M. Pirhaji: A full-Newton step $\mathcal{O}(n)$ infeasible interior-point algorithm for linear complementarity problems. Nonlinear Anal. Real World Appl. 12(1) (2011), 545-561.   DOI:10.1016/j.nonrwa.2010.06.039
  30. M. Moslemi and B. Kheirfam: Complexity analysis of infeasible interior-point method for semidefinite optimization based on a new trigonometric kernel function. Optim. Lett. 13 (2019), 127-145.   DOI:10.1007/s11590-018-1257-7
  31. J. Peng, C. Roos and T. Terlaky: A new class of polynomial primal-dual methods for linear and semidefinite optimization. European J. Oper. Res. 143 (2002), 234-256.   DOI:10.1016/S0377-2217(02)00275-8
  32. M. Pirhaji, M. Zangiabadi and H. Mansouri: An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function. J. Appl. Math. Comput. 54 (2017), 469-483.   DOI:10.1007/s12190-016-1019-6
  33. C. Roos: A full-Newton step $\mathcal{O}(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4) (2006), 1110-1136.   DOI:10.1137/050623917
  34. C. Roos, T. Terlaky and J. Ph. Vial: Theory and Algorithms for Linear Optimization. In: An Interior-Point Approach, John Wiley \& Sons, Chichester 1997.   CrossRef
  35. M. Salahi, M. R. Peyghami and T. Terlaky: New complexity analysis of IIPMs for linear optimization based on a specific self-regular function. Eur. J. Oper. Res. 186(2) (2008), 466-485.   DOI:10.1016/j.ejor.2007.02.008
  36. M. Salahi, T. Terlaky and G. Zhang: The complexity of self-regular proximity based infeasible IPMs. Comput. Optim. Appl. 33 (2006), 157-185.   DOI:10.1007/s10589-005-3064-1
  37. 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), 3957-3969.   DOI:10.2298/FIL2012957T
  38. I. Touil and W. Chikouche: Novel kernel function with a hyperbolic barrier term to primal-dual interior-point algorithm for SDP problems. Acta Math. Appl. Sin. Engl. Ser. 38 (2022), 44-67.   DOI:10.1007/s10255-022-1061-0
  39. I. Touil and W. Chikouche: Polynomial-time algorithm for linear programming based on a kernel function with hyperbolic-logarithmic barrier term. Palest. J. Math. 11(II) (2022), 127-135.  
  40. L. Zhang, Y. Q. Bai and Y. Xu: A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally kernel function. Numer. Algorithms 61 (2012), 57-81.   DOI:10.1007/s11075-011-9530-1