Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
linear complementarity problems; infeasible interior-point method; kernel function; polynomial complexity
linear complementarity problems; infeasible interior-point method; kernel function; polynomial complexity
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.
References:
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[7] Cottle, R. W., Pang, J.-S., Stone, R. E.: The Linear Complementarity Problem. Academic Press, Boston, MA 1992.
[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. DOI
[9] Ferris, M. C., Pang, J. S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4) (1997), 669-713. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[15] Kanzow, C.: Some non-interior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17(4) (1996), 851-868. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[24] Kojima, M., Mizuno, S., Yoshise, A.: A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44 (1989), 1-26. DOI
[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. DOI
[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. DOI
[27] Lustig, I. J.: Feasibility issues in a primal-dual interior-point method for linear programming. Math. Program. 49(1-3) (1990), 145-162. DOI
[28] Mansouri, H., Roos, C.: A new full-Newton step infeasible interior-point algorithm for semidefinite optimization. Numer. Algorithms 52(2) (2009), 225-255. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
[34] Roos, C., Terlaky, T., Vial, J. Ph.: Theory and Algorithms for Linear Optimization. In: An Interior-Point Approach, John Wiley & Sons, Chichester 1997.
[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. DOI
[36] Salahi, M., Terlaky, T., Zhang, G.: The complexity of self-regular proximity based infeasible IPMs. Comput. Optim. Appl. 33 (2006), 157-185. DOI
[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. DOI
[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. DOI
[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. DOI
[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. DOI
Search
Partner of
