Distribution approximation, combinatorial optimization, and Lagrange-Barrier

In this paper, typical analog combinatorial optimization approaches, such as Hopfield net, Hopfield-Lagrange net, Maximum entropy approach, Lagrange-Barrier approach, are systematically examined from the perspective of learning distribution. The minimization of a combinatorial cost is turned into a procedure of learning a simple distribution to approximate the Gibbs distribution induced from this cost such that both the distributions share a same global peak. From this new perspective, a new general guideline is obtained for developing analog combinatorial optimization approaches. Moreover, the Lagrange-Barrier iterative procedure proposed in Xu (1994) is further elaborated with guaranteed convergence on a feasible solution that satisfies constraints.