Previous |  Up |  Next


neural network; mathematical programming with equilibrium constraints; asymptotically stability; globally convergence
This paper introduces a neurodynamics optimization model to compute the solution of mathematical programming with equilibrium constraints (MPEC). A smoothing method based on NPC-function is used to obtain a relaxed optimization problem. The optimal solution of the global optimization problem is estimated using a new neurodynamic system, which, in finite time, is convergent with its equilibrium point. Compared to existing models, the proposed model has a simple structure, with low complexity. The new dynamical system is investigated theoretically, and it is proved that the steady state of the proposed neural network is asymptotic stable and global convergence to the optimal solution of MPEC. Numerical simulations of several examples of MPEC are presented, all of which confirm the agreement between the theoretical and numerical aspects of the problem and show the effectiveness of the proposed model. Moreover, an application to resource allocation problem shows that the new method is a simple, but efficient, and practical algorithm for the solution of real-world MPEC problems.
[1] Andreani, R., Martínez, J. M.: On the solution of mathematical programming problems with equilibrium constraints. Math. Methods Oper. Res. 54 (2001), 345-359. DOI 10.1007/s001860100158 | MR 1890905
[2] Aiyoshi, E., Shimizu, K.: Hierarchical decentralized systems and its new solution by a barrier method. IEEE Trans. Systems Man Cybernet. 11 (1981), 444-449. DOI 10.1109/tsmc.1981.4308712 | MR 0631815
[3] Bard, J. F.: Convex two-level optimization. Math. Program. 40 (1988), 15-27. DOI 10.1109/tsmc.1981.4308712 | MR 0923693
[4] Chen, J. S.: On some NCP-functions based on the generalized Fischer-Burmeister function. Asia-Pacific J. Oper. Res. 24 (2007), 401-420. DOI 10.1142/s0217595907001292 | MR 2335554
[5] Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85 (1999), 107-134. DOI 10.1007/s10107990015a | MR 1689366 | Zbl 0959.65079
[6] Ferris, M. C., Dirkse, S. P., Meeraus, A.: Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimization. Frontiers in Applied General Equilibrium Modeling, Cambridge University Press 2002, pp. 67-94. DOI 10.1017/cbo9780511614330.005
[7] Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17 (2006), 259-286. DOI 10.1137/s1052623402407382 | MR 2219153 | Zbl 1112.90098
[8] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7 (1997), 225-247. DOI 10.1137/s1052623494279110 | MR 1430565
[9] Guo, L., Lin, G. H., Ye, J. J.: Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166 (2015), 234-256. DOI 10.1007/s10957-014-0699-z | MR 3366112
[10] Golbabai, A., Ezazipour, S.: A high-performance nonlinear dynamic scheme for the solution of equilibrium constrained optimization problems. Expert Systems Appl. 82 (2017), 291-300. DOI 10.1016/j.eswa.2017.04.016
[11] He, X., Li, C., Huang, T., Li, C. H.: Neural network for solving convex quadratic bilevel programming problems. Neural Networks 51 (2014), 17-25. DOI 10.1016/j.neunet.2013.11.015
[12] Hopfiel, J. J., Tank, D. W.: Neural computation of decisions in optimization problems. Biol. Cybernet. 52 (1985), 141-152. DOI 10.1016/0096-3003(85)90004-9 | MR 0824597
[13] Hosseini, A., Hosseini, S. M.: A new steepest descent differential inclusion-based method for solving general nonsmooth convex optimization problems. J. Optim. Theory Appl. 159 (2013), 698-720. DOI 10.1007/s10957-012-0258-4 | MR 3124992
[14] Hosseinipour-Mahani, N., Malek, A.: A neurodynamic optimization technique based on overestimator and underestimator functions for solving a class of non-convex optimization problems. Math. Comput. Simul. 122 (2016), 20-34. DOI 10.1016/j.matcom.2015.09.013 | MR 3436939
[15] Hosseinipour-Mahani, N., Malek, A.: Solving a class of non-convex quadratic problems based on generalized KKT conditions and neurodynamic optimization technique. Kybernetika 51 (2015), 890-908. DOI 10.14736/kyb-2015-5-0890 | MR 3445990
[16] Huang, X. X., Yang, X. Q., Teo, K. L.: Partial augmented Lagrangian method and mathematical programs with complementarity constraints. Global Optim. 35 (2006), 235-254. DOI 10.1007/s10898-005-3837-1 | MR 2242014
[17] Jane, J. Y.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. Math. Anal. Appl. 307 (2005), 350-369. DOI 10.1016/j.jmaa.2004.10.032 | MR 2138995
[18] Kočvara, M., Outrata, J.: Optimization problems with equilibrium constraints and their numerical solution. Math. Program. 101 (2004), 119-149. DOI 10.1007/s10107-004-0539-2 | MR 2085261
[19] Kanzow, C., Schwartz, A.: A new regularization method for mathematical programs with complementarity constraints with strong convergence properties. SIAM J. Optim. 23 (2013), 770-798. DOI 10.1137/100802487 | MR 3045664 | Zbl 1282.65069
[20] Luenberger, D. G., Ye, Y.: Linear and Nonlinear Programming. Springer Science and Business Media, 233 Spring Street, New York 2008. DOI 10.1007/978-0-387-74503-9 | MR 2423726
[21] Luo, Z. Q., Pang, J. S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge 1996. DOI 10.1017/cbo9780511983658 | MR 1419501 | Zbl 1139.90003
[22] Lan, K. M., Wen, U. P., Shih, H. S., Lee, E. S.: A hybrid neural network approach to bilevel programming problems. Appl. Math. Lett. 20 (2007), 880-884. DOI 10.1016/j.aml.2006.07.013 | MR 2323126
[23] Li, J., Li, C., Wu, Z., Huang, J.: A feedback neural network for solving convex quadratic bi-level programming problems. Neural Comput. Appl. 25 (2014), 603-611. DOI 10.1007/s00521-013-1530-8
[24] Liu, Q., Wang, J.: A one-layer projection neural network for nonsmooth optimization subject to linear equalities and bound constraints. IEEE Trans. Neural Networks Learning Systems 24 (2013), 812-824. DOI 10.1109/tnnls.2013.2244908 | MR 3453221
[25] Lv, Y., Chen, Z., Wan, Z.: A neural network approach for solving mathematical programs with equilibrium constraints. Expert System Appl. 38 (2011), 231-234. DOI 10.1016/j.eswa.2010.06.050 | MR 2557563
[26] Leyffer, S.: Complementarity constraints as nonlinear equations: Theory and numerical experience. In: Optimization with Multivalued Mappings (S. Dempe and V. Kalashnikov, eds.), Springer Optimization and Its Applications, vol 2. Springer, Boston 2006. DOI 10.1007/0-387-34221-4\_9 | MR 2243542
[27] Liao, L. Z., Qi, H., Qi, L.: Solving nonlinear complementarity problems with neural networks: a reformulation method approach. J. Comput. Appl. Math. 131 (2001), 343-359. DOI 10.1016/s0377-0427(00)00262-4 | MR 1835721
[28] Lillo, E. W., Loh, M. H., Hui, S., Zak, H. S.: On solving constrained optimization problems with neural networks: a penalty method approach. IEEE Trans. Neural Networks 4 (1993), 931-940. DOI 10.1109/72.286888
[29] Lin, G. H., Fukushima, M.: New relaxation method for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 118 (2003), 81-116. DOI 10.1023/a:1024739508603 | MR 1995697
[30] Malek, A., Ezazipour, S., Hosseinipour-Mahani, N.: Projected dynamical systems and optimization problems. Bull. Iranian Math. Soc. 37 (2011), 81-96. MR 2890580 | Zbl 1253.37091
[31] Malek, A., Ezazipour, S., Hosseinipour-Mahani, N.: Double projection neural network for solving pseudomonotone variational inequalities. Fixed Point Theory 12 (2011), 401-418. MR 2895702
[32] Malek, A., Hosseinipour-Mahani, N., Ezazipour, S.: Efficient recurrent neural network model for the solution of general nonlinear optimization problems. Optim. Methods Software 25 (2010), 489-506. DOI 10.1080/10556780902856743 | MR 2724153 | Zbl 1225.90129
[33] Morrison, D. D.: Optimization by least squares. SIAM J. Numer. Anal. 5 (1968), 83-88. DOI 10.1137/0705006 | MR 0226828
[34] Miller, R. K., Michel, A. N.: Ordinary Differential Equations. Academic Press, New York 1982. MR 0660250 | Zbl 0552.34001
[35] Outrata, J. V., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Theory, Applications and Numerical Results. Kluwer Academic Publishers, Dordrecht 1998. DOI 10.1007/978-1-4757-2825-5 | MR 1641213
[36] Outrata, J. V.: On optimization problems with variational inequality constraints. SIAM J. Optim. 4 (1994), 340-357. DOI 10.1137/0804019 | MR 1273763
[37] Ranjbar, M., Effati, S., Miri, S. M.: An artificial neural network for solving quadratic zero-one programming problems. Neurocomputing 235 (2017), 192-198. DOI 10.1016/j.neucom.2016.12.064
[38] Sheng, Z., Lv, Z., Xu, Z.: A new algorithm based on the Frank-Wolfe method and neural network for a class of bilevel decision making problem. Acta Automat. Sinica 22 (1996), 657-665.
[39] Scholtes, S., Stohr, M.: Exact penalization of mathematical programs with complementarity constraints. SIAM J. Control Optim. 37 (1999), 617-652. DOI 10.1137/s0363012996306121 | MR 1670641
[40] Tank, D. W., Hopfield, J. J.: Simple neural optimization networks: an A/D converter, signal decision circuit, and a linear programming circuit. IEEE Trans. Circuits Syst. 33 (1986), 533-541. DOI 10.1109/tcs.1986.1085953
[41] Yang, Q. X., Huang, X. X.: Lower-order penalty methods for mathematical programs with complementarity constraints. Optim. Methods Software 19 (2004), 693-720. DOI 10.1080/1055678041001697659 | MR 2102222
Partner of
EuDML logo