A globally convergent neurodynamics optimization model for mathematical programming with equilibrium constraints

Ezazipour, Soraya ; Golbabai, Ahmad

Kybernetika, Tome 56 (2020) no. 3, pp. 383-409

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2020-3-0383

Classification : 90C26, 90C33
Keywords: neural network; mathematical programming with equilibrium constraints; asymptotically stability; globally convergence

Bibliographie

[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 | MR

[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 | MR

[3] Bard, J. F.: Convex two-level optimization. Math. Program. 40 (1988), 15-27. | DOI | MR

[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 | MR

[5] Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85 (1999), 107-134. | DOI | MR | Zbl

[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

[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 | MR | Zbl

[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 | MR

[9] Guo, L., Lin, G. H., Ye, J. J.: Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166 (2015), 234-256. | DOI | MR

[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

[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

[12] Hopfiel, J. J., Tank, D. W.: Neural computation of decisions in optimization problems. Biol. Cybernet. 52 (1985), 141-152. | DOI | MR

[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 | MR

[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 | MR

[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 | MR

[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 | MR

[17] Jane, J. Y.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. Math. Anal. Appl. 307 (2005), 350-369. | DOI | MR

[18] Kočvara, M., Outrata, J.: Optimization problems with equilibrium constraints and their numerical solution. Math. Program. 101 (2004), 119-149. | DOI | MR

[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 | MR | Zbl

[20] Luenberger, D. G., Ye, Y.: Linear and Nonlinear Programming. Springer Science and Business Media, 233 Spring Street, New York 2008. | DOI | MR

[21] Luo, Z. Q., Pang, J. S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge 1996. | DOI | MR | Zbl

[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 | MR

[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

[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 | MR

[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 | MR

[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 | MR

[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 | MR

[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

[29] Lin, G. H., Fukushima, M.: New relaxation method for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 118 (2003), 81-116. | DOI | MR

[30] Malek, A., Ezazipour, S., Hosseinipour-Mahani, N.: Projected dynamical systems and optimization problems. Bull. Iranian Math. Soc. 37 (2011), 81-96. | MR | Zbl

[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

[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 | MR | Zbl

[33] Morrison, D. D.: Optimization by least squares. SIAM J. Numer. Anal. 5 (1968), 83-88. | DOI | MR

[34] Miller, R. K., Michel, A. N.: Ordinary Differential Equations. Academic Press, New York 1982. | MR | Zbl

[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 | MR

[36] Outrata, J. V.: On optimization problems with variational inequality constraints. SIAM J. Optim. 4 (1994), 340-357. | DOI | MR

[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

[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 | MR

[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

[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 | MR