Approximate global minimizers to pairwise interaction problems via convex relaxation
From MaRDI portal
Abstract: 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.
Recommendations
- scientific article; zbMATH DE number 2040634
- A Convex Approach to Minimal Partitions
- Nonconvex minimization related to quadratic double-well energy -- approximation by convex problems
- Global minimization of Markov random fields with applications to optical flow
- Exact relaxations of non-convex variational problems
Cites work
- A proof of crystallization in two dimensions
- A simple closure condition for the normal cone intersection formula
- A variational approach to copositive matrices
- Asymptotic Dynamics of Attractive-Repulsive Swarms
- Blind Deconvolution Using Convex Programming
- Confinement for repulsive-attractive kernels
- Convergence of regularized nonlocal interaction energies
- Convex Analysis
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Crystallization for a Brenner-like potential
- Density matrix minimization with \({\ell}_1\) regularization
- Deterministic global optimization. Theory, methods and applications
- Dimensionality of local minimizers of the interaction energy
- Efficient algorithms for large scale global optimization: Lennard-Jones clusters
- Existence of compactly supported global minimisers for the interaction energy
- Existence of ground states of nonlocal-interaction energies
- Geometry of minimizers for the interaction energy with mildly repulsive potentials
- Global minimum potential energy conformations of small molecules
- Global optimization. Theory, algorithms, and applications
- Ground state at high density
- Heterophilious dynamics enhances consensus
- scientific article; zbMATH DE number 3695547 (Why is no real title available?)
- scientific article; zbMATH DE number 1324223 (Why is no real title available?)
- scientific article; zbMATH DE number 1022658 (Why is no real title available?)
- scientific article; zbMATH DE number 1534299 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Mutual interactions, potentials, and individual distance in a social aggregation
- Nonlocal aggregation models: a primer of swarm equilibria
- Nonlocal-interaction equations on uniformly prox-regular sets
- On global minimizers of repulsive-attractive power-law interaction energies
- On minimizers of interaction functionals with competing attractive and repulsive potentials
- On the crystallization of 2D hexagonal lattices
- Phase recovery, MaxCut and complex semidefinite programming
- Phase retrieval via Wirtinger flow: theory and algorithms
- Predicting pattern formation in particle interactions
- Scaling law for recovering the sparsest element in a subspace
- Solving quadratic equations via phaselift when there are about as many equations as unknowns
- Sufficient conditions for global minimality of metastable states in a class of non-convex functionals: a simple approach via quadratic lower bounds
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
Cited in
(5)- Aggregation-diffusion to constrained interaction: minimizers \& gradient flows in the slow diffusion limit
- Note on crystallization for alternating particle chains
- Minimizing lattice structures for Morse potential energy in two and three dimensions
- On the spectral gap of a square distance matrix
- Approximating particle-based clustering dynamics by stochastic PDEs
This page was built for publication: Approximate global minimizers to pairwise interaction problems via convex relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608088)
