Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT
Lattice models, also known as generalized Ising models or cluster expansions, are widely used in many areas of science and are routinely applied to the study of alloy thermodynamics, solid-solid phase transitions, magnetic and thermal properties of solids, fluid mechanics, and others. However, the p...
| Main Authors: | , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2016
|
| Online Access: | http://hdl.handle.net/1721.1/105425 https://orcid.org/0000-0002-1459-3770 https://orcid.org/0000-0003-2309-3644 https://orcid.org/0000-0002-7737-1278 https://orcid.org/0000-0002-8987-8500 |
| _version_ | 1826207331479715840 |
|---|---|
| author | Urban, Alexander Luo, Chuan Huang, Wenxuan Kitchaev, Daniil Andreevich Dacek, Stephen Thomas Cao, Shan Ceder, Gerbrand Rong, Ziqin |
| author2 | Massachusetts Institute of Technology. Department of Materials Science and Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Materials Science and Engineering Urban, Alexander Luo, Chuan Huang, Wenxuan Kitchaev, Daniil Andreevich Dacek, Stephen Thomas Cao, Shan Ceder, Gerbrand Rong, Ziqin |
| author_sort | Urban, Alexander |
| collection | MIT |
| description | Lattice models, also known as generalized Ising models or cluster expansions, are widely used in many areas of science and are routinely applied to the study of alloy thermodynamics, solid-solid phase transitions, magnetic and thermal properties of solids, fluid mechanics, and others. However, the problem of finding and proving the global ground state of a lattice model, which is essential for all of the aforementioned applications, has remained unresolved for relatively complex practical systems, with only a limited number of results for highly simplified systems known. In this paper, we present a practical and general algorithm that provides a provable periodically constrained ground state of a complex lattice model up to a given unit cell size and in many cases is able to prove global optimality over all other choices of unit cell. We transform the infinite-discrete-optimization problem into a pair of combinatorial optimization (MAX-SAT) and nonsmooth 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 may find and prove the exact ground state of realistic Hamiltonians whose exact solutions are difficult, if not impossible, to obtain via traditional methods. Considering that currently such practical Hamiltonians are solved using simulated annealing and genetic algorithms that are often unable to find the true global energy minimum and inherently cannot prove the optimality of their result, our paper opens the door to resolving longstanding uncertainties in lattice models of physical phenomena. An implementation of the algorithm is available at https://github.com/dkitch/maxsat-ising. |
| first_indexed | 2024-09-23T13:47:40Z |
| format | Article |
| id | mit-1721.1/105425 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:47:40Z |
| publishDate | 2016 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1054252022-10-01T17:13:45Z Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT Urban, Alexander Luo, Chuan Huang, Wenxuan Kitchaev, Daniil Andreevich Dacek, Stephen Thomas Cao, Shan Ceder, Gerbrand Rong, Ziqin Massachusetts Institute of Technology. Department of Materials Science and Engineering Huang, Wenxuan Kitchaev, Daniil Andreevich Dacek, Stephen Thomas Cao, Shan Ceder, Gerbrand Rong, Ziqin Lattice models, also known as generalized Ising models or cluster expansions, are widely used in many areas of science and are routinely applied to the study of alloy thermodynamics, solid-solid phase transitions, magnetic and thermal properties of solids, fluid mechanics, and others. However, the problem of finding and proving the global ground state of a lattice model, which is essential for all of the aforementioned applications, has remained unresolved for relatively complex practical systems, with only a limited number of results for highly simplified systems known. In this paper, we present a practical and general algorithm that provides a provable periodically constrained ground state of a complex lattice model up to a given unit cell size and in many cases is able to prove global optimality over all other choices of unit cell. We transform the infinite-discrete-optimization problem into a pair of combinatorial optimization (MAX-SAT) and nonsmooth 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 may find and prove the exact ground state of realistic Hamiltonians whose exact solutions are difficult, if not impossible, to obtain via traditional methods. Considering that currently such practical Hamiltonians are solved using simulated annealing and genetic algorithms that are often unable to find the true global energy minimum and inherently cannot prove the optimality of their result, our paper opens the door to resolving longstanding uncertainties in lattice models of physical phenomena. An implementation of the algorithm is available at https://github.com/dkitch/maxsat-ising. United States. Dept. of Energy (Contract DE-FG02-96ER45571) United States. Office of Naval Research (Contract N00014-14-1-0444) 2016-11-22T19:34:57Z 2016-11-22T19:34:57Z 2016-10 2016-05 2016-10-21T22:00:21Z Article http://purl.org/eprint/type/JournalArticle 2469-9950 2469-9969 http://hdl.handle.net/1721.1/105425 Huang, Wenxuan et al. “Finding and Proving the Exact Ground State of a Generalized Ising Model by Convex Optimization and MAX-SAT.” Physical Review B 94.13 (2016): n. pag. ©2016 American Physical Society https://orcid.org/0000-0002-1459-3770 https://orcid.org/0000-0003-2309-3644 https://orcid.org/0000-0002-7737-1278 https://orcid.org/0000-0002-8987-8500 en http://dx.doi.org/10.1103/PhysRevB.94.134424 Physical Review B Creative Commons Attribution http://creativecommons.org/licenses/by/3.0 authors application/pdf American Physical Society American Physical Society |
| spellingShingle | Urban, Alexander Luo, Chuan Huang, Wenxuan Kitchaev, Daniil Andreevich Dacek, Stephen Thomas Cao, Shan Ceder, Gerbrand Rong, Ziqin Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT |
| title | Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT |
| title_full | Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT |
| title_fullStr | Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT |
| title_full_unstemmed | Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT |
| title_short | Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT |
| title_sort | finding and proving the exact ground state of a generalized ising model by convex optimization and max sat |
| url | http://hdl.handle.net/1721.1/105425 https://orcid.org/0000-0002-1459-3770 https://orcid.org/0000-0003-2309-3644 https://orcid.org/0000-0002-7737-1278 https://orcid.org/0000-0002-8987-8500 |
| work_keys_str_mv | AT urbanalexander findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT luochuan findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT huangwenxuan findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT kitchaevdaniilandreevich findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT dacekstephenthomas findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT caoshan findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT cedergerbrand findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat AT rongziqin findingandprovingtheexactgroundstateofageneralizedisingmodelbyconvexoptimizationandmaxsat |