Abstract
We consider the complexity of random ferromagnetic landscapes on the hypercube {±1}N given by Ising models on the complete graph with i.i.d. non-negative edge-weights. This includes, in particular, the case of Bernoulli disorder corresponding to the Ising model on a dense random graph G(N, p). Previous results had shown that, with high probability as N→ ∞, the gradient search (energy-lowering) algorithm, initialized uniformly at random, converges to one of the homogeneous global minima (all-plus or all-minus). Here, we devise two modified algorithms tailored to explore the landscape at near-zero magnetizations (where the effect of the ferromagnetic drift is minimized). With these, we numerically verify the landscape complexity of random ferromagnets, finding a diverging number of (1-spin-flip-stable) local minima as N→ ∞. We then investigate some of the properties of these local minima (e.g., typical energy and magnetization) and compare to the situation where the edge-weights are drawn from a heavy-tailed distribution.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 576-596 |
| Number of pages | 21 |
| Journal | Journal of Statistical Physics |
| Volume | 180 |
| Issue number | 1-6 |
| DOIs | |
| State | Published - Sep 1 2020 |
Funding
This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise. The research of EYS, RG and CMN was supported in part by US NSF grant DMS-1507019. RG thanks the Miller Institute for Basic Research in Science, University of California Berkeley, for its support during some of the time when this work was completed. DLS thanks the Aspen Center for Physics, supported by National Science Foundation grant PHY-1607611, where part of this work was performed. The authors thank an anonymous referee for several useful suggestions, which have been incorporated in the current version of the paper. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise. The research of EYS, RG and CMN was supported in part by US NSF grant DMS-1507019. RG thanks the Miller Institute for Basic Research in Science, University of California Berkeley, for its support during some of the time when this work was completed. DLS thanks the Aspen Center for Physics, supported by National Science Foundation grant PHY-1607611, where part of this work was performed. The authors thank an anonymous referee for several useful suggestions, which have been incorporated in the current version of the paper.
Keywords
- Complex landscapes
- Constrained optimization
- Disordered ferromagnets
- Dynamics in dilute Curie–Weiss models
- Landscape search algorithms
- Local MINCUT
- Local energy minima
- Mean-field ferromagnets
- Metastable traps
- Quenched disorder
ASJC Scopus subject areas
- Statistical and Nonlinear Physics
- Mathematical Physics