Optimization of the Sherrington--Kirkpatrick Hamiltonian
Optimization of the Sherrington--Kirkpatrick Hamiltonian
复制标题
Sherrington--Kirkpatrick 哈密顿量的优化
DOI：
10.1137/20m132016x
复制
发表时间：
2021
影响因子：
1.6
通讯作者：
Montanari, Andrea
中科院分区：
文献类型：
--
作者：
Montanari, Andrea
假设是一个对称随机矩阵，对角线上方具有独立同分布（i.i.d.）高斯项。我们考虑最大化二元向量的问题。用统计物理学的语言来说，这相当于找到自旋玻璃谢林顿-柯克帕特里克模型的基态。 Parisi 通过著名的变分原理描述了该优化问题的渐近值，随后由 Talagrand 证明。我们给出了一种算法，对于任何情况，输出至少是最优值，并且概率收敛为 1。该算法的时间复杂度为。我们将其推广到具有 i.i.d.（但不一定是高斯）项的矩阵，并获得一种算法，该算法可将密集 Erdös-Renyi 随机图的 MAXCUT 计算到一个因子内。作为附带结果，我们证明，在（低）非零温度下，该算法构造了 Thouless--Anderson-Palmer 方程的近似解。
Letbe a symmetric random matrix with independent and identically distributed (i.i.d.) Gaussian entries above the diagonal. We consider the problem of maximizingover binary vectors. In the language of statistical physics, this amounts to finding the ground state of the Sherrington--Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any, outputssuch thatis at leastof the optimum value, with probability converging to one as. The algorithm's time complexity is. We generalize it to matrices with i.i.d., but not necessarily Gaussian, entries, and obtain an algorithm that computes the MAXCUT of a dense Erdös--Renyi random graph to within a factor. As a side result, we prove that, at (low) nonzero temperature, the algorithm constructs approximate solutions of the Thouless--Anderson--Palmer equations.