Statistical mechanics as the underlying theory of 'elastic' and 'neural' optimisations

There is an interesting connection between two, recently popular, methods for finding good approximate solutions to hard optimisation problems, the 'neural' approach of Hopfield and Tank and the elastic-net method of Durbin and Willshaw. They both have an underlying statistical mechanics foundation and can be derived as the leading approximation to the thermodynamic free energy of related physical models. The apparent difference in the form of the two algorithms comes from different handling of constraints when evaluating the thermodynamic partition function. If all the constraints are enforced 'softly', the 'mean-field' approximation to the thermodynamic free energy is just the neural network Lyapunov function. If, on the other hand, half of the constraints are enforced 'strongly', the leading approximation to the thermodynamic free energy is the elastic-net Lyapunov function. Our results have interesting implications for the general problem of mapping optimisation problems to 'neural' and 'elastic' networks, and suggest a natural and systematic way to generalise the elastic-net and 'neural' methods to a large class of hard optimisation problems. We derive a new algorithm of the elastic-net type based on statistical mechanics. It has some of the 'positive' ingredients of the elastic-net method, yet it does not have an intrinsic problem (discussed in this paper) of the original algorithm.