Approximate Global Minimizers to Pairwise Interaction Problems via Convex Relaxation
Approximate Global Minimizers to Pairwise Interaction Problems via Convex Relaxation
复制标题
DOI：
10.1137/16m1069146
复制
发表时间：
2018-01-01
影响因子：
2.1
通讯作者：
Shirokoff, David
中科院分区：
文献类型：
--
作者：
Bandegi, Mandi;Shirokoff, David
我们提出了一种新的方法来计算近似的全局极小值的一个大类的非局部两两相互作用的问题定义的概率分布。该方法预测候选全局最小值，具有恢复保证，有时是精确的，并且通常在最佳能量的百分之几以内（在适当的能量归一化下）。该过程依赖于一个凸松弛的成对能量，利用平移对称性，其次是恢复过程，最大限度地减少相对熵。凸松弛的数值离散产生凸锥上的线性规划问题，可以使用众所周知的方法来解决。该方法的一个优点是，它提供了一个非凸二次变分问题的全局极小的充分条件，在一个线性的，凸的，概率密度的自相关优化问题的形式。我们展示了在一个周期域的方法所产生的材料，社会现象和植绒模型的例子。当Dirac质量格点求解凸松弛时，该方法也能精确地恢复全局极小值。松弛的一个重要副产品是成对能量泛函分解成凸泛函和非凸泛函的和。我们观察到，在某些情况下，分解的非凸分量可以用来表征恢复极小的支持。
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.