Optimization algorithms to compute approximate solutions to the Max-Cut problem
These are codes from 2016 used for the experiments in the following paper:
N. Boumal, V. Voroninski and A. S. Bandeira,
The non-convex Burer-Monteiro approach works on smooth semidefinite programs,
in the proceedings of NIPS 2016.
We followed up with more theory in another paper:
N. Boumal, V. Voroninski and A. S. Bandeira,
Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs,
in Communications on Pure and Applied Mathematics, 2019.
Usage:
- Install Manopt, SDPLR and CVX (or a subset, depending on which methods you want to test)
- Make sure they are all on your Matlab path
- Run rudytest.m for the actual experiments (edit it first to choose which graphs to run on etc.)
- Run rudytest_to_table.m (this produces rudytable.tex with latex code for a table of results; without header though: see the paper)
Uploaded to github on March 25, 2024.