Convergence of Neural Networks for Programming Problems via a Nonsmooth Łojasiewicz Inequality
Authors:
- Mauro FortiMFMauro Forti
- Paolo NistriPNPaolo Nistri
- Marc QuincampoixMQMarc Quincampoix
- 13 November 2006
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 17 (6) , 1471-1486
Abstract
This paper considers a class of neural networks (NNs) for solving linear programming (LP) problems, convex quadratic programming (QP) problems, and nonconvex QP problems where an indefinite quadratic objective function is subject to a set of affine constraints. The NNs are characterized by constraint neurons modeled by ideal diodes with vertical segments in their characteristic, which enable to implement an exact penalty method. A new method is exploited to address convergence of trajectories, which is based on a nonsmooth Lstrokojasiewicz inequality for the generalized gradient vector field describing the NN dynamics. The method permits to prove that each forward trajectory of the NN has finite length, and as a consequence it converges toward a singleton. Furthermore, by means of a quantitative evaluation of the Lstrokojasiewicz exponent at the equilibrium points, the following results on convergence rate of trajectories are established: 1) for nonconvex QP problems, each trajectory is either exponentially convergent, or convergent in finite time, toward a singleton belonging to the set of constrained critical points; 2) for convex QP problems, the same result as in 1) holds; moreover, the singleton belongs to the set of global minimizers; and 3) for LP problems, each trajectory converges in finite time to a singleton belonging to the set of global minimizers. These results, which improve previous results obtained via the Lyapunov approach, are true independently of the nature of the set of equilibrium points, and in particular they hold even when the NN possesses infinitely many nonisolated equilibrium pointsKeywords
This publication has 21 references indexed in Scilit:
- A Recurrent Neural Network for Solving Nonlinear Convex Programs Subject to Linear ConstraintsIEEE Transactions on Neural Networks, 2005
- Generalized Neural Network for Nonsmooth Nonlinear Programming ProblemsIEEE Transactions on Circuits and Systems I: Regular Papers, 2004
- A Neural Network for a Class of Convex Quadratic Minimax Problems With ConstraintsIEEE Transactions on Neural Networks, 2004
- Deriving Sufficient Conditions for Global Asymptotic Stability of Delayed Neural Networks via Nonsmooth AnalysisIEEE Transactions on Neural Networks, 2004
- An analysis of a class of neural networks for solving linear programming problemsIEEE Transactions on Automatic Control, 1999
- Solving linear programming problems with neural networks: a comparative studyIEEE Transactions on Neural Networks, 1995
- Lyapunov stability theory of nonsmooth systemsIEEE Transactions on Automatic Control, 1994
- Nonlinear switched capacitor 'neural' networks for optimization problemsIEEE Transactions on Circuits and Systems, 1990
- Neural networks for nonlinear programmingIEEE Transactions on Circuits and Systems, 1988
- Necessary and sufficient conditions for a penalty method to be exactMathematical Programming, 1975