Abstract
We present a new approach for computing approximate global minimizers to a large class of nonlocal 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 nonconvex quadratic variational problem, in the form of a linear, convex, optimization problem for the autocorrelation 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 nonconvex functional. We observe that in some cases, the nonconvex component of the decomposition can be used to characterize the support of the recovered minimizers.
| Original language | American English |
|---|---|
| Pages (from-to) | 417-456 |
| Number of pages | 40 |
| Journal | SIAM Journal on Applied Dynamical Systems |
| Volume | 17 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2018 |
ASJC Scopus subject areas
- Analysis
- Modeling and Simulation
Keywords
- Conic programming
- Convex relaxations
- Flocking
- Global minimizers
- Nonconvex energy
- Pairwise interactions
- Self-assembly
- Semidefinite programming