Discrete Optimization Using Analog Neural Networks with Discontinuous Dynamics
Mathukumalli Vidyasagar · Birkhäuser Basel eBooks · 1996
In this paper, a new type of neural network is presented, that can be used to perform discrete optimization over a set of the form {0, 1} n . Unlike earlier neural networks, this network is characterized by the fact that the dynamics are discontinuous. It is shown that the discontinuous nature of the dynamics makes it possible to carry out quite a thorough analysis of the network trajectories. In particular, it is shown that, in the practically important case where the objective function to be maximized is a multilinear polynomial, almost all trajectories converge to a local maximum of the objective function. Moreover, it is possible to make the trajectories converge within a finite amount of time, and in fact arbitrarily quickly, to a local maximum. The results presented here open the way for the formulation of a suitable complexity theory for analog computation.