| Title:
|
An improved descent direction for path-following algorithm in monotone linear complementarity problems (English) |
| Author:
|
Menniche, Linda |
| Author:
|
Zaoui, Billel |
| Author:
|
Benterki, Djamel |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
62 |
| Issue:
|
1 |
| Year:
|
2026 |
| Pages:
|
35-54 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We present a new full-Newton step feasible interior-point method for solving monotone linear complementarity problems. We derive an efficient search direction by applying an algebraic transformation to the central path system. Furthermore, we prove that the proposed method solves the problem within polynomial time. Notably, the algorithm achieves the best-known iteration bound, namely $O(\sqrt{n} \log \frac{n}{\epsilon})$-iterations. Finally, comparative numerical simulations illustrate the effectiveness of the proposed algorithm. (English) |
| Keyword:
|
Interior-point method |
| Keyword:
|
Monotone linear complementarity problem |
| Keyword:
|
Descent direction |
| MSC:
|
65K05 |
| MSC:
|
90C33 |
| MSC:
|
90C51 |
| DOI:
|
10.14736/kyb-2026-1-0035 |
| . |
| Date available:
|
2026-03-03T17:35:48Z |
| Last updated:
|
2026-03-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/153534 |
| . |
| Reference:
|
[1] Achache, M.: A new primal-dual path-following method for convex quadratic programming..Comput. Appl. Math. 25 (2006), 97-110. 10.1590/S0101-82052006000100005 |
| Reference:
|
[2] Cottle, R. W., Pang, J.-S., Stone, R. E.: The linear complementarity problem..SIAM, Philadelphia 2009. |
| Reference:
|
[3] Darvay, Z., Papp, I.-M., Takács, P.-R.: Complexity analysis of a full-Newton step interior-point method for linear optimization..Period. Math. Hung. 73 (2016), 27-42. 10.1007/s10998-016-0119-2 |
| Reference:
|
[4] Darvay, Z.: New interior point algorithms in linear programming..Adv. Model. Optim. 5 (2003), no. 1, 51-92. |
| Reference:
|
[5] Darvay, Z., Takács, P. R.: New method for determining search directions for interior point algorithms in linear optimization..Optim. Lett. 12 (2018), 1099-1116. 10.1007/s11590-017-1171-4 |
| Reference:
|
[6] Darvay, Z., Illés, T., Rigó, P. R.: Predictor-corrector interior-point algorithm for P*($\kappa$)-linear complementarity problems based on a new type of algebraic equivalent transformation technique..Eur. J. Oper. Res. 298 (2022), no. 1, 25-35. 10.1016/j.ejor.2021.08.039 |
| Reference:
|
[7] Grimes, W., Achache, M.: A path-following interior-point algorithm for monotone LCP based on a modified Newton search direction..RAIRO-Oper. Res. 57 (2023), no. 3, 1059-1073. 10.1051/ro/2023054 |
| Reference:
|
[8] Guerra, L.: A class of new search directions for full-NT step feasible interior point method in semidefinite optimization..RAIRO Oper. Res. 56 (2022), no. 6, 3955-3971. 10.1051/ro/2022192 |
| Reference:
|
[9] Kheirfam, B., Haghighi, M.: A full-Newton step feasible interior-point algorithm for $P_{\ast }(\kappa)$-LCP based on a new search direction..Croatian Oper. Res. Rev. 7 (2016), 277-290. 10.17535/crorr.2016.0019 |
| Reference:
|
[10] Kheirfam, B., Nasrollahi, A.: A full-Newton step interior-point method based on a class of specific algebra transformation..Fundam. Inform. 163 (2018), no. 4, 325-337. 10.3233/FI-2018-1747 |
| Reference:
|
[11] Kheirfam, B.: A new search direction for full-Newton step interior-point method in $P_{\ast }(\kappa)$-HLCP..Numer. Funct. Anal. Optim. 40 (2019), no. 10, 1169-1181. 10.1080/01630563.2019.1598430 |
| Reference:
|
[12] Kheirfam, B.: A new search direction for full-Newton step infeasible interior-point method in linear optimization..Croatian Oper. Res. Rev. 14 (2023), no. 2, 193-202. 10.17535/crorr.2023.0016 |
| Reference:
|
[13] Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems..Lecture Notes in Comput. Sci., 538 (1991). 10.1007/3-540-54509-3 |
| Reference:
|
[14] Maros, I., Mészáros, C.: A repository of convex quadratic programming problems..Optim. Methods Softw. 11 (1999), no. 1-4, 671-681. 10.1080/10556789908805768 |
| Reference:
|
[15] Moussaoui, N., Achache, M.: A weighted-path following interior-point algorithm for convex quadratic optimization based on modified search directions..Stat. Optim. Inf. Comput. 10 (2022), no. 3, 873-889. 10.19139/soic-2310-5070-1385 |
| Reference:
|
[16] Roos, C., Terlaky, T., Vial, J. Ph.: Theory and algorithms for linear optimization, an interior point approach..Wiley, Chichester, 1997. |
| Reference:
|
[17] Wang, G.Q., Bai, Y.Q.: A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step..Appl. Math. Comput. 215 (2009), no. 3, 1047-1061. |
| Reference:
|
[18] Wang, G.Q., Bai, Y.Q.: A new primal-dual path-following interior-point algorithm for semidefinite optimization..J. Math. Anal. Appl. 353 (2009), no. 1, 339-349. 10.1016/j.jmaa.2008.12.016 |
| Reference:
|
[19] Wang, G.Q., Bai, Y.Q.: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization..J. Optim. Theory Appl. 154 (2012), 966-985. 10.1007/s10957-012-0013-x |
| Reference:
|
[20] Wang, G.Q., Fan, X.J., Zhu, D.T., Wang, D.Z.: New complexity analysis of a full-Newton step feasible interior-point algorithm for $P_*(\kappa)$-LCP..Optim. Lett. 9 (2015), 1105-1119. 10.1007/s11590-014-0800-4 |
| Reference:
|
[21] Wright, S.J.: Primal-dual interior point methods..SIAM, Philadelphia, 1997. |
| Reference:
|
[22] Zaoui, B., Benterki, D., Kraria, A., Raouache, H.: Interior-point algorithm for linear programming based on a new descent direction..RAIRO-Oper. Res. 57 (2023), no. 5, 2473-2491. 10.1051/ro/2023127 |
| Reference:
|
[23] Zaoui, B., Benterki, D., Khelladi, S.: New efficient descent direction of a primal-dual path-following algorithm for linear programming..Stat. Optim. Inf. Comput. 12 (2024), no. 4, 1076-1090. 10.19139/soic-2310-5070-1748 |
| Reference:
|
[24] Zaoui, B., Benterki, D., Yassine, A.: An efficient primal-dual interior point algorithm for convex quadratic semidefinite optimization..J. Appl. Math. Comput. 70 (2024), no. 3, 2129-2148. 10.1007/s12190-024-02041-3 |
| . |
