Author: |
吳孝仁 Wu, Xiao-Ren |
---|---|
Thesis Title: |
Neural Network Approach for Nonlinear Complementarity Problem and Quadratic Programming with Second-Order Cone Constraints Neural Network Approach for Nonlinear Complementarity Problem and Quadratic Programming with Second-Order Cone Constraints |
Advisor: |
陳界山
Chen, Jein-Shan |
Degree: |
博士 Doctor |
Department: |
數學系 Department of Mathematics |
Thesis Publication Year: | 2017 |
Academic Year: | 105 |
Language: | 英文 |
Number of pages: | 90 |
Keywords (in Chinese): | Nonlinear Complementarity Problem 、Second-Order Cone 、Neural Network |
Keywords (in English): | Nonlinear Complementarity Problem, Second-Order Cone, Neural Network |
DOI URL: | https://doi.org/10.6345/NTNU202203035 |
Thesis Type: | Academic thesis/ dissertation |
Reference times: | Clicks: 64 Downloads: 24 |
Share: |
School Collection Retrieve National Library Collection Retrieve Error Report |
無中文摘要
This dissertation focuses on two types of optimization problems, nonlinear complementarity problem (NCP for short) and quadratic programming with second-order cone constraints (SOCQP for short). Based on NCP-function and SOC-complementarity function, we propose suitable neural networks for each of them, respectively. For the NCP-function, we propose new one which is the generalization of natural residual function for NCP. It is a discrete generalization of natural residual function phinr, denoted as phinrp. Besides being a NCP-function, we also show its twice dierentiability and present the geometric view. In addition, we utilize neural network approach to solving nonlinear complementarity problems and quadratic programming problems with second-order cone constraints. By building neural networks based on dierent families of smooth NCP or SOCCP-functions. Our goal is to study the stability of the equilibrium with respect to dierent neural network models. Asymptotical stability are built in most neural network models. Under suitable conditions, we show the equilibrium being exponentially stable. Finally, the simulation results are reported to demonstrate the effectiveness of the proposed neural network.
[1] N. Aras, i. K. Altnel and M. Orbay, New heuristic methods for the capacitated
multi-facility Weber problem, Nav. Res. Logist, vol. 54, pp. 2132 2007.
[2] F. Alizedah and D. Goldfarb, Second-order cone programming, Mathematical
Programming, vol. 95, no.1, pp. 3-51, 2003.
[3] Y. L. Chang, J.-S. Chen and C. Y. Yang, Symmetrization of generalized natural
residual function for NCP, Operations Research Letters, vol. 43, pp. 354-358, 2015.
[4] J.-S. Chen and P. Tseng, An unconstrained smooth minimization reformulation
of the second-order cone complementarity problem, Mathematical Programming, vol.
104, pp. 293-327, 2005.
[5] J.-S. Chen, C. H. Ko and S. H. Pan, A neural network based on the general-
ized Fischer-Burmeister function for nonlinear complementarity problems, Informa-
tion Science, vol. 180, pp. 697-711, 2010.
[6] A. Cichocki and R. Unbehauen, Neural Networks for Optimization and Signal
Processing, John wiley. New York, 1993.
[7] J.-S. Chen, The semismooth-related properties of a merit function and a descent
method for the nonlinear complementarity problem, Journal of Global Optimization,
vol. 36, pp. 565-580, 2006.
[8] J.-S. Chen, On some NCP-functions based on the generalized Fischer-Burmeister
function, Asia-Pacic Journal of Operational Research, vol. 24, no. 3, pp. 401-420,
2007.
[9] J.-S. Chen, H. T. Gao and S. Pan, A R-linearly convergent derivative-free al-
gorithm for the NCPs based on the generalized Fischer-Burmeister merit function,
Journal of Computational and Applied Mathematics, vol. 232, pp. 455-471, 2009.
[10] J.-S. Chen, Z. H. Huang and C. Y. She, A new class of penalized NCP-functions
and its properties, Computational Optimization and Applications, vol. 50, no. 1, pp.
49-73, 2011.
[11] J.-S. Chen and S. Pan, A family of NCP-functions and a descent method for the
nonlinear complementarity problem, Computational Optimization and Applications,
vol. 40, pp. 389-404, 2008.
[12] J.-S. Chen, S. H. Pan and T. C. Lin, A smoothing Newton method based on
the generalized Fischer-Burmeister function for MCPs, Nonlinear Analysis: Theory,
Methods and Applications, vol. 72, no. 9-10, pp. 3739-3758, 2010.
[13] J.-S. Chen, S. H. Pan and C. H. Ko, A continuation approach for the capaci-
tated multi-facility Weber problem based on nonlinear SOCP reformulation, Journal
of Global Optimization, vol. 50, no. 4, pp. 713-2, 2011.
[14] J.-S. Chen, S. H. Pan and C. Y. Yang, Numerical comparison of two eective
methods for mixed complementarity problems, Journal of Computational and Applied
Mathematics, vol. 234, no. 3, pp. 667-683, 2010.
[15] J.-S. Chen, D. F. Sun and J. Sun, The SC1 property of the squared norm of the
SOC Fischer-Burmeister function, Operations Research Letters, vol. 36, no. 3, pp.
385-392, 2008.
[16] R. W. Cottle, J.-S. Pang and R. E. Stone, The Linear Complementarity
Problem, Academic Press, New York, 1992.
[17] J.-S. Chen The semismooth-related properties of a merit function and a descent
method for the nonlinear complementarity problem, Journal of Global Optimization,
vol. 36, pp. 565-580, 2006.
[18] J.-S. Chen, H. T. Gao and S. H. Pan A derivative-free R-linearly conver-
gent algorithm based on the generalized Fischer-Burmeister merit function, Journal
of Computational and Applied Mathematics, vol. 232, pp. 455-471, 2009.
[19] J.-S. Chen and S. H. Pan A family of NCP functions and a descent method for the
nonlinear complementarity problem, Computational Optimization and Applications,
vol. 40, pp. 389-404, 2008.
[20] J.-S. Chen and S. H. Pan A regularization semismooth Newton method based on
the generalized Fischer-Burmeister function for P0-NCPs, Journal of Computational
and Applied Mathematics, vol. 220, pp. 464-479, 2008.
[21] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.
[22] C. Dang, Y. Leung, X. Gao and K. Chen Neural networks for nonlinear and
mixed complementarity problems and their applications, Neural Networks, vol. 17, pp.
271-283, 2004.
[23] S. Effati, A. Ghomashi and A. R. Nazemi Application of projection neural
network in solving convex programming problems, Applied Mathematics and Compu-
tation, vol. 188, pp. 1103-1114, 2007.
[24] S. Effati and A. R. Nazemi, Neural and its application for solving linear and
quadratic programming problems, Applied Mathematics and Computation, vol. 172,
pp. 305-331, 2006.
[25] F. Facchinei and J. Pang, Finite-dimensional Variational Inequalities and Com-
plementatity problems, Springer. New York, 2003.
[26] F. Facchinei and J. Soares, A new merit function for nonlinear complementarity
problems and a related algorithm, SIAM Journal on Optimization, vol. 7, pp. 225-247,
1997.
[27] A. Fischer, A special Newton-type optimization methods, Optimization, vol. 24,
pp. 269-284, 1992.
[28] A. Fischer, Solution of the monotone complementarity problem with locally Lips-
chitzian functions, Mathematical Programming, vol. 76, pp. 513-532, 1997.
[29] M. C. Ferris, O. L. Mangasarian and J.-S. Pang, editors, Complementarity:
Applications, Algorithms and Extensions, Kluwer Academic Publishers, Dordrecht,
2001.
[30] S. H. Friedberg, A. J. Insel and L. E. Spence, Linear Algebra, Pearson
College Div, 2002.
[31] A. Galantai, Properties and construction of NCP functions, Computational Op-
timization and Applications, vol. 52, pp. 805-824, 2012.
[32] C. Geiger and C. Kanzow, On the resolution of monotone complementarity
problems, Computational Optimization and Applications, vol. 5, pp. 155-173, 1996.
[33] P. T. Harker and J.-S. Pang, Finite dimensional variational inequality and
nonlinear complementarity problem: a survey of theory, algorithms and applications,
Mathematical Programming, vol. 48, pp. 161-220, 1990.
[34] S. L. Hu, Z. H. Huang and J.-S. Chen, Properties of a family of generalized
NCP-functions and a derevative free algotithm for complementarity problems, Journal
of Computational and Applied Mathematics, vol. 230, pp. 69-82, 2009.
[35] S. Hayashi, N. Yamashita and M. Fukushima, A combined smoothing and reg-
ularization method for monotone second-order cone complementarity problems, SIAM
journal on optimization, vol. 15, pp. 593-615, 2005.
[36] J. J. Hopfield and D. W. Tank, Neural computation of decision in optimization
problems, Biological Cybernetics, vol. 52, pp. 141-152, 1985.
[37] Q. Han, L. Z. Liao, H. Qi and L. Qi, Stabliity analysis of gradient-based neural
networks for optimization problems, Journal of Global Optimization, vol. 19, pp. 363-
381, 2001.
[38] X. Hu and J. Wang, A recurrent neural network for solving a class general vari-
ational inequalities, IEEE Transactions on System, Man and Cybernetics-B, vol. 37,
pp. 528-539, 2007.
[39] C. H. Huang, K. J. Weng, J.-S. Chen, H. W. Chu and M. Y. Li, On four
types of discrete NCP-functions, submitted, 2016
[40] X. Hu and J. Wang Solving pseudomonotone variational inequalities and pseudo-
convex optimization problems using the projection neural network, IEEE Transactions
on Neural Networks, vol. 17, pp. 1487-1499, 2006.
[41] H. Jiang, Unconstrained minimization approaches to nonlinear complementarity
problems, Journal of Global Optimization, vol. 9, pp. 169-181, 1996.
[42] V. Jeyakumar and H. Wolkowicz, Generalizations of Slater's Constraint Qual-
ication for Innite Convex Programs, Mathematical Programming, vol. 57, pp.85-
101, 1992.
[43] C. Knozow, I. Ferenczi and M. Fukushima, On the local convergence of semis-
mooth Newton methods for linear adn nonlinear second-order cone programs without
srict complementarity, SIAM journal on optimization, vol. 20, pp. 297-320, 2009.
[44] M. P. Kenedy and L. O. Chua, Neural network for nonlinear programming,
IEEE Transactions on Circuits and System, vol. 35, pp. 554-562, 1988.
[45] C. H. Ko, J.-S. Chen and C. Y. Yang, Recurrent neural network for solving
second-order cone programming, Neurocomputing, vol. 74, pp. 3646-3653, 2011.
[46] C. Kanzow, Nonlinear complementarity as unconstrained optimization, Journal of
Optimization Theory and Applications, vol. 88, pp. 139-155, 1996.
[47] C. Kanzow, N. Yamashita and M. Fukushima, New NCP-functions and their
properties, Journal of Optimization Theory and Applications, vol. 94, pp. 115-135,
1997.
[48] C. Kanzow and M. Fukushima Equivalence of the generalized complementarity
problem to dierentiable unconstrained minimization, Journal of Optimization Theory
and Applications, vol. 90, pp. 581-603, 1996.
[49] H. K. Khalil Nonlinear System, Upper Saddle River, NJ: Prentice Hall, 1996.
[50] M. Kojima, S. Shindo, Extensions of Newton and quasi-Newton methods to sys-
tems of PC1 equations, Journal of Operations Research Society of Japan, vol. 29, pp.
352-374, 1986.
[51] L. Z. Liao, H. Qi and L. Qi, Solving nonlinear complementarityproblems with
neural network: a reformulation method approach, Journal of Computational and
Applied Mathematics, vol. 131, pp. 342-359, 2001.
[52] D. R. Liu, D. Wang and X. Yang, An inerative adaptivedynamic programming
algorithm for optimal control of unknoe discrete-time nonlinear systems with con-
strained inputs, Information Science, vol. 220, pp. 331-342, 2013.
[53] P. F. Ma, J.-S. Chen, C. H. Huang and C. H. Ko, Discovery of new comple-
mentarity functions for NCP and SOCCP, submitted manuscript, 2017.
[54] O. L. Mangasarian, Equivalence of the Complementarity Problem to a System
of Nonlinear Equations, SIAM Journal on Applied Mathematics, vol. 31, pp. 89-92,
1976.
[55] R. K. Miller and A. N. Michel, Ordinary Dierential Equations, Academic
Press, 1982.
[56] X. H. Miao, J.-S. Chen and C. H. Ko, A neural network based on the general-
ized FB function for nonlinear convex programs with second-order cone constraints,
Neurocomputing, vol. 203, pp. 62-72, 2016.
[57] S-K. Oh, W. Pedrycz and S-B. Roh Genetically optimized fuzzy polynomial
neural networks with fuzzy set-based polynomial neurons, Information Sciences, vol.
176, pp. 3490-3519, 2006.
[58] S. H. Pan and J.-S. Chen, A semismooth Newton method for SOCCP based on a
one-parameter class of SOC complementarity functions, Computational Optimization
and Applications, vol. 45, pp. 59-88, 2010.
[59] J.-S. Pang, Newton's Method for B-dierentiable Equations, Mathematics of Op-
erations Research, vol. 15, pp. 311-341, 1990.
[60] J.-S. Pang and D. Chan, Iterative methods for variational and complemantarity
problems, Mathematics Programming, vol. 27, 99. 284-313, 1982.
[61] D. Sun and L. Qi, On NCP-functions, Computational Optimization and Applica-
tions, vol. 13, pp. 201-220, 1999.
[62] A. Shortt, J. Keating, L. Monlinier and C. Pannell Optical implementa-
tion of the Kak neural network, Information Sciences, vol. 171, pp. 273-287, 2005.
[63] J. H. Sun, J.-S. Chen and C. H. Ko, Neoral network for solving second-order
cone constrained variational inequality problem, Computational Optimization and Ap-
plication, vol. 5, pp. 743-648, 2012.
[64] H. Y. Tsai and J.-S. Chen, Geometric views of the generalized Fischer-
Burmeister function and its induced merit function, Applied Mathematics and Com-
putation, vol. 237, pp. 31-59, 2014.
[65] D. W. Tank and J. J. Hopfield, Simple neural optimization network: an A/D
converter, signal decision circuit and a linear programming circuit, IEEE Transactions
on Circuits and Systems, vol. 33, pp. 533-541, 1986.
[66] P. Tseng Global behaviour of a class of merit functions for the nonlinear comple-
mentarity problem, Journal of Optimization Theory and Applications, vol. 89, pp.
17-37, 1996.
[67] L. T. Watson, Solving the nonlinear complementarity problem by a homotopy
method, SIAM Journal on Control and Optimization, vol. 17, pp. 36-46, 1979.
[68] S. J. Wright, An infeasible-interior-point algorithm for linear complementarity
problems, Mathematical Programming, vol. 67, pp. 29-51, 1994.
[69] Y. Xia, H. Leung and J. Wang, A projection neural network and its application
to constrained optimization problems, IEEE Transactions on Circuits and Systems-I,
vol. 49, pp. 447-458, 2002.
[70] Y. Xia, H. Leung and J. Wang A general projection neural network for solving
monotone variational inequalities and related optimization problems, IEEE Transac-
tions on Neural Networks, vol. 15, pp. 318-328, 2004.
[71] Y. Xia, H. Leung and J. Wang A recurrent neural network for solving nonlinear
convex programs subject to linear constraints, IEEE Transactions on Neural Networks,
vol. 16, pp. 379-386, 2005.
[72] N. Yamashita and M. , On stationary points of the implict Lagrangian for non-
linear complementarity problems, Journal of Optimization Theory and Applications,
vol. 84, pp. 653-663, 1995.
[73] N. Yamashita and M. Fukushima, Modied Newton methods for solving a semis-
mooth reformulation of monotone complementarity problems, Mathematical Program-
ming, vol. 76, pp. 469-491, 1997.
[74] M. Yashtini and A. Malek Solving complementarity and variational inequalities
problems using neural networks, Applied Mathematics and Computation, vol. 190,
pp. 216-230, 2007.
[75] S. H. Zak, V. Upatising and S. Hui Solving linear programming problems with
neural networks: a comparative study, IEEE Transactions on Neural Networks, vol.
6, pp. 94-104, 1995.
[76] G. Zhang A neural network ensemble method with jittered training data for time
series forecasting, Information Sciences, vol. 177, pp. 5329-5340, 2007.