Complexity of a predictor-corrector interior-point method using special kernel function for sufficient WLCPs

Zhuoran Gao; Hongjin Wei; Suobin Zhang; Xiaoni Chi; Zhuoran Gao; Hongjin Wei; Suobin Zhang; Xiaoni Chi

doi:10.3934/math.2026912

AIMS Mathematics

2026, Volume 11, Issue 7: 22576-22597. doi: 10.3934/math.2026912

Previous Article Next Article

Research article

Complexity of a predictor-corrector interior-point method using special kernel function for sufficient WLCPs

1.
School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China
2.
Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004, China
3.
Center for Applied Mathematics of Guangxi (GUET), Guilin 541004, China
4.
School of Mathematics and Computer Engineering, Guangxi Science and Technology Normal University, Laibin Guangxi 546199, China
5.
Institute of Scientific Research and Development, Guilin University of Electronic Technology, Guilin 541004, China

Received: 11 May 2026 Revised: 07 July 2026 Accepted: 16 July 2026 Published: 27 July 2026
MSC : 90C33, 90C51

A predictor-corrector interior-point method (PC IPM) is developed in this paper to address sufficient weighted linear complementarity problems (WLCPs). Specifically, the analysis is conducted by choosing the parameters of the kernel function $ \varphi \left(t\right) = \frac{{t}^{\mathfrak{p}+1}-1}{\mathfrak{p}+1}+\frac{{t}^{1-\mathfrak{q}}-1}{\mathfrak{q}-1} $ to $ \mathfrak{p} = 1 $ and $ \mathfrak{q} = 3 $. Each iteration of the algorithm performs two steps: a predictor step followed by a corrector step. Furthermore, with appropriate parameter selections, we prove that the proposed method remains strictly feasible and converges. A polynomial complexity bound is derived, which is comparable to the best-known iteration bound reported in the literature on PC IPMs for solving sufficient WLCPs. Additionally, preliminary numerical experiments indicate that the proposed algorithm performs effectively.
- predictor-corrector interior-point method,
- sufficient weighted linear complementarity problem,
- full-Newton step,
- proximity measure,
- kernel function
Citation: Zhuoran Gao, Hongjin Wei, Suobin Zhang, Xiaoni Chi. Complexity of a predictor-corrector interior-point method using special kernel function for sufficient WLCPs[J]. AIMS Mathematics, 2026, 11(7): 22576-22597. doi: 10.3934/math.2026912

Related Papers:

Abstract

A predictor-corrector interior-point method (PC IPM) is developed in this paper to address sufficient weighted linear complementarity problems (WLCPs). Specifically, the analysis is conducted by choosing the parameters of the kernel function $ \varphi \left(t\right) = \frac{{t}^{\mathfrak{p}+1}-1}{\mathfrak{p}+1}+\frac{{t}^{1-\mathfrak{q}}-1}{\mathfrak{q}-1} $ to $ \mathfrak{p} = 1 $ and $ \mathfrak{q} = 3 $. Each iteration of the algorithm performs two steps: a predictor step followed by a corrector step. Furthermore, with appropriate parameter selections, we prove that the proposed method remains strictly feasible and converges. A polynomial complexity bound is derived, which is comparable to the best-known iteration bound reported in the literature on PC IPMs for solving sufficient WLCPs. Additionally, preliminary numerical experiments indicate that the proposed algorithm performs effectively.

References

[1]	F. A. Potra, Weighted complementarity problems-a new paradigm for computing equilibria, SIAM J. Optim., 22 (2012), 1634–1654. http://doi.org/10.1137/110837310 doi: 10.1137/110837310
[2]	J. Y. Tang, A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Comput. Appl. Math., 37 (2018), 3927–3936. http://doi.org/10.1007/s40314-017-0554-6 doi: 10.1007/s40314-017-0554-6
[3]	X. N. Chi, M. S. Gowda, J. Y. Tao, The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, J. Glob. Optim., 73 (2019), 153–169. http://doi.org/10.1007/s10898-018-0689-z doi: 10.1007/s10898-018-0689-z
[4]	F. A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl., 64 (2016), 467–488. http://doi.org/10.1007/s10589-015-9811-z doi: 10.1007/s10589-015-9811-z
[5]	J. Zhang, A smoothing Newton algorithm for weighted linear complementarity problem, Optim. Lett., 10 (2016), 499–509. http://doi.org/10.1007/s11590-015-0877-4 doi: 10.1007/s11590-015-0877-4
[6]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373–395. http://doi.org/10.1007/BF02579150 doi: 10.1007/BF02579150
[7]	S. Asadi, Z. Darvay, G. Lesaja, N. Mahdavi-Amiri, F. A. Potra, A full-Newton step interior-point method for monotone weighted linear complementarity problems, J. Optim. Theory Appl., 186 (2020), 864–878. http://doi.org/10.1007/s10957-020-01728-4 doi: 10.1007/s10957-020-01728-4
[8]	X. N. Chi, Z. P. Wan, Z. J. Hao, A full-modified-Newton step $\mathcal{O}(n)$ infeasible interior-point method for the special weighted linear complementarity problem, J. Ind. Manag. Optim., 18 (2022), 2579–2598. http://doi.org/10.3934/jimo.2021082 doi: 10.3934/jimo.2021082
[9]	X. N. Chi, G. Q. Wang, A full-Newton step infeasible interior-point method for the special weighted linear complementarity problem, J. Optim. Theory Appl., 190 (2021), 108–129. http://doi.org/10.1007/s10957-021-01873-4 doi: 10.1007/s10957-021-01873-4
[10]	S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J Optim., 2 (1992), 575–601. http://doi.org/10.1137/0802028 doi: 10.1137/0802028
[11]	G. Sonnevend, J. Stoer, G. Zhao, On the complexity of following the central path of linear programs by linear extrapolation Ⅱ, Math. Program., 52 (1991), 527–553. http://doi.org/10.1007/BF01582904 doi: 10.1007/BF01582904
[12]	S. Mizuno, M. J. Todd, Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18 (1993), 964–981. http://doi.org/10.1287/moor.18.4.964 doi: 10.1287/moor.18.4.964
[13]	F. A. Potra, R. Sheng, Predictor-corrector algorithm for solving $ P_{\ast}(\kappa) $-matrix LCP from arbitrary positive starting points, Math. Program., 76 (1996), 223–244. http://doi.org/10.1007/bf02614385 doi: 10.1007/bf02614385
[14]	Z. Darvay, A predictor-corrector algorithm for linearly constrained convex optimization, Stud. univ. babes-Bolyai Inform., 54 (2009), 121–138.
[15]	B. Kheirfam, A corrector-predictor path-following method for Convex quadratic symmetric cone optimization, J. Optim. Theory Appl., 164 (2015), 246–260. https://doi.org/10.1007/s10957-014-0554-2 doi: 10.1007/s10957-014-0554-2
[16]	B. Kheirfam, A corrector-predictor path-following method for second-order cone optimization, Int. J. Comput. Math., 93 (2016), 2064–2078. https://doi.org/10.1080/00207160.2015.1085028 doi: 10.1080/00207160.2015.1085028
[17]	L. Zhang, X. N. Chi, S. B. Zhang, Y. P. Yang, A predictor-corrector interior-point algorithm for $ P_{\ast}(\kappa) $-weighted linear complementarity problems, AIMS Math., 8 (2023), 2064–2078. http://doi.org/10.3934/math.2023462 doi: 10.3934/math.2023462
[18]	F. A. Potra, Y. Y. Ye, Interior-point methods for nonlinear complementarity problems, J. Optim. Theory Appl., 88 (1996), 617–647. http://doi.org/10.1007/BF02192201 doi: 10.1007/BF02192201
[19]	X. R. He, J. Y. Tang, A smooth Levenberg-Marquardt method without nonsingularity condition for wLCP, AIMS Math., 7 (2022), 8914–8932. http://doi.org/10.3934/math.2022497 doi: 10.3934/math.2022497
[20]	Z. Darvay, New interior point algorithms in linear programming, Adv. Model. Optim., 5 (2003), 51–92.
[21]	M. Achache, A new primal-dual path-following method for convex quadratic programming, Comput. Appl. Math., 25 (2006), 97–110. http://doi.org/10.1590/S0101-82052006000100005 doi: 10.1590/S0101-82052006000100005
[22]	G. Q. Wang, A new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones with full NT-steps, Asia-Pacific J. Oper. Res., 29 (2012), 1250015. http://doi.org/10.1142/S0217595912500157 doi: 10.1142/S0217595912500157
[23]	L. P. Zhang, Y. Q. Bai, Y. H. Xu, A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function, Numer. Algor., 61 (2012), 57–81. http://doi.org/10.1007/s11075-011-9530-1 doi: 10.1007/s11075-011-9530-1
[24]	H. Mansouri, M. Pirhaji, A polynomial interior-point algorithm for monotone linear complementarity problems, J. Optim. Theory Appl., 157 (2013), 451–461. http://doi.org/10.1007/s10957-012-0195-2 doi: 10.1007/s10957-012-0195-2
[25]	G. Lesaja, C. Roos, Unified analysis of Kernel-based interior-point methods for ${P}_(\kappa)$-linear complementary problems, SIAM J Optim.*, 20 (2010), 3014–3039. https://doi.org/10.1137/090766735 doi: 10.1137/090766735
[26]	M. Kojima, N. Megiddo, T. Noma, A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems, Oper. Res. Lett., 10 (1991), 247–254. https://doi.org/10.1007/3-540-54509-3 doi: 10.1007/3-540-54509-3
[27]	H. Väliaho, Criteria for sufficient matrices, Linear Algebra Appl., 233 (1996), 109–129. http://doi.org/10.1016/0024-3795(94)00058-1 doi: 10.1016/0024-3795(94)00058-1
[28]	X. N. Chi, L. Gan, Z. R. Gao, J-S Chen, A feasible interior-point method with full-Newton step for $P_{\ast}(\kappa) $-weighted linear complementarity problem via the algebraically equivalent transformation, Appl. Numer. Math., 220 (2026), 144–166. http://doi.org/10.1016/j.apnum.2025.10.003 doi: 10.1016/j.apnum.2025.10.003
[29]	C. Roos, T. Terlaky, J. P. Vial, Theory and Algorithm for Linear Optimization–An Interior Point Approach, New York: John Wiley and Sons Inc, 1997.
[30]	W. Hock, K. Shittkowski, Test examples for nonlinear programming codes, J. Optim. Theory Appl., 30 (1980), 127–129. https://doi.org/10.1007/BF00934594 doi: 10.1007/BF00934594

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)