Kybernetika 51 no. 5, 890-908, 2015

Solving a class of non-convex quadratic problems based on generalized KKT conditions and neurodynamic optimization technique

Alaeddin Malek and Najmeh Hosseinipour-MahaniDOI: 10.14736/kyb-2015-5-0890

Abstract:

In this paper, based on a generalized Karush-Kuhn-Tucker (KKT) method a modified recurrent neural network model for a class of non-convex quadratic programming problems involving a so-called $Z$-matrix is proposed. The basic idea is to express the optimality condition as a mixed nonlinear complementarity problem. Then one may specify conditions for guaranteeing the global solutions of the original problem by using results from the S-lemma. This process is proved by building up a dynamic system from the optimality condition whose equilibrium point is exactly the solution of the mixed nonlinear complementarity problem. By the study of the resulting dynamic system it is shown that under given assumptions, steady states of the dynamic system are stable. Numerical simulations and comparisons with the other methods are presented to illustrate the efficiency of the practical technique that is proposed in this paper.

Keywords:

global convergence, non-convex quadratic optimization, recurrent neural network model, global optimality conditions

Classification:

90C26, 37N40

References:

  1. M. S. Bazaraa and C. M. Shetty: Nonlinear Programming Theory and Algorithms. Wiley and Sons, New York 1990.   CrossRef
  2. D. Beyer and R. Ogier: Tabu learning: A neural network search method for solving nonconvex optimization problems. IEEE Int. Joint Conf. Neural Networks 2 (2000), 953-961.   CrossRef
  3. W. Bian and X. Xue: Subgradient-based neural networks for nonsmooth nonconvex optimization problems. IEEE Trans. Neural Networks 20 (2009), 6, 1024-1038.   DOI:10.1109/tnn.2009.2016340
  4. C. Chicone: Ordinary Differential Equations with Applications. Second edition. Springer-Verlag, New York 2006.   CrossRef
  5. M. Forti, P. Nistri and M. Quincampoix: Convergence of neural networks for programming problems via a nonsmooth Lojasiewicz inequality. IEEE Trans. Neural Networka 17 (2006), 6, 1471-1486.   DOI:10.1109/tnn.2006.879775
  6. X. B. Gao: A novel neural network for nonlinear convex programming problems. IEEE Trans. Neural Network 15 (2004), 613-621.   DOI:10.1109/tnn.2004.824425
  7. X. Hu: Neurodynamic optimization: Towards nonconvexity. In: Recurrent Neural Networks ( X. Hu and P. Balasubramaniam, ed.), IN-TECH, 2008, pp. 289-308.   DOI:10.5772/5551
  8. V. Jeyakumar, A. M. Rubinov and Z. Y. Wu: Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions. Math. Program., Ser. A 110 (2007), 521-541.   DOI:10.1007/s10107-006-0012-5
  9. V. Jeyakumar, G. M. Lee and G. Y. Li: Alternative theorems for quadratic inequality systems and global quadratic optimization. SIAM J. Optim 20 (2009), 2, 983-1001.   DOI:10.1137/080736090
  10. V. Jeyakumar and S. Srisatkunarajah: Lagrange multiplier necessary condition for global optimality for non-convex minimization over a quadratic constraint via S-lemma. Optim. Lett. 3 (2009), 23-33.   DOI:10.1007/s11590-008-0088-3
  11. H. K. Khalil: Nonlinear Systems. Third edition. Prentice Hall, 2002.   CrossRef
  12. A. Malek: Application of recurrent neural networks to optimization problems. In: Recurrent Neural Networks ( X. Hu and P. Balasubramaniam, eds.), IN-TECH, 2008, pp. 255-288.   DOI:10.5772/5556
  13. A. Malek and M. Alipour: Numerical solution for linear and quadratic programming problems using a recurrent neural network. Appl. Math. Comput 192 (2007), 27-39.   DOI:10.1016/j.amc.2007.02.149
  14. A. Malek, N. Hosseinipour-Mahani and S. Ezazipour: Efficient recurrent neural network model for the solution of general nonlinear optimization problems. Optimization Methods and Software 25 (2010), 489-506.   DOI:10.1080/10556780902856743
  15. A. Malek, S. Ezazipour and N. Hosseinipour-Mahani: Double projection neural network for solving pseudomonotone variational inequalities. Fixed Point Theory 12 (2011), 2, 401-418.   CrossRef
  16. A. Malek, S. Ezazipour and N. Hosseinipour-Mahani: Projected dynamical systems and optimization problems. Bull. Iranian Math. Soc. 37 (2011), 2, 81-96.   CrossRef
  17. A. Malek and A. Yari: Primal-dual solution for the linear programming problem using neural network. Appl. Math. Comput. 169 (2005), 198-211.   DOI:10.1016/j.amc.2004.06.081
  18. R. K. Miller and A. N. Michel: Ordinary Differential Equations. Academic Press, 1982.   DOI:10.1016/b978-0-12-497280-3.50008-6
  19. I. Polik and T. Terlaky: A survey of the S-Lemma. SIAM Rev. 49 (2007), 371-418.   DOI:10.1137/s003614450444614x
  20. C. Y. Sun and C. B. Feng: Neural networks for nonconvex nonlinear programming problems: A switching control approach. In: Lecture Notes in Computer Science 3495, Springer-Verlag, Berlin 2005, pp. 694-699.   DOI:10.1007/11427391_111
  21. Q. Tao, X. Liu and M. S. Xue: A dynamic genetic algorithm based on continuous neural networks for a kind of non-convex optimization problems. Appl. Math. Comput. 150 (2004), 811-820.   DOI:10.1016/s0096-3003(03)00309-6
  22. Y. Tian and Ch. Lu: Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems J. Industr. Managment Optim. 7 (2011), 1027-1039.   DOI:10.3934/jimo.2011.7.1027
  23. Y. Xia, G. Feng and J. Wang: A recurrent neural network with exponential convergence for solving convex quadratic program and related linear piecewise equation. Neural Networks 17 (2004), 1003-1015.   DOI:10.1016/j.neunet.2004.05.006
  24. Y. S. Xia, G. Feng and J. Wang: A novel recurrent neural network for solving nonlinear optimization problems with inequality constraints. IEEE Trans. Neural Networks 19 (2008), 1340-1353.   DOI:10.1109/tnn.2008.2000273
  25. X. Xue and W. Bian: A project neural network for solving degenerate convex quadratic program. Neurocomputing 70 (2007), 2449-2459.   DOI:10.1016/j.neucom.2006.10.038
  26. Z. Yan, J. Wang and G. Li: A collective neurodynamic optimization approach to bound-constrained nonconvex optimization. Neural networks 55 (2014), 20-29.   DOI:10.1016/j.neunet.2014.03.006
  27. M. Yashtini and A. Malek: Solving complementarity and variational inequalities problems using neural networks. Appl. Math. Comput. 190 (2007), 216-230.   DOI:10.1016/j.amc.2007.01.036
  28. Y. Zhang: Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization. Math. Programming 55 (1992), 109-124.   DOI:10.1007/bf01581194
  29. X. J. Zheng, X. L. Sun, D. Li and Y. F. Xu: On zero duality gap in nonconvex quadratic programming problems. Global Optim. 52 (2012), 229-242.   DOI:10.1007/s10898-011-9660-y