A neural network for a generalized vertical complementarity problem

Bin Hou; Jie Zhang; Chen Qiu; Bin Hou; Jie Zhang; Chen Qiu

doi:10.3934/math.2022371

AIMS Mathematics

2022, Volume 7, Issue 4: 6650-6668. doi: 10.3934/math.2022371

Previous Article Next Article

Research article

A neural network for a generalized vertical complementarity problem

School of Mathematics, Liaoning Normal University, Dalian 116029, China

Received: 25 October 2021 Revised: 06 December 2021 Accepted: 06 January 2022 Published: 24 January 2022
MSC : 90C30

In this paper, an efficient artificial neural network is proposed for solving a generalized vertical complementarity problem. Based on the properties of log-exponential function, the generalized vertical complementarity problem is reformulated in terms of the unconstrained minimization problem. The existence and the convergence of the trajectory of the neural network are addressed in detail. In addition, it is also proved that if the neural network problem has an equilibrium point under some initial condition, the equilibrium point is asymptotically stable or exponentially stable under certain conditions. At the end of this paper, the simulation results for the generalized bimatrix game are illustrated to show the efficiency of the neural network.
- neural network,
- generalized vertical complementarity problem,
- stability,
- log-exponential function,
- consistency
Citation: Bin Hou, Jie Zhang, Chen Qiu. A neural network for a generalized vertical complementarity problem[J]. AIMS Mathematics, 2022, 7(4): 6650-6668. doi: 10.3934/math.2022371

Related Papers:

Abstract

In this paper, an efficient artificial neural network is proposed for solving a generalized vertical complementarity problem. Based on the properties of log-exponential function, the generalized vertical complementarity problem is reformulated in terms of the unconstrained minimization problem. The existence and the convergence of the trajectory of the neural network are addressed in detail. In addition, it is also proved that if the neural network problem has an equilibrium point under some initial condition, the equilibrium point is asymptotically stable or exponentially stable under certain conditions. At the end of this paper, the simulation results for the generalized bimatrix game are illustrated to show the efficiency of the neural network.

References

[1]	R. Cottle, G. Dantzig, A generalization of the linear complementarity problem, J. Comb. Theory, 8 (1970), 79–90. http://dx.doi.org/10.1016/S0021-9800(70)80010-2 doi: 10.1016/S0021-9800(70)80010-2
[2]	L. Zhang, Z. Gao, Global linear and quadratic one-step smoothing Newton method for vertical linear complementarity problems, Appl. Math. Mech., 24 (2003), 738–746. http://dx.doi.org/10.1007/BF02437876 doi: 10.1007/BF02437876
[3]	H. Qi, L. Liao, A smoothing Newton method for extended vertical linear complementarity problems, SIAM J. Matrix Anal. Appl., 21 (1999), 45–66. http://dx.doi.org/10.1137/S0895479897329837 doi: 10.1137/S0895479897329837
[4]	J. Peng, Z. Lin, A non-interior continuation method for generalized linear complementarity problems, Math. Program., 86 (1999), 533–563. http://dx.doi.org/10.1007/s101070050104 doi: 10.1007/s101070050104
[5]	S. C. Fang, J. Han, Z. H. Huang, S. Birbil, On the finite termination of an entropy function based non-interior continuation method for vertical linear complementarity problems, J. Glob. Optim., 33 (2005), 369–391. http://dx.doi.org/10.1007/s10898-004-6098-5 doi: 10.1007/s10898-004-6098-5
[6]	F. Mezzadri, E. Galligani, Projected splitting methods for vertical linear complementarity problems, J. Optim. Theory Appl., in press. http://dx.doi.org/10.1007/s10957-021-01922-y
[7]	A. Ebiefung, Nonlinear mappings associated with the generalized linear complementarity problem, Math. Program., 69 (1995), 255–268. http://dx.doi.org/10.1007/BF01585560 doi: 10.1007/BF01585560
[8]	S. Mohan, S. Neogy, R. Sridhar, The generalized linear complementarity problem revisited, Math. Program., 74 (1996), 197. http://dx.doi.org/10.1007/BF02592211 doi: 10.1007/BF02592211
[9]	S. Mohan, S. Neogy, Algorithms for the generalized linear complementarity problem with a vertical block z-matrix, SIAM J. Optim., 6 (1996), 994–1006. http://dx.doi.org/10.1137/S1052623494275586 doi: 10.1137/S1052623494275586
[10]	S. Mohan, S. Neogy, Vertical block hidden Z-matrices and the generalized linear complementarity problem, SIAM J. Matrix Anal. Appl., 18 (1997), 181–190. http://dx.doi.org/10.1137/S0895479894271147 doi: 10.1137/S0895479894271147
[11]	A. Ebiefung, Existence theory and Q-matrix characterization for the generalized linear complementarity problem, Linear Algebra Appl., 223 (1995), 155–169. http://dx.doi.org/10.1016/0024-3795(95)00091-5 doi: 10.1016/0024-3795(95)00091-5
[12]	A. Ebiefung, G. Habetler, M. Kostreva, B. Szanc, A direct algorithm for the vertical generalized complementarity problem associated with P-matrices, Open Journal of Optimization, 6 (2017), 101–114. http://dx.doi.org/10.4236/ojop.2017.63008 doi: 10.4236/ojop.2017.63008
[13]	G. Habetler, B. Szanc, Existence and uniqueness of solutions for the generalized linear complementarity problem, J. Optim. Theory Appl., 84 (1995), 103–116. http://dx.doi.org/10.1007/BF02191738 doi: 10.1007/BF02191738
[14]	A. Ebiefung, M. Kostreva, V. Ramanujam, An algorithm to solve the generalized linear complementarity problem with a vertical block Z-matrix, Optim. Method. Softw., 7 (1997), 123–138. http://dx.doi.org/10.1080/10556789708805648 doi: 10.1080/10556789708805648
[15]	F. Mezzadri, E. Galligani, A generalization of irreducibility and diagonal dominance with applications to horizontal and vertical linear complementarity problems, Linear Algebra Appl., 621 (2021), 214–234. http://dx.doi.org/10.1016/j.laa.2021.03.016 doi: 10.1016/j.laa.2021.03.016
[16]	M. Gowda, R. Sznajder, The generalized order linear complementarity problem, SIAM J. Matrix Anal. Appl., 15 (1994), 779–795. http://dx.doi.org/10.1137/S0895479892237859 doi: 10.1137/S0895479892237859
[17]	F. Facchinei, J. Pang, Finite-dimensional variational inequalities and complementarity problems, New York: Springer, 2003.
[18]	J. Alcantara, J. S. Chen, Neural networks based on three classes of NCP-functions for solving nonlinear complementarity problems, Neurocomputing, 359 (2019), 102–113. http://dx.doi.org/10.1016/j.neucom.2019.05.078 doi: 10.1016/j.neucom.2019.05.078
[19]	L. Yang, J. Li, L. W. Zhang, A novel neural network for linear complementarity problems, Journal of Mathematical Research and Exposition, 27 (2007), 539–546.
[20]	A. Hadjidimos, M. Tzoumas, On the solution of the linear complementarity problem by the generalized accelerated overrelaxation iterative method, J. Optim. Theory Appl., 165 (2015), 545–562. http://dx.doi.org/10.1007/s10957-014-0589-4 doi: 10.1007/s10957-014-0589-4
[21]	H. Ren, X. Wang, X. B. Tang, T. Wang, The general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems, Comput. Math. Appl., 77 (2019), 1071–1081. http://dx.doi.org/10.1016/j.camwa.2018.10.040 doi: 10.1016/j.camwa.2018.10.040
[22]	L. Pang, N. Xu, J. Lv, The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints, J. Ind. Manag. Optim., 15 (2019), 59–79. http://dx.doi.org/10.3934/jimo.2018032 doi: 10.3934/jimo.2018032
[23]	J. Zhang, X. S. He, Q. Wang, A SAA nonlinear regularization method for a stochastic extended vertical linear complementarity problem, Appl. Math. Comput., 232 (2014), 888–897. http://dx.doi.org/10.1016/j.amc.2014.01.121 doi: 10.1016/j.amc.2014.01.121
[24]	J. Zhang, S. Lin, L. W. Zhang, A log-exponential regularization method for a mathenmatical program with general vertical complementarity constraints, J. Ind. Manag. Optim., 9 (2013), 561–577. http://dx.doi.org/10.3934/jimo.2013.9.561 doi: 10.3934/jimo.2013.9.561
[25]	J. Zhang, Y. Q. Zhang, L. W. Zhang, A sample average approximation regulaeization method for a stochastic mathematical program with general vertical complementarity constraints, J. Comput. Appl. Math., 280 (2015), 202–216. http://dx.doi.org/10.1016/j.cam.2014.11.057 doi: 10.1016/j.cam.2014.11.057
[26]	H. Scheel, S. Scholtes, Mathematical programs with complementarity constraints: stationarity, optimiality and sensitivity, Math. Oper. Res., 25 (2000), 1–22. http://dx.doi.org/10.1287/moor.25.1.1.15213 doi: 10.1287/moor.25.1.1.15213
[27]	L. Chua, G. N. Lin, Nonlinear programming without computation, IEEE T. Circuits, 31 (1984), 182–188. http://dx.doi.org/10.1109/TCS.1984.1085482 doi: 10.1109/TCS.1984.1085482
[28]	J. Hopfield, Neurons with graded response have collective computational properties like those of two-state neurons, Proc. Natl. Acad. Sci. USA, 81 (1984), 3088–3092. http://dx.doi.org/10.1073/pnas.81.10.3088 doi: 10.1073/pnas.81.10.3088
[29]	J. Hopfield, D. Tank, "Neural" computation of decisions in optimization problems, Biol. Cybern., 52 (1985), 141–152. http://dx.doi.org/10.1007/bf00339943 doi: 10.1007/bf00339943
[30]	L. Z. Liao, H. Qi, A neural network for the linear complementarity problem, Math. Comput. Model., 29 (1999), 9–18. http://dx.doi.org/10.1016/S0895-7177(99)00026-6 doi: 10.1016/S0895-7177(99)00026-6
[31]	L. Z. Liao, H. Qi, L. Qi, Solving nonlinear complementarity problems with neural networks: a reformulation method approach, J. Comput. Appl. Math., 131 (2001), 343–359. http://dx.doi.org/10.1016/S0377-0427(00)00262-4 doi: 10.1016/S0377-0427(00)00262-4
[32]	A. Golbabai, S. Ezazipour, A projection based on recurrent neural network and its application in solving convex quadratic bilevel optimization problems, Neural Comput. Applic., 32 (2020), 3887–3900. http://dx.doi.org/10.1007/s00521-019-04391-7 doi: 10.1007/s00521-019-04391-7
[33]	A. Zazemi, A. Sabeghi, A new neural network framework for solving convex second-order cone constrained variational inequality problems with an application in multi-ginger robot hands, J. Exp. Thero. Artif. In., 32 (2020), 181–203. http://dx.doi.org/10.1080/0952813X.2019.1647559 doi: 10.1080/0952813X.2019.1647559
[34]	J. Sun, J. S. Chen, C. H. Ko, Neural networks for solving second-order cone constrained variational inequality problem, Comput. Optim. Appl., 51 (2012), 623–648. http://dx.doi.org/10.1007/s10589-010-9359-x doi: 10.1007/s10589-010-9359-x
[35]	J. Sun, W. Fu, J. Alcantara, J. S. Chen, A neural network based on the metric projector for solving SOCCVI problem, IEEE T. Neur. Net. Lear., 32 (2020), 2886–2900. http://dx.doi.org/10.1109/TNNLS.2020.3008661 doi: 10.1109/TNNLS.2020.3008661
[36]	S. Wen, S. Xiao, Z. Yan, Z. Zeng, T. Huang, Adjusting learning rate of memristor-based multilayer neural networks via fuzzy method, IEEE T. Comput. Aid. D., 38 (2019), 1084–1094. http://dx.doi.org/10.1109/TCAD.2018.2834436 doi: 10.1109/TCAD.2018.2834436
[37]	X. Ju, H. Che, C. Li, X. He, G. Feng, Exponential convergence of a proximal projection neural network for mixed variational inequalities and applications, Neurocomputing, 454 (2021), 54–64. http://dx.doi.org/10.1016/j.neucom.2021.04.059 doi: 10.1016/j.neucom.2021.04.059
[38]	X. Ju, C. Li, X. He, G. Feng, An inertial projection neural network for solving inverse variational inequalities, Neurocomputing, 406 (2020), 99–105. http://dx.doi.org/10.1016/j.neucom.2020.04.023 doi: 10.1016/j.neucom.2020.04.023
[39]	Q. Han, L. Z. Liao, H. Qi, L. Qi, Stability analysis of gradient-based neural networks for optimization problems, J. Global Optim., 19 (2001), 363–381. http://dx.doi.org/10.1023/A:1011245911067 doi: 10.1023/A:1011245911067
[40]	M. Xu, B. Du, Dynamic behaviors for reation-diffusion neural networks with mixed delays, AIMS Mathematics, 5 (2020), 6841–6855. http://dx.doi.org/10.3934/math.2020439 doi: 10.3934/math.2020439
[41]	F. Clarke, Optimization and nonsmooth analysis, New York: Society for Industrial and Applied Mathematics, 1990.
[42]	R. Rockafellar, Convex analysis, New Jersey: Princeton University Press, 1970.
[43]	R. Rockafellar, R. Wets, Variational analysis, Berlin: Springer, 1998. http://dx.doi.org/10.1007/978-3-642-02431-3
[44]	W. Bian, X. Chen, Neural network for nonsmooth, nonconvex constrained minimization via smooth approximation, IEEE T. Neur. Net. Lear., 25 (2014), 545–556. http://dx.doi.org/10.1109/TNNLS.2013.2278427 doi: 10.1109/TNNLS.2013.2278427
[45]	J. Zabczyk, Mathematical control theory, Boston: Birkh $ \ddot{a} $ users, 2020. http://dx.doi.org/10.1007/978-3-030-44778-6
[46]	H. Qi, L. Liao, Z. Lin, Regularized smoothing approximations to vertical nonlinear complementarity problems, J. Math. Anal. Appl., 230 (1999), 261–276. http://dx.doi.org/10.1006/jmaa.1998.6205 doi: 10.1006/jmaa.1998.6205
[47]	F. Facchinei, J. Soares, A new merit function for nonliner complementarity problems and a related algorithm, SIAM J. Optim., 7 (1997), 225–247. http://dx.doi.org/10.1137/S1052623494279110 doi: 10.1137/S1052623494279110
[48]	L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18 (1993), 227–244. http://dx.doi.org/10.1287/moor.18.1.227 doi: 10.1287/moor.18.1.227
[49]	M. Gowda, R. Sznajder, A generalization of the Nash equilibeium theorem on bimatrix games, Int. J. Game Theory, 25 (1996), 1–12. http://dx.doi.org/10.1007/BF01254380 doi: 10.1007/BF01254380
[50]	G. Murthy, T. Parthasarthy, D. Sampangi, SER-SIT stichastic games and vertical linear, Proceedings of 14th International Conference on Game Theory, 2003.

Reader Comments

Your name:*

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