A predictor-corrector interior-point algorithm for $ P_{*}(\kappa) $-weighted linear complementarity problems

Lu Zhang; Xiaoni Chi; Suobin Zhang; Yuping Yang; Lu Zhang; Xiaoni Chi; Suobin Zhang; Yuping Yang

doi:10.3934/math.2023462

AIMS Mathematics

2023, Volume 8, Issue 4: 9212-9229. doi: 10.3934/math.2023462

Previous Article Next Article

Research article

A predictor-corrector interior-point algorithm for $ P_{*}(\kappa) $-weighted linear complementarity problems

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

Received: 25 September 2022 Revised: 18 January 2023 Accepted: 01 February 2023 Published: 13 February 2023
MSC : 90C33, 90C51

In this paper, we present a predictor-corrector interior-point algorithm for $ P_{*}(\kappa) $-weighted linear complementarity problems. Based on the kernel function $ \varphi(t) = \sqrt{t} $, the search direction of the algorithm is obtained. By choosing appropriate parameters, we prove that the algorithm is feasible and convergent. It is shown that the proposed algorithm has polynomial iteration complexity. Numerical results illustrate the effectiveness of the algorithm.
Citation: Lu Zhang, Xiaoni Chi, Suobin Zhang, Yuping Yang. A predictor-corrector interior-point algorithm for $ P_{*}(\kappa) $-weighted linear complementarity problems[J]. AIMS Mathematics, 2023, 8(4): 9212-9229. doi: 10.3934/math.2023462

Related Papers:

Abstract

In this paper, we present a predictor-corrector interior-point algorithm for $ P_{*}(\kappa) $-weighted linear complementarity problems. Based on the kernel function $ \varphi(t) = \sqrt{t} $, the search direction of the algorithm is obtained. By choosing appropriate parameters, we prove that the algorithm is feasible and convergent. It is shown that the proposed algorithm has polynomial iteration complexity. Numerical results illustrate the effectiveness of the algorithm.

References

[1]	R. W. Cottle, J. S. Pang, R. E. Stone, The linear complementarity problem, Academic Press, Boston, 1992. http://dx.doi.org/10.1137/1.9780898719000.bm
[2]	F. A. Potra, Weighted complementarity problems-a new paradigm for computing equilibria, SIAM J. Optim., 22 (2012), 1634–1654. http://dx.doi.org/10.1137/110837310 doi: 10.1137/110837310
[3]	K. Jain, M. Mahdian, Computing equilibria in a Fisher market with linear single-constraint production units, In: Internet and network economics, WINE 2005, Lecture Notes in Computer Science, Vol 3828, Springer, Berlin, Heidelberg 2005. https://dx.doi.org/10.1007/11600930_79
[4]	F. A. Potra, Sufficient weighted complementarity problems, Comput. Optim. Appl., 64 (2016), 467–488. http://dx.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://dx.doi.org/10.1007/s11590-015-0877-4 doi: 10.1007/s11590-015-0877-4
[6]	H. T. Che, A smoothing and regularization predictor-corrector method for nonlinear inequalities, J. Inequal. Appl., 214 (2012), 214. http://dx.doi.org/10.1186/1029-242x-2012-214 doi: 10.1186/1029-242x-2012-214
[7]	J. Y. Tang, A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Comput. Appl. Math., 37 (2018), 3927–3936. http://dx.doi.org/10.1007/s40314-017-0554-6 doi: 10.1007/s40314-017-0554-6
[8]	X. R. He, J. Y. Tang, A smooth Levenberg-Marquardt method without nonsingularity condition for wLCP, AIMS Math., 7 (2022), 8914–8932. http://dx.doi.org/10.3934/math.2022497 doi: 10.3934/math.2022497
[9]	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://dx.doi.org/10.1007/s10898-018-0689-z doi: 10.1007/s10898-018-0689-z
[10]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373–395. http://dx.doi.org/10.1007/BF02579150 doi: 10.1007/BF02579150
[11]	S. Asadi, Z. Darvay, G. Lesaja, N. Mahdavi-Amiri, F. Potra, A full-Newton step interior-point method for monotone weighted linear complementarity problems, J. Optim. Theory Appl., 186 (2020), 864–878. http://dx.doi.org/10.1007/s10957-020-01728-4 doi: 10.1007/s10957-020-01728-4
[12]	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://dx.doi.org/10.1007/s10957-021-01873-4 doi: 10.1007/s10957-021-01873-4
[13]	X. N. Chi, Z. P. Wan, Z. J. Hao, A full-modified-Newton step $O(n)$ infeasible interior-point method for the special weighted linear complementarity problem, J. Ind. Manag. Optim., 18 (2022), 2579–2598. http://dx.doi.org/10.3934/jimo.2021082 doi: 10.3934/jimo.2021082
[14]	Z. Darvay, New interior point algorithms in linear programming, Adv. Model. Optim., 5 (2003), 51–92.
[15]	B. Kheirfam, M. Haghighi, A full-Newton step feasible interior-point algorithm for $P_{}(\kappa)$-LCP based on a new search direction, Croat. Oper. Res. Rev.*, 2 (2016), 277–290. http://dx.doi.org/10.17535/crorr.2016.0019 doi: 10.17535/crorr.2016.0019
[16]	Z. Darvay, T. Ill$\acute{e}$s, B. Kheirfam, P. R. Rig$\acute{o}$, A corrector-predictor interior-point method with new search direction for linear optimization, Cent. Eur. J. Oper. Res., 28 (2020), 1123–1140. http://dx.doi.org/10.1007/s10100-019-00622-3 doi: 10.1007/s10100-019-00622-3
[17]	Z. Darvay, T. Ill$\acute{e}$s, P. R. Rig$\acute{o}$, 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), 25–35. http://dx.doi.org/10.1016/j.ejor.2021.08.039 doi: 10.1016/j.ejor.2021.08.039
[18]	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://dx.doi.org/10.1007/s11075-011-9530-1 doi: 10.1007/s11075-011-9530-1
[19]	H. Mansouri, M. Pirhaji, A polynomial interior-point algorithm for monotone linear complementarity problems, J. Optim. Theory Appl., 157 (2013), 451–461. http://dx.doi.org/10.1007/s10957-012-0195-2 doi: 10.1007/s10957-012-0195-2
[20]	M. Kojima, N. Megiddo, T. Noma, A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems, Springer Berlin, Heidelberg, 1991. https://doi.org/10.1007/3-540-54509-3
[21]	C. Roos, T. Teerlaky, J. P. Vial, Theory and algorithm for linear optimization-an interior point approach, New York: John Wiley and Sons Inc, 1997.
[22]	W. W. Wang, H. M. Bi, H. W. Liu, A full-Newton step interior-point algorithm for linear optimization based on a finite barrier, Oper. Res. Lett., 44 (2016), 750–753. http://dx.doi.org/10.1016/j.orl.2016.09.009 doi: 10.1016/j.orl.2016.09.009
[23]	G. Q. Wang, C. J. Yu, K. L. Teo, A full-Newton step feasible interior-point algorithm for $P_{}(\kappa)$-linear complementarity problems, J. Glob. Optim.*, 59 (2014), 81–99. http://dx.doi.org/10.1007/s10898-013-0090-x doi: 10.1007/s10898-013-0090-x
[24]	B. Kheirfam, A predictor-corrcetor interior-point algorithm for $P_{}(\kappa)$-horizontal linear complementarity problem, Numer. Algor.*, 66 (2014), 349–361. https://dx.doi.org/10.1007/s11075-013-9738-3 doi: 10.1007/s11075-013-9738-3
[25]	W. Hock, K. Shittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, Springer Berlin, Heidelberg, 1981. https://doi.org/10.1007/978-3-642-48320-2
[26]	Y. Fathi, Computational complexity of LCPs associated with positive definite matrices, Math. Program., 17 (1979), 335–344. http://dx.doi.org/10.1007/BF01588254 doi: 10.1007/BF01588254
[27]	L. T. Watson, Solving the nonlinear complementarity problem by a homotopy method, SIAM J. Optim., 17 (1979), 36–46. http://dx.doi.org/10.1137/0317004 doi: 10.1137/0317004

Reader Comments

Your name:*

Email:*
© 2023 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)