×

Approximate global minimizers to pairwise interaction problems via convex relaxation. (English) Zbl 1386.49014

Summary: 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.

MSC:

49J45 Methods involving semicontinuity and convergence; relaxation
49M30 Other numerical methods in calculus of variations (MSC2010)

Software:

Wirtinger Flow
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Ahmed, B. Recht, and J. Romberg, {\it Blind deconvolution using convex programming}, IEEE Trans. Inform. Theory, 60 (2013), pp. 1711-1732. · Zbl 1360.94057
[2] B. Ames and S. Vavasis, {\it Convex optimization for the planted k-disjoint-clique problem}, Math. Program., 143 (2014), pp. 299-337. · Zbl 1291.90194
[3] D. Balagué, J. Carrillo, T. Laurent, and G. Raoul, {\it Dimensionality of local minimizers of the interaction energy}, Arch. Ration. Mech. Anal., 209 (2013), pp. 1055-1088. · Zbl 1311.49053
[4] D. Balagué, J. Carrillo, and Y. Yao, {\it Confinement for repulsive-attractive kernels}, Discrete Contin. Dyn. Syst. Ser. B, 19 (2014), pp. 1227-1248. · Zbl 1304.35703
[5] A. J. Bernoff and C. M. Topaz, {\it Nonlocal aggregation models: A primer of swarm equilibria}, SIAM Rev., 55 (2013), pp. 709-747. · Zbl 1282.35003
[6] S. Boyd and L. Vandenberghe, {\it Convex Optimization}, Cambridge University Press, Cambridge, 2004. · Zbl 1058.90049
[7] R. Burachik and V. Jeyakumar, {\it A simple closure condition for the normal cone intersection formula}, Proc. Amer. Math. Soc., 133 (2005), pp. 1741-1748. · Zbl 1065.46055
[8] J. A. Can̈izo, J. A. Carrillo, and F. S. Patacchini, {\it Existence of compactly supported global minimisers for the interaction energy}, Arch. Ration. Mech. Anal., 217 (2015), pp. 1197-1217. · Zbl 1317.82010
[9] E. Candès and X. Li, {\it Solving quadratic equations via phaselift when there are about as many equations as unknowns}, Found. Comput. Math., 14 (2014), pp. 1017-1026. · Zbl 1312.90054
[10] E. Candès, X. Li, and M. Soltanolkotabi, {\it Phase retrieval via Wirtinger flow: Theory and algorithms}, IEEE Trans. Inform. Theory, 61 (2015), pp. 1985-2007. · Zbl 1359.94069
[11] E. Candès and T. Tao, {\it The power of convex relaxation: Near-optimal matrix completion}, IEEE Trans. Inform. Theory, 56 (2010), pp. 2053-2080. · Zbl 1366.15021
[12] J. Carrillo, A. Figalli, and F. Patacchini, {\it Geometry of minimizers for the interaction energy with mildly repulsive potentials}, Ann. Inst. H. Poincaré Anal. Non Linéaire, 34 (2016), pp. 1299-1308, . · Zbl 1408.49035
[13] J. A. Carrillo, M. Chipot, and Y. Huang, {\it On global minimizers of repulsive-attractive power-law interaction energies}, R. Soc. Phil. Trans. Lond. A Math. Phys. Eng. Sci., 372 (2014), 0399, . · Zbl 1353.49002
[14] J. A. Carrillo, D. Slepc̆ev, and L. Wu, {\it Nonlocal-interaction equations on uniformly prox-regular sets}, Discrete Contin. Dyn. Syst., 36 (2016), pp. 1209-1247. · Zbl 1353.35110
[15] R. Choksi, R. Fetecau, and I. Topaloglu, {\it On minimizers of interaction functionals with competing attractive and repulsive potentials}, Ann. Inst. H. Poincaré Anal. Non Linéaire, 32 (2015), pp. 1283-1305. · Zbl 1329.49019
[16] H. Cohn, A. Kumar, and A. Schurmann, {\it Ground states and formal duality relations in the Gaussian core model}, Phys. Rev. E (3), 80 (2009), 061116.
[17] M. A. Cotter, {\it Hard spherocylinders in an anisotropic mean field: A simple model for a nematic liquid crystal}, J. Chem. Phys., 66 (1977), pp. 1098-1106.
[18] K. Craig and I. Topaloglu, {\it Convergence of regularized nonlocal interaction energies}, SIAM J. Math. Anal., 48 (2016), pp. 34-60. · Zbl 1334.49040
[19] L. Demanet and P. Hand, {\it Scaling law for recovering the sparsest element in a subspace}, Inf. Inference, 3 (2014), pp. 295-309. · Zbl 06840288
[20] W. E and D. Li, {\it On the crystallization of 2d hexagonal lattices}, Comm. Math. Phys., 286 (2009), pp. 1099-1140. · Zbl 1180.82191
[21] M. Emelianenko, Z.-K. Liu, and Q. Du, {\it A new algorithm for the automation of phase diagram calculation}, Comput. Mater. Sci., 35 (2006), pp. 61-74.
[22] B. Farmer, S. Esedoḡlu, and P. Smereka, {\it Crystallization for a Brenner-like potential}, Comm. Math. Phys., 349 (2016), pp. 1029-1061, . · Zbl 1381.74044
[23] C. Floudas, {\it Deterministic Global Optimization, Theory, Methods and Applications}, Kluwer Academic, Dordrecht, the Netherlands, 2000.
[24] G. B. Folland, {\it Real Analysis: Modern Techniques and Their Applications}, 2nd ed., Wiley, New York, 1999. · Zbl 0924.28001
[25] M. Goemans and D. Williamson, {\it Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[26] J.-P. Harvey, G. Eriksson, D. Orban, and P. Chartrand, {\it Global minimization of the Gibbs energy of multicomponent systems involving the presence of order/disorder phase transitions}, Amer. J. Sci., 313 (2013), pp. 199-241.
[27] R. C. Heitmann and C. Radin, {\it The ground state for sticky disks}, J. Stat. Phys., 22 (1980), pp. 281-287.
[28] J.-B. Hiriart-Urruty and A. Seeger, {\it A variational approach to copositive matrices}, SIAM Rev., 52 (2010), pp. 593-629. · Zbl 1207.15037
[29] M. Holmes-Cerfon, S. J. Gortler, and M. P. Brenner, {\it A geometrical approach to computing energy landscapes from short-ranged potentials}, Proc. Natl. Acad. Sci. USA, 110 (2013), pp. E5-E14.
[30] K. Jaganathan, S. Oymak, and B. Hassibi, {\it Recovery of sparse 1d signals from the magnitudes of their Fourier transform}, 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), IEEE, Piscataway, NJ, (2012), pp. 1473-1477.
[31] W. Jones and W. J. Thron, {\it Continued Fractions. Analytic Theory and Applications}, Encyclopaedia of Math. Appl. 11, Addison-Wesley, Reading, MA, 1980. · Zbl 0445.30003
[32] R. Lai, J. Liu, and S. Osher, {\it Density matrix minimization with \(ℓ_1\) regularization}, Comm. Math. Sci., 13 (2015), pp. 2097-2117. · Zbl 1327.65110
[33] A. J. Leverentz, C. M. Topaz, and A. J. Bernoff, {\it Asymptotic dynamics of attractive-repulsive swarms}, SIAM J. Appl. Dyn. Syst., 8 (2009), pp. 880-908. · Zbl 1168.92045
[34] M. Locatelli and F. Schoen, {\it Efficient algorithms for large scale global optimization: Lennard-Jones clusters}, Comput. Optim. Appl., 26 (2003), pp. 173-190. · Zbl 1047.90050
[35] M. Locatelli and F. Schoen, {\it Global Optimization: Theory, Algorithms and Applications}, MOS-SIAM Ser. Optim., SIAM, Philadelphia, 2013. · Zbl 1286.90003
[36] J. Lu and F. Otto, {\it An isoperimetric problem with Coulomb repulsion and attraction to a background nucleus}, preprint, arXiv:1508.07172, 2015.
[37] C. D. Maranas and C. A. Floudas, {\it Global minimum potential energy conformations of small molecules}, J. Global. Optim., 4 (1994), pp. 135-170. · Zbl 0797.90114
[38] E. Marcotte, F. Stillingerb, and S. Torquato, {\it Optimized monotonic convex pair potentials stabilize low-coordinated crystals}, Soft Matter, 7 (2011), pp. 2332-2335.
[39] P. Massart, {\it Concentration Inequalitites and Model Selection}, Lecture Notes in Math. 1896, Springer, Berlin, 2007.
[40] A. Mogilner, L. Edelstein-Keshet, L. Bent, and A. Spiros, {\it Mutual interactions, potentials, and individual distance in a social aggregation}, J. Math. Biol., 47 (2003), pp. 353-389. · Zbl 1054.92053
[41] S. Motsch and E. Tadmor, {\it Heterophilious dynamics enhances consensus}, SIAM Rev., 56 (2014), pp. 577-621. · Zbl 1310.92064
[42] Y. Nesterov, H. Wolkowicz, and Y. Ye, {\it Semidefinite programming relaxations of nonconvex quadratic optimization}, in Handbook of Semidefinite Programming, Vol. 27, Springer, 2000, pp. 361-419. · Zbl 0957.90528
[43] M. Nouralishahi, C. Wu, and L. Vandenberghe, {\it Model calibration for optical lithography via semidefinite programming}, Optim. Eng., 9 (2008), pp. 19-35.
[44] Onsager, {\it The effects of shape on the interaction of colloidal particles}, Ann. N.Y. Acad. Sci., 51 (1949), pp. 627-659.
[45] C. Radin, {\it The ground state for soft disks}, J. Stat. Phys., 26 (1981), pp. 365-373.
[46] M. Rechtsman, F. Stillinger, and S. Torquato, {\it Optimized interactions for targeted self-assembly: Application to a honeycomb lattice}, Phys. Rev. Lett., 95 (2005), 228301.
[47] T. Rockafellar, {\it Convex Analysis}, Princeton Math. Ser. 28, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[48] W. Rudin, {\it Real and Complex Analysis}, 3rd ed., McGraw-Hill, Singapore, 1987. · Zbl 0925.00005
[49] A. S. Schneider, C. J. Horowitz, J. Hughto, and D. K. Berry, {\it Nuclear pasta formation}, Phys. Rev. C (3), 88 (2013), 065807.
[50] T. Schulz and D. Snyder, {\it Image recovery from correlations}, J. Optical. Soc. Amer. A, 9 (1992), pp. 1266-1272.
[51] T. Schulz and D. Voelz, {\it Signal recovery from autocorrelation and cross-correlation data}, J. Optical. Soc. Amer. A, 22 (2005), pp. 616-624.
[52] D. Shirokoff, R. Choksi, and J.-C. Nave, {\it Sufficient conditions for global minimality of metastable states in a class of non-convex functionals: A simple approach via quadratic lower bounds}, J. Nonlinear Sci., 25 (2015), pp. 539-582. · Zbl 1317.49023
[53] R. Simione, D. Slepc̆ev, and I. Topaloglu, {\it Existence of ground states of nonlocal-interaction energies}, J. Stat. Phys., 159 (2015), pp. 972-986. · Zbl 1328.82016
[54] A. Sütö, {\it Crystalline ground states for classical particles}, Phys. Rev. Lett., 95 (2005), 265501.
[55] A. Sütö, {\it From bcc to fcc: Interplay between oscillating long-range and repulsive short-range forces}, Phys. Rev. B (3), 74 (2006), 104117.
[56] A. Sütö, {\it Ground state at high density}, Comm. Math. Phys., 305 (2011), pp. 657-710. · Zbl 1226.82014
[57] F. Theil, {\it A proof of crystallization in two dimensions}, Comm. Math. Phys., 262 (2006), pp. 209-236. · Zbl 1113.82016
[58] S. Torquato, {\it Necessary conditions on realizable two-point correlation functions of random media}, Ind. Eng. Chem. Res., 45 (2006), pp. 6923-6928.
[59] J. von Brecht, D. Uminsky, T. Kolokolnikov, and A. Bertozzi, {\it Predicting pattern formation in particle interactions}, Math. Models Methods Appl. Sci., 22 (2012), 1140002. · Zbl 1252.35056
[60] I. Waldspurger, A. d’Aspremont, and S. Mallat, {\it Phase recovery, maxcut and complex semidefinite programming}, Math. Program., 149 (2015), pp. 47-81. · Zbl 1329.94018
[61] X. R. Wang, J. M. Miller, J. Lizier, M. Prokopenko, and L. Rossi, {\it Quantifying and tracing information cascades in swarms}, PLoS ONE, 7 (2012), e40084.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.