Paper ID sheet UCL-INMA-2004.902


Continuous dynamical systems that realize discrete optimization on the hypercube

P.-A. Absil, R. Sepulchre,
We study the problem of finding a local minimum of a multilinear function $E$ over the discrete set $\{0,1\}^n$. The search is achieved by a gradient system in $[0,1]^n$ with cost function $E$. Under mild restrictions on the metric, the stable attractors of the gradient system are shown to produce solutions of the problem. Moreover, we make connections with interior point methods for linear programming and with the analog neural network studied by Vidyasagar (1995) in the same context.
Key words
Published in Systems & Control Letters, Volume 52, Issues 3-4, July 2004, Pages 297-304