Kybernetika 56 no. 3, 383-409, 2020

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

Soraya Ezazipour and Ahmad GolbabaiDOI: 10.14736/kyb-2020-3-0383

Abstract:

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.

Keywords:

neural network, mathematical programming with equilibrium constraints, asymptotically stability, globally convergence

Classification:

90C33, 90C26

paper.pdf

References:

  1. R. Andreani and J. M. Martínez: On the solution of mathematical programming problems with equilibrium constraints. Math. Methods Oper. Res. 54 (2001), 345-359.   DOI:10.1007/s001860100158
  2. E. Aiyoshi and K. Shimizu: 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
  3. J. F. Bard: Convex two-level optimization. Math. Program. 40 (1988), 15-27.   DOI:10.1109/tsmc.1981.4308712
  4. J. S. Chen: On some NCP-functions based on the generalized Fischer-Burmeister function. Asia-Pacific J. Oper. Res. 24 (2007), 401-420.   DOI:10.1142/s0217595907001292
  5. F. Facchinei, H. Jiang and L. Qi: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85 (1999), 107-134.   DOI:10.1007/s10107990015a
  6. M. C. Ferris, S. P. Dirkse and A. Meeraus: 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. R. Fletcher, S. Leyffer, D. Ralph and S. Scholtes: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17 (2006), 259-286.   DOI:10.1137/s1052623402407382
  8. F. Facchinei and J. Soares: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7 (1997), 225-247.   DOI:10.1137/s1052623494279110
  9. L. Guo, G. H. Lin and J. J. Ye: Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166 (2015), 234-256.   DOI:10.1007/s10957-014-0699-z
  10. A. Golbabai and S. Ezazipour: 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. X. He, C. Li, T. Huang and C. H. Li: Neural network for solving convex quadratic bilevel programming problems. Neural Networks 51 (2014), 17-25.   DOI:10.1016/j.neunet.2013.11.015
  12. J. J. Hopfiel and D. W. Tank: Neural computation of decisions in optimization problems. Biol. Cybernet. 52 (1985), 141-152.   DOI:10.1016/0096-3003(85)90004-9
  13. A. Hosseini and S. M. Hosseini: 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
  14. N. Hosseinipour-Mahani and A. Malek: 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
  15. N. Hosseinipour-Mahani and A. Malek: 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
  16. X. X. Huang, X. Q. Yang and K. L. Teo: Partial augmented Lagrangian method and mathematical programs with complementarity constraints. Global Optim. 35 (2006), 235-254.   DOI:10.1007/s10898-005-3837-1
  17. J. Y. Jane: 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
  18. M. Kočvara and J. Outrata: Optimization problems with equilibrium constraints and their numerical solution. Math. Program. 101 (2004), 119-149.   DOI:10.1007/s10107-004-0539-2
  19. C. Kanzow and A. Schwartz: 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
  20. D. G. Luenberger and Y. Ye: Linear and Nonlinear Programming. Springer Science and Business Media, 233 Spring Street, New York 2008.   DOI:10.1007/978-0-387-74503-9
  21. Z. Q. Luo, J. S. Pang and D. Ralph: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge 1996.   DOI:10.1017/cbo9780511983658
  22. K. M. Lan, U. P. Wen, H. S. Shih and E. S. Lee: A hybrid neural network approach to bilevel programming problems. Appl. Math. Lett. 20 (2007), 880-884.   DOI:10.1016/j.aml.2006.07.013
  23. J. Li, C. Li, Z. Wu and J. Huang: 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. Q. Liu and J. Wang: 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
  25. Y. Lv, Z. Chen and Z. Wan: 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
  26. S. Leyffer: 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
  27. L. Z. Liao, H. Qi and L. Qi: 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
  28. E. W. Lillo, M. H. Loh, S. Hui and H. S. Zak: 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. G. H. Lin and M. Fukushima: New relaxation method for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 118 (2003), 81-116.   DOI:10.1023/a:1024739508603
  30. A. Malek, S. Ezazipour and N. Hosseinipour-Mahani: Projected dynamical systems and optimization problems. Bull. Iranian Math. Soc. 37 (2011), 81-96.   CrossRef
  31. A. Malek, S. Ezazipour and N. Hosseinipour-Mahani: Double projection neural network for solving pseudomonotone variational inequalities. Fixed Point Theory 12 (2011), 401-418.   CrossRef
  32. A. Malek, N. Hosseinipour-Mahani and S. Ezazipour: Efficient recurrent neural network model for the solution of general nonlinear optimization problems. Optim. Methods Software 25 (2010), 489-506.   DOI:10.1080/10556780902856743
  33. D. D. Morrison: Optimization by least squares. SIAM J. Numer. Anal. 5 (1968), 83-88.   DOI:10.1137/0705006
  34. R. K. Miller and A. N. Michel: Ordinary Differential Equations. Academic Press, New York 1982.   CrossRef
  35. J. V. Outrata, M. Kočvara and J. Zowe: 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
  36. J. V. Outrata: On optimization problems with variational inequality constraints. SIAM J. Optim. 4 (1994), 340-357.   DOI:10.1137/0804019
  37. M. Ranjbar, S. Effati and S. M. Miri: 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. Z. Sheng, Z. Lv and Z. Xu: 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.   CrossRef
  39. S. Scholtes and M. Stohr: Exact penalization of mathematical programs with complementarity constraints. SIAM J. Control Optim. 37 (1999), 617-652.   DOI:10.1137/s0363012996306121
  40. D. W. Tank and J. J. Hopfield: 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. Q. X. Yang and X. X. Huang: Lower-order penalty methods for mathematical programs with complementarity constraints. Optim. Methods Software 19 (2004), 693-720.   DOI:10.1080/1055678041001697659