Kybernetika 62 no. 1, 35-54, 2026

An improved descent direction for path-following algorithm in monotone linear complementarity problems

Linda Menniche, Billel Zaoui and Djamel BenterkiDOI: 10.14736/kyb-2026-1-0035

Abstract:

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.

Keywords:

Interior-point method, Monotone linear complementarity problem, Descent direction

Classification:

90C51, 90C33, 65K05

paper.pdf

References:

  1. M. Achache: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006), 97-110.   CrossRef
  2. R. W. Cottle, J.-S. Pang and R. E. Stone: The linear complementarity problem. SIAM, Philadelphia 2009.   CrossRef
  3. Z. Darvay, I.-M. Papp and P.-R. Takács: Complexity analysis of a full-Newton step interior-point method for linear optimization. Period. Math. Hung. 73 (2016), 27-42.   CrossRef
  4. Z. Darvay: New interior point algorithms in linear programming. Adv. Model. Optim. 5 (2003), no. 1, 51-92.   CrossRef
  5. Z. Darvay and P. R. Takács: New method for determining search directions for interior point algorithms in linear optimization. Optim. Lett. 12 (2018), 1099-1116.   CrossRef
  6. Z. Darvay, T. Illés and P. R. Rigó: 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.   CrossRef
  7. W. Grimes and M. Achache: 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.   CrossRef
  8. L. Guerra: 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.   CrossRef
  9. B. Kheirfam and M. Haghighi: 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.   CrossRef
  10. B. Kheirfam and A. Nasrollahi: A full-Newton step interior-point method based on a class of specific algebra transformation. Fundam. Inform. 163 (2018), no. 4, 325-337.   CrossRef
  11. B. Kheirfam: 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.   CrossRef
  12. B. Kheirfam: 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.   CrossRef
  13. M. Kojima, N. Megiddo, T. Noma and A. Yoshise: A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in Comput. Sci., 538 (1991).   CrossRef
  14. I. Maros and C. Mészáros: A repository of convex quadratic programming problems. Optim. Methods Softw. 11 (1999), no. 1-4, 671-681.   CrossRef
  15. N. Moussaoui and M. Achache: 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.   CrossRef
  16. C. Roos, T. Terlaky and J. Ph. Vial: Theory and algorithms for linear optimization, an interior point approach. Wiley, Chichester, 1997.   CrossRef
  17. G.Q. Wang and Y.Q. Bai: 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.   CrossRef
  18. G.Q. Wang and Y.Q. Bai: A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353 (2009), no. 1, 339-349.   CrossRef
  19. G.Q. Wang and Y.Q. Bai: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154 (2012), 966-985.   CrossRef
  20. G.Q. Wang, X.J. Fan, D.T. Zhu and D.Z. Wang: New complexity analysis of a full-Newton step feasible interior-point algorithm for $P_*(\kappa)$-LCP. Optim. Lett. 9 (2015), 1105-1119.   CrossRef
  21. S.J. Wright: Primal-dual interior point methods. SIAM, Philadelphia, 1997.   CrossRef
  22. B. Zaoui, D. Benterki, A. Kraria and H. Raouache: Interior-point algorithm for linear programming based on a new descent direction. RAIRO-Oper. Res. 57 (2023), no. 5, 2473-2491.   CrossRef
  23. B. Zaoui, D. Benterki and S. Khelladi: New efficient descent direction of a primal-dual path-following algorithm for linear programming. Stat. Optim. Inf. Comput. 12 (2024), no. 4, 1076-1090.   CrossRef
  24. B. Zaoui, D. Benterki and A. Yassine: An efficient primal-dual interior point algorithm for convex quadratic semidefinite optimization. J. Appl. Math. Comput. 70 (2024), no. 3, 2129-2148.   CrossRef