A Dynamical Systems Perspective on Discrete Optimization

Tong Guanchun, Michael Muehlebach
Proceedings of The 5th Annual Learning for Dynamics and Control Conference, PMLR 211:1373-1386, 2023.

Abstract

We discuss a dynamical systems perspective on discrete optimization. Departing from the fact that many combinatorial optimization problems can be reformulated as finding low energy spin con- figurations in corresponding Ising models, we derive a penalized rank-two relaxation of the Ising formulation. It turns out that the associated gradient flow dynamics exactly correspond to a type of hardware solvers termed oscillator-based Ising machines. We also analyze the advantage of adding angle penalties by leveraging random rounding techniques. Therefore, our work contributes to a rigorous understanding of oscillator-based Ising machines by drawing connections to the penalty method in constrained optimization and providing a rationale for the introduction of sub-harmonic injection locking. Furthermore, we characterize a class of coupling functions between oscillators, which ensures convergence to discrete solutions. This class of coupling functions avoids explicit penalty terms or rounding schemes, which are prevalent in other formulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v211-guanchun23a, title = {A Dynamical Systems Perspective on Discrete Optimization}, author = {Guanchun, Tong and Muehlebach, Michael}, booktitle = {Proceedings of The 5th Annual Learning for Dynamics and Control Conference}, pages = {1373--1386}, year = {2023}, editor = {Matni, Nikolai and Morari, Manfred and Pappas, George J.}, volume = {211}, series = {Proceedings of Machine Learning Research}, month = {15--16 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v211/guanchun23a/guanchun23a.pdf}, url = {https://proceedings.mlr.press/v211/guanchun23a.html}, abstract = {We discuss a dynamical systems perspective on discrete optimization. Departing from the fact that many combinatorial optimization problems can be reformulated as finding low energy spin con- figurations in corresponding Ising models, we derive a penalized rank-two relaxation of the Ising formulation. It turns out that the associated gradient flow dynamics exactly correspond to a type of hardware solvers termed oscillator-based Ising machines. We also analyze the advantage of adding angle penalties by leveraging random rounding techniques. Therefore, our work contributes to a rigorous understanding of oscillator-based Ising machines by drawing connections to the penalty method in constrained optimization and providing a rationale for the introduction of sub-harmonic injection locking. Furthermore, we characterize a class of coupling functions between oscillators, which ensures convergence to discrete solutions. This class of coupling functions avoids explicit penalty terms or rounding schemes, which are prevalent in other formulations.} }
Endnote
%0 Conference Paper %T A Dynamical Systems Perspective on Discrete Optimization %A Tong Guanchun %A Michael Muehlebach %B Proceedings of The 5th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2023 %E Nikolai Matni %E Manfred Morari %E George J. Pappas %F pmlr-v211-guanchun23a %I PMLR %P 1373--1386 %U https://proceedings.mlr.press/v211/guanchun23a.html %V 211 %X We discuss a dynamical systems perspective on discrete optimization. Departing from the fact that many combinatorial optimization problems can be reformulated as finding low energy spin con- figurations in corresponding Ising models, we derive a penalized rank-two relaxation of the Ising formulation. It turns out that the associated gradient flow dynamics exactly correspond to a type of hardware solvers termed oscillator-based Ising machines. We also analyze the advantage of adding angle penalties by leveraging random rounding techniques. Therefore, our work contributes to a rigorous understanding of oscillator-based Ising machines by drawing connections to the penalty method in constrained optimization and providing a rationale for the introduction of sub-harmonic injection locking. Furthermore, we characterize a class of coupling functions between oscillators, which ensures convergence to discrete solutions. This class of coupling functions avoids explicit penalty terms or rounding schemes, which are prevalent in other formulations.
APA
Guanchun, T. & Muehlebach, M.. (2023). A Dynamical Systems Perspective on Discrete Optimization. Proceedings of The 5th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 211:1373-1386 Available from https://proceedings.mlr.press/v211/guanchun23a.html.

Related Material