Neural networks based on three classes of NCP-functions for solving nonlinear complementarity problems

Jan Harold M. Alcantara

Department of Mathematics

National Taiwan Normal University

janharold27@yahoo.com

    We consider a family of neural networks for solving nonlinear complementarity problems (NCP). The neural networks are based from the merit functions induced by three classes of NCP-functions: the generalized natural residual function and its two symmetrizations. We first provide a characterization of the stationary points of the induced merit functions. To describe the level sets of the merit functions, we prove some important properties related to the growth behavior of the complementarity functions. Furthermore, we analyze the stability of the steepest descent-based neural network model for NCP. To illustrate the theoretical results, we provide numerical simulations using our neural network and compare it with other similar neural networks in the literature which are based on other well-known NCP-functions. The numerical results suggest that the neural network has a better performance when their common parameter `p` is smaller. We also found that one among the three families of neural networks we considered is capable of outperforming other existing neural networks.
This is a joint work with Jein-Shan Chen.

Keyword: NCP-function, Neural network, natural residual function, stability

References

[1] Y.-L. Chang, J.-S. Chen, C.-Y. Yang, Symmetrization of generalized natural residual function for NCP, Operations Research Letters, 43(2015), 354-358.
[2] J.-S. Chen, C.-H. Ko, and S.-H. Pan, A neural network based on generalized Fischer-Burmeister function for nonlinear complementarity problems, Information Sciences, 180(2010), 697-711.
[3] J.-S. Chen, C.-H. Ko, and X.-R. Wu, What is the generalization of natural residual function for NCP, Pacific Journal of Optimization, 12(2016), 19-27.
[4] J.-S. Chen and S.-H. Pan (2008), A family of NCP functions and a descent method for the nonlinear complementarity problem, Computational Optimization and Applications, vol. 40, 389-404.
[5] R.W. Cottle, J.-S. Pang and R.-E. Stone, The Linear Complementarity Problem, Academic Press, New York 1992.
[6] C. Dang, Y. Leung, X. Gao, and K. Chen (2004), Neural networks for nonlinear and mixed complementarity problems and their applications, Neural Networks, vol. 17, 271-283.
[7] M. C. Ferris, O. L. Mangasarian, and J.-S. Pang, editors, Complementarity: Applications, Algorithms and Extensions, Kluwer Academic Publishers, Dordrecht, 2001.
[8] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II, Springer-Verlag, New York, 2003.
[9] F. Facchinei and J. Soares (1997), A new merit function for nonlinear complementarity problems and a related algorithm, SIAM Journal on Optimization, vol. 7, 225-247.
[10] C. Geiger, and C. Kanzow (1996), On the resolution of monotone complementarity problems, Computational Optimization and Applications, vol. 5, 155-173.
[11] J. J. Hopfield and D. W. Tank (1985), Neural computation of decision in optimization problems, Biological Cybernetics, vol. 52, 141-152.
[12] X. Hu and J. Wang (2006), Solving pseudomonotone variational inequalities and pseudoconvex optimization problems using the projection neural network, IEEE Transactions on Neural Networks, vol. 17, 1487-1499.
[13] X. Hu and J. Wang (2007), A recurrent neural network for solving a class of general variational inequalities, IEEE Transactions on Systems, Man, and Cybernetics-B, vol. 37, 528--539.
[14] C.-H. Huang, K.-J. Weng, J.-S. Chen, H.-W. Chu and M.-Y. Li (2017), On four discrete-type families of NCP Functions, to appear in Journal of Nonlinear and Convex Analysis, 2017.
[15] C. Kanzow and H. Kleinmichel (1995), A class of Newton-type methods for equality and inequality constrained optimization, Optimization Methods and Software, vol. 5, pp. 173-198.
[16] C. Kanzow (1996), Nonlinear complementarity as unconstrained optimization, Journal of Optimization Theory and Applications, vol. 88, 139-155.
[17] M. P. Kennedy and L. O. Chua (1988), Neural network for nonlinear programming, IEEE Tansaction on Circuits and Systems, vol. 35, 554-562.
[18] M. Kojima and S. Shindo (1986), Extensions of Newton and quasi-Newton methods to systems of `PC^1` equations, Journal of Operations Research Society of Japan, vol. 29, 352-374.
[19] J. P. LaSalle (1968) Stability Theory for Ordinary Differential Equations, Journal of Differential Equations, vol. 4, 57-65.
[20] L.-Z. Liao, H. Qi, and L. Qi (2001), Solving nonlinear complementarity problems with neural networks: a reformulation method approach, Journal of Computational and Applied Mathematics, vol. 131, 342-359.
[21] R. K. Miller and A. N. Michel (1982), Ordinary Differential Equations, Academic Press.
[22] S-K. Oh, W. Pedrycz, and S-B. Roh (2006), Genetically optimized fuzzy polynomial neural networks with fuzzy set-based polynomial neurons, Information Sciences, vol. 176, 3490-3519.
[23] L. Qi and J. Sun (1993) A nonsmooth version of Newton's method Math. Programm. 58, 353-368.
[24] A. Shortt, J. Keating, L. Monlinier, and C. Pannell (2005), Optical implementation of the Kak neural network, Information Sciences, vol. 171, 273-287.
[25] D. W. Tank and J. J. Hopfield (1986), Simple neural optimization networks: an A/D converter, signal decision circuit, and a linear programming circuit, IEEE Transactions on Circuits and Systems, vol. 33, 533-541.
[26] S. Wiggins (2003), Introduction to Applied and Nonlinear Dynamical Systems and Chaos, Springer-Verlag, New York, Inc.
[27] Y. Xia, H. Leung, and J. Wang (2002), A projection neural network and its application to constrained optimization problems, IEEE Transactions on Circuits and Systems-I, vol. 49, 447-458.
[28] Y. Xia, H. Leung, and J. Wang (2004), A genarl projection neural network for solving monotone variational inequalities and related optimization problems, IEEE Transactions on Neural Networks, vol. 15, 318-328.
[29] Y. Xia, H. Leung, and J. Wang (2005), A recurrent neural network for solving nonlinear convex programs subject to linear constraints, IEEE Transactions on Neural Networks, vol. 16, 379-386.
[30] M. Yashtini and A. Malek (2007), Solving complementarity and variational inequalities problems using neural networks, Applied Mathematics and Computation, vol. 190, 216-230.
[31] S. H. Zak, V. Upatising, and S. Hui (1995), Solving linear programming problems with neural networks: a comparative study, IEEE Transactions on Neural Networks, vol. 6, 94-104.
[32] G. Zhang (2007), A neural network ensemble method with jittered training data for time series forecasting, Information Sciences, vol. 177, 5329-5340.