Basic Search / Detailed Display

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 ProblemSecond-Order ConeNeural 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: 64Downloads: 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 di erentiability 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 di erent families of smooth NCP or SOCCP-functions. Our goal is to study the stability of the equilibrium with respect to di erent 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 e ffectiveness 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 Diff erent 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-Paci c 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 e ective
    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-
    i cation for In nite 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 di erentiable 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 Di erential 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-di erentiable 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, Modi ed 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.

    下載圖示
    QR CODE