Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
Interior-point method; Monotone linear complementarity problem; Descent direction
Interior-point method; Monotone linear complementarity problem; Descent direction
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.
References:
[1] Achache, M.: A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006), 97-110. DOI 10.1590/S0101-82052006000100005
[2] Cottle, R. W., Pang, J.-S., Stone, R. E.: The linear complementarity problem. SIAM, Philadelphia 2009.
[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. DOI 10.1007/s10998-016-0119-2
[4] Darvay, Z.: New interior point algorithms in linear programming. Adv. Model. Optim. 5 (2003), no. 1, 51-92.
[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. DOI 10.1007/s11590-017-1171-4
[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. DOI 10.1016/j.ejor.2021.08.039
[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. DOI 10.1051/ro/2023054
[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. DOI 10.1051/ro/2022192
[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. DOI 10.17535/crorr.2016.0019
[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. DOI 10.3233/FI-2018-1747
[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. DOI 10.1080/01630563.2019.1598430
[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. DOI 10.17535/crorr.2023.0016
[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). DOI 10.1007/3-540-54509-3
[14] Maros, I., Mészáros, C.: A repository of convex quadratic programming problems. Optim. Methods Softw. 11 (1999), no. 1-4, 671-681. DOI 10.1080/10556789908805768
[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. DOI 10.19139/soic-2310-5070-1385
[16] Roos, C., Terlaky, T., Vial, J. Ph.: Theory and algorithms for linear optimization, an interior point approach. Wiley, Chichester, 1997.
[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.
[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. DOI 10.1016/j.jmaa.2008.12.016
[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. DOI 10.1007/s10957-012-0013-x
[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. DOI 10.1007/s11590-014-0800-4
[21] Wright, S.J.: Primal-dual interior point methods. SIAM, Philadelphia, 1997.
[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. DOI 10.1051/ro/2023127
[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. DOI 10.19139/soic-2310-5070-1748
[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. DOI 10.1007/s12190-024-02041-3
Search
Partner of
