  We present a new approach for computing approximate global minimizers to a
large class of non-local 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. Numerical discretizations of the convex relaxation yield a
linear programming problem over convex cones that can be solved using
well-known methods. One advantage of the approach is that it provides
sufficient conditions for global minimizers to a non-convex quadratic
variational problem, in the form of a linear, convex, optimization problem for
the auto-correlation of the probability density. We demonstrate the approach in
a periodic domain for examples arising from models in materials, social
phenomena and flocking. The approach also exactly recovers the global minimizer
when a lattice of Dirac masses solves the convex relaxation. An important
by-product of the relaxation is a decomposition of the pairwise energy
functional into the sum of a convex functional and non-convex functional. We
observe that in some cases, the non-convex component of the decomposition can
be used to characterize the support of the recovered minimizers.
