| Title:
|
An infeasible interior-point algorithm for monotone linear complementarity problems based on a finite hyperbolic kernel function (English) |
| Author:
|
Guerdouh, Safa |
| Author:
|
Chikouche, Wided |
| Author:
|
Kheirfam, Behrouz |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
62 |
| Issue:
|
1 |
| Year:
|
2026 |
| Pages:
|
55-76 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
linear complementarity problems |
| Keyword:
|
infeasible interior-point method |
| Keyword:
|
kernel function |
| Keyword:
|
polynomial complexity |
| MSC:
|
90C33 |
| MSC:
|
90C51 |
| DOI:
|
10.14736/kyb-2026-1-0055 |
| . |
| Date available:
|
2026-03-03T19:38:02Z |
| Last updated:
|
2026-03-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/153535 |
| . |
| Reference:
|
[1] Amini, K., Peyghami, M. R.: An interior-point method for linear programming based on a class of kernel functions..Bull. Austral. Math. Soc. 71 (2005), 139-153. |
| Reference:
|
[2] Bai, Y. Q., Ghami, M. El, Roos, C.: A new efficient large-update primal-dual interior-point method based on a finite barrier..SIAM J. Optim. 13 (2002), 766-782. |
| Reference:
|
[3] Bai, Y.Q., Ghami, M. El, Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization..SIAM J. Optim. 15 (2004), 101-128. |
| Reference:
|
[4] Bouhenache, Y., Chikouche, W., Guerdouh, S.: An interior-point algorithm for LCP based on a parameterized hyperbolic kernel function..Comput. Math. Math. Phys. 65 (2025), 1181-1194. |
| Reference:
|
[5] Bouhenache, Y., Chikouche, W., Touil, I.: 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. |
| Reference:
|
[6] Bouhenache, Y., Chikouche, W., Touil, I., Hafshejani, S. F.: 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. |
| Reference:
|
[7] Cottle, R. W., Pang, J.-S., Stone, R. E.: The Linear Complementarity Problem..Academic Press, Boston, MA 1992. |
| Reference:
|
[8] Ghami, M. El, Ivanov, I. D., Steihaug, T.: 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. |
| Reference:
|
[9] Ferris, M. C., Pang, J. S.: Engineering and economic applications of complementarity problems..SIAM Rev. 39(4) (1997), 669-713. |
| Reference:
|
[10] Guerdouh, S., Chikouche, W.: 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. |
| Reference:
|
[11] Guerdouh, S., Chikouche, W., Kheirfam, B.: 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. |
| Reference:
|
[12] 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..Preprint, HAL, 2021. |
| Reference:
|
[13] Guerdouh, S., Chikouche, W., Touil, I.: A primal-dual interior-point algorithm based on a kernel function with a new barrier term..Stat. Optim. Inf. Comput. 11 (2023), 773-784. |
| Reference:
|
[14] Guerdouh, S., Chikouche, W., Touil, I., Yassine, A.: Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions..Kybernetika 59(6) (2023), 827-860. |
| Reference:
|
[15] Kanzow, C.: Some non-interior continuation methods for linear complementarity problems..SIAM J. Matrix Anal. Appl. 17(4) (1996), 851-868. |
| Reference:
|
[16] Karmarkar, N. K.: A new polynomial-time algorithm for linear programming..In: Proc. 16th Annual ACM Symposium on Theory of Computing 4, 1984, pp. 373-395. |
| Reference:
|
[17] Kheirfam, B.: Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term..Numer. Algorithms 61 (2012), 659-680. |
| Reference:
|
[18] Kheirfam, B.: A full-Newton step infeasible interior-point algorithm for linear complementarity problems based on a kernel function..Algorithmic Oper. Res. 7 (2013), 103-110. |
| Reference:
|
[19] Kheirfam, B., Haghighi, M.: 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. |
| Reference:
|
[20] Kheirfam, B., Haghighi, M.: A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function..Optimization 65(4) (2016), 841-857. |
| Reference:
|
[21] Kheirfam, B., Haghighi, M.: A full-Newton step infeasible interior-point method based on a trigonometric kernel function without centering steps..Numer. Algorithms 85 (2020), 59-75. |
| Reference:
|
[22] Kheirfam, B., Moslemi, M.: 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. |
| Reference:
|
[23] Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior-point algorithms for linear complementarity problems..In: Lecture Notes in Computer Science, vol. 538, Springer, Berlin 1991. |
| Reference:
|
[24] Kojima, M., Mizuno, S., Yoshise, A.: A polynomial-time algorithm for a class of linear complementarity problems..Math. Program. 44 (1989), 1-26. |
| Reference:
|
[25] Liu, Z., Sun, W.: A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions..Appl. Math. Comput. 217 (2011), 4990-4999. |
| Reference:
|
[26] Luca, T. De, Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems..Math. Program. 75 (1996), 407-439. |
| Reference:
|
[27] Lustig, I. J.: Feasibility issues in a primal-dual interior-point method for linear programming..Math. Program. 49(1-3) (1990), 145-162. |
| Reference:
|
[28] Mansouri, H., Roos, C.: A new full-Newton step infeasible interior-point algorithm for semidefinite optimization..Numer. Algorithms 52(2) (2009), 225-255. |
| Reference:
|
[29] Mansouri, H., Zangiabadi, M., Pirhaji, M.: 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. |
| Reference:
|
[30] Moslemi, M., Kheirfam, B.: Complexity analysis of infeasible interior-point method for semidefinite optimization based on a new trigonometric kernel function..Optim. Lett. 13 (2019), 127-145. |
| Reference:
|
[31] Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization..European J. Oper. Res. 143 (2002), 234-256. |
| Reference:
|
[32] Pirhaji, M., Zangiabadi, M., Mansouri, H.: An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function..J. Appl. Math. Comput. 54 (2017), 469-483. |
| Reference:
|
[33] Roos, C.: A full-Newton step $\mathcal{O}(n)$ infeasible interior-point algorithm for linear optimization..SIAM J. Optim. 16(4) (2006), 1110-1136. |
| Reference:
|
[34] Roos, C., Terlaky, T., Vial, J. Ph.: Theory and Algorithms for Linear Optimization..In: An Interior-Point Approach, John Wiley & Sons, Chichester 1997. |
| Reference:
|
[35] Salahi, M., Peyghami, M. R., Terlaky, T.: New complexity analysis of IIPMs for linear optimization based on a specific self-regular function..Eur. J. Oper. Res. 186(2) (2008), 466-485. |
| Reference:
|
[36] Salahi, M., Terlaky, T., Zhang, G.: The complexity of self-regular proximity based infeasible IPMs..Comput. Optim. Appl. 33 (2006), 157-185. |
| Reference:
|
[37] Touil, I., Chikouche, W.: Primal-dual interior-point methods for semidefinite programming based on a new type of kernel functions..Filomat 34(12) (2020), 3957-3969. |
| Reference:
|
[38] Touil, I., Chikouche, W.: 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. |
| Reference:
|
[39] Touil, I., Chikouche, W.: Polynomial-time algorithm for linear programming based on a kernel function with hyperbolic-logarithmic barrier term..Palest. J. Math. 11(II) (2022), 127-135. |
| Reference:
|
[40] Zhang, L., Bai, Y. Q., Xu, Y.: A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally kernel function..Numer. Algorithms 61 (2012), 57-81. |
| . |
