Using full parallel Boltzmann Machines for Optimization

Johannes Faassen

           It is well known that synchronously full parallel Boltzmann
           machines do not converge to the minima of the quadratic
           energy but to a so called pseudo energy. So far the pseudo
           energy was treated as a defect disturbing the convergence
           of these Boltzmann machines. Various simulations suggest
           that convergence can be ensured if one reduces the degree
           of parallelism. Another approach that we follow in this
           paper is to map the problem onto the pseudo energy i.e. we
           directly exploit the dynamics of the full parallel Boltzmann
           machine. First we prove that minimizing the pseudo energy is
           NP-hard and derive a simple mapping scheme that allows us to
           reduce an arbitrary quadratic 0-1-problem to the minimization
           of the pseudo energy. After that we present some simulation
           results showing the potential of this approach and compare
           it to the results obtained by Aarts, Korst, and Zwietering.