Approximate global minimizers to pairwise interaction problems via convex relaxation

We present a new approach for systematically computing approximate global minimizers to a large class of pairwise interaction problems defined over probability distributions. The approach predicts candidate global minimizers, with a recovery guarantee, that are sometimes exact, and often within a few percent of the optimum energy (under appropriate normalization of the energy). The procedure relies on a convex relaxation of the pairwise energy that exploits translational symmetry, followed by a recovery procedure that minimizes a relative entropy. In the convex relaxation one obtains a linear programming problem over convex cones that is more efficient, in both space and time, to solve than semi-definite programming techniques. We demonstrate the approach in a periodic domain for examples arising from models in materials, social phenomena, flocking, or many particle physical systems. The examples are computed in dimensions one and two, and generate solutions with both discrete, continuous structures as well as lattices. The structure of the convex relaxation also yields an optimal dual decomposition for the interaction potential.