A Feasible Predictor-Corrector Interior-Point Method for Monotone Weighted Linear Complementarity Problems

Articles in Press

Document Type : Original paper

Authors

1 Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

2 Center for Mathematical and Theoretical Physical Sciences PRISM, MSU-Iligan Institute of Technology, Iligan City, Philippines

Abstract

This work presents a predictor-corrector interior-point algorithm for solving the weighted linear complementarity problem. By applying Newton's type method to the central path system, the search directions are obtained. The algorithm works in the $\tau$-neighborhood, which measures the proximity of iterates to the central path. By suitable choice of parameters, the global convergence of the method under mild conditions is guaranteed. The iteration bound derived  to find   $\varepsilon$-approximate  solution  matches the best known iteration bound for these types of problems. To the best of our knowledge, this is the first work based on these types of search directions.

Keywords

Main Subjects

References

[1] M. Achache, A new primal-dual path-following method for convex quadratic programming, Comput. Appl. Math. 25 (2006), no. 1, 97–110. https://doi.org/10.1590/S0101-82052006000100005
[2] K.M. Anstreicher, Interior-point algorithms for a generalization of linear programming and weighted centering, Optim. Methods Soft. 27 (2012), no. 4-5, 605–612. https://doi.org/10.1080/10556788.2011.644791
[3] S. Asadi, Z. Darvay, G. Lesaja, N. Mahdavi-Amiri, and F.A. Potra, A full-Newton step interior-point method for monotone weighted linear complementarity problems, J. Optim. Theory Appl. 186, no. 3, 864–878. https://doi.org/10.1007/s10957-020-01728-4
[4] R.W. Cottle, J.S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, CA, 1992.
[5] Z. Darvay, New interior-point algorithm in linear programming, Adv. Model. Optim. 5 (2003), 51–92.
[6] Z. Darvay, T. Illés, B. Kheirfam, and P.R. Rigó, A corrector-predictor interior-point method with new search direction for linear optimization, Cent. Euro. J. Oper. Res. 28 (2020), no. 3, 1123–1140. https://doi.org/10.1007/s10100-019-00622-3
[7] Z. Darvay, T. Illés, J. Povh, and P.R. Rigó, Feasible corrector-predictor interior-point algorithm for $p∗(\kappa)$-linear complementarity problems based on a new search direction, SIAM J. Optim. 30 (2020), no. 3, 2628–2658. https://doi.org/10.1137/19M1248972
[8] 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, Euro. J. Oper. Res. 298 (2022), no. 7, 25–35. https://doi.org/10.1016/j.ejor.2021.08.039
[9] B. Kheirfam, A corrector-predictor path-following algorithm for semidefinite optimization, Asian-Eur. J. Math. 7 (2014), no. 2, 1450028. https://doi.org/10.1142/S1793557114500284
[10] B. Kheirfam, A predictor-corrector interior-point algorithm for $P∗(\kappa)$ horizontal linear complementarity problem, Numer. Algorithms 66 (2014), no. 2, 349–361. https://doi.org/10.1007/s11075-013-9738-3
[11] B. Kheirfam, A corrector-predictor path-following method for convex quadratic symmetric cone optimization, J. Optim. Theory Appl. 164 (2015), no. 1, 246–260. https://doi.org/10.1007/s10957-014-0554-2
[12] B. Kheirfam, Complexity analysis of a full-Newton step interior-point method for monotone weighted linear complementarity problems, J. Optim. Theory Appl. 202 (2024), no. 1, 133–145. https://doi.org/10.1007/s10957-022-02139-3
[13] K.A. McShane, Superlinearly convergent o(√nl)-iteration interior-point algorithms for linear programming and the monotone linear complementarity problem, SIAM J. Optim. 4 (1994), no. 2, 247–261. https://doi.org/10.1137/0804014
[14] S. Mizuno, M.J. Todd, and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res. 18, no. 4. 964–981. https://doi.org/10.1287/moor.18.4.964
[15] F.A. Potra, Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path, Math. Program. 111 (2008), 243–272. https://doi.org/10.1007/s10107-006-0068-2
[16] F.A. Potra, Weighted complementarity problems- a new paradigm for computing equilibria, SIAM J. Optim. 22 (2012), no. 4, 1634–1654. https://doi.org/10.1137/110837310
[17] F.A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl. 64 (2016), no. 2, 467–488. https://doi.org/10.1007/s10589-015-9811-z
[18] F.A. Potra and X. Liu, Predictor-corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path, Optim. Methods Softw. 20 (2005), no. 1, 145–168. https://doi.org/10.1080/10556780512331318038
[19] C. Roos, T. Terlaky, and J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, UK, 1997.
[20] J.Y. Tang and J.C. Zhou, A modified damped Gauss-Newton method for non-monotone weighted linear complementarity problems, Optim. Methods Softw. 37 (2022), no. 3, 1145–1164. https://doi.org/10.1080/10556788.2021.1903007
[21] 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. https://doi.org/10.1016/j.amc.2009.06.034
[22] 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. https://doi.org/10.1007/s10957-012-0013-x
[23] G.Q. Wang, C.J. Yu, and K.L. Teo, A full-Newton step feasible interior-point algorithm for $P∗(\kappa)$-linear complementarity problems, J. Glob. Optim. 59 (2014), no. 1, 81–99. https://doi.org/10.1007/s10898-013-0090-x
[24] Y. Ye, A fully polynomial-time approximation algorithm for computing a stationary point of the general linear complementarity problem, Math. Oper. Res. 18 (1993), no. 2, 334–345.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 17 March 2026

Files

Share

How to cite

Statistics