Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT

Wenxuan Huang, Daniil A. Kitchaev, Stephen Dacek, Ziqin Rong, Alexander Urban, Shan Cao, Chuan Luo, Gerbrand Ceder

Published 2016-04-22Version 1

Lattice models, also known as generalized Ising models or cluster expansions, are widely used in many areas of science and are routinely applied to alloy thermodynamics, solid-solid phase transitions, magnetic and thermal properties of solids, and fluid mechanics, among others. However, the problem of finding the true global ground state of a lattice model, which is essential for all of the aforementioned applications, has remained unresolved, with only a limited number of results for highly simplified systems known. In this article, we present the first general algorithm to find the exact ground states of complex lattice models and to prove their global optimality, resolving this fundamental problem in condensed matter and materials theory. We transform the infinite-discrete-optimization problem into a pair of combinatorial optimization (MAX-SAT) and non-smooth convex optimization (MAX-MIN) problems, which provide upper and lower bounds on the ground state energy respectively. By systematically converging these bounds to each other, we find and prove the exact ground state of realistic Hamiltonians whose solutions are completely intractable via traditional methods. Considering that currently such Hamiltonians are solved using simulated annealing and genetic algorithms that are often unable to find the true global energy minimum, and never able to prove the optimality of their result, our work opens the door to resolving long-standing uncertainties in lattice models of physical phenomena.