{"id":"arxiv/2610.20270","url":"https://arxiv.org/abs/2610.20270","tags":["math.OC"],"score":0,"title":"Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS Relaxations","domain":"math.OC","source":"arxiv","authors":["Shucheng Kang"],"reviews":0,"subject":"math.OC","summary":"Pseudo-Boolean optimization -- minimizing a polynomial over $\\{\\pm 1\\}^n$ -- includes MAX-CUT, binary quadratic optimization, and Ising models. The moment-sum-of-squares (Moment-SOS) hierarchy provides certified semidefinite relaxations that are often empirically exact at low order. We ask: once a relaxation is exact, how difficult is the resulting semidefinite program (SDP) to solve with first-order methods? Exactness does not imply regularity. At every order $d \\ge 2$, a unique rank-one moment optimum is primal degenerate; moreover, if one optimal SOS certificate is strictly complementary,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}