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 Introduction 4
2 Preliminaries 12
3 NCP-Functions: Generalized Natural Residual Function 15
3.1 Properties of Generalized Natural Residual Function
phinrp 17
3.2 Geometric View of
phinrp 23
3.3 Other types of NCP-Functions Based on NR and FB function 24
4 Neural Networks for Solving NCP by Smooth NCP-Functions 29
4.1 Background Materials for Stability Analysis 33
4.2 Dynamic System Based on
phinrp 36
4.3 Dynamic Systems Based on
psisnrp and phidfbp 40
4.4 Numerical Experiments 44
5 Neural Networks for Solving SOCQP by Smooth SOC-Complementarity functions 63
5.1 Neural Network Model 64
5.2 Stability Analysis 66
5.3 Two Different Families of Smooth SOC-Complementarity Functions 68
5.4 Numerical Experiments 71
6 Concluding Remarks 81
Bibliography 82

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