Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. We study Particle Polynomial Relaxation (PPR), a moment-based nonconvex continuous reformulation possessing an advantageous optimization landscape.