Document Type

Technical Report

Publication Date

1992

Filename

WUCS-92-02.pdf

DOI:

10.7936/K70863N1

Technical Report Number

WUCS-92-02

Abstract

Symmetric networks that are based on energy minimization, such as Boltzmann machines or Hopfield nets, are used extensively for optimization, constraint satisfaction, and approximation of NP-hard problems. Nevertheless, finding a global minimum for the energy function is not guaranteed, and even a local minimum may take an exponential number of steps. We propose and improvement to the standard activation function used for such networks. The improved algorithm guarantees that a global minimum is found in linear time for tree-like subnetworks. The algorithm is uniform and does not assume that the network is a tree. It performs no worse than the standard algorithms for any network topology. In the case where there are trees growing from a cyclic subnetwork, the new algorithm performs better than the standard algorithms by avoiding local minima along the trees and by optimizing the energy of these trees in linear time. The algorithm is self-stabilizing for trees (cycle-free undirected graphs) and remains correct under various scheduling demons. However, no uniform protocol exists to optimze trees under a pure distributed demon and no such protocol exists for cyclic networks under central demon.

Comments

Permanent URL: http://dx.doi.org/10.7936/K70863N1

Download

Share

COinS