Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)
On Using Neural Networks for Solving Linear Programming Problems
Leonardo Valente Ferreira
April/2002
Advisors: |
Eugenius Kaszkurewicz
Amit Bhaya
|
Department: |
Eletrical Engineering |
Artificial neural networks for solving different variants of linear programming problems are proposed and analysed. An energy function with an exact penalty term is associated to each variant and leads to a discontinuous dynamic gradient system model of an artificial neural network.
The objective is to derive conditions that the network must satisfy in order to ensure convergence to the solution of the linear programming problems. This objective is attained by representing the neural networks in a Persidskii type form and using an associated diagonal type Liapunov function.
The linear programming problems are also studied by using winner-take-all subnetworks, which are abtained by associating to each variant an energy function that produces discontinuous dynamic gradient type systems, containing a controller that has the characteristic of a winner-take-all function. Network convergence is analysed, and conditions that the network gains must satisfy in order 0 ensure convergence to the solution set of the linear programming problems are also derived, providing sufficient conditions in terms of the network gains, that ensure convergence to the solution set of the original linear programming problem.