MAGNEO-Certified: A Hybrid Framework Combining Gradient-Based Heuristics with Certifiable Spectral Bounds

This repository contains the article “MAGNEO-Certified: A Hybrid Framework Combining Gradient-Based Heuristics with Certifiable Spectral Bounds”, together with the complete source codes used in the experimental section. The paper introduces MAGNEO-Certified, a hybrid optimization framework that bridges fast gradient-based heuristics and rigorous polynomial optimization theory. The method combines: MAGNEO, a continuous relaxation heuristic for NP-hard graph optimization problems based on spectral penalties, and Spectral sum-of-squares (SOS) relaxations developed by Mai, Lasserre, and Magron for polynomial optimization problems (POPs) with the Constant Trace Property (CTP). The MAGNEO energy optimized in the heuristic phase includes non-polynomial spectral terms,$E(X) = f_0(X) - \alpha \ln \det(\mathcal{L}_X^{*} + \epsilon I)- \gamma / \lambda_2(\mathcal{L}_X)+ \beta \sum_{k=2}^{K} (\operatorname{tr}(X^{k}))^{2}.$ where $\mathcal{L}X$ is the graph Laplacian and $\lambda_2(\mathcal{L}X)$ is the Fiedler value.Since such terms are incompatible with polynomial optimization theory, the paper introduces a polynomial relaxation$f_{\mathrm{poly}}(X) = f_0(X)+ \lambda_{\mathrm{spec}}\, P_{\mathrm{spec}}^{\mathrm{poly}}(X)+ \lambda_{\mathrm{bin}}\, P_{\mathrm{bin}}(X),$which enables certification through a spectral SOS hierarchy with convergence rate$f_{\mathrm{poly}}^{*} - \tau_k= O\!\left(\log(k/c)^{-1/c}\right).$ A three-phase algorithm is proposed: MAGNEO exploration using the full non-polynomial energy, Certification via spectral SDP relaxations solved with LMBM, Hybrid refinement using warm-starts and iterative gap reduction. The repository includes both codes used in the experiments: the MAGNEO optimization code implementing the gradient-based heuristic with spectral penalties, and the certification code implementing the polynomial relaxation and spectral SOS bounds via the MLM framework. These codes allow full reproduction of the experimental results, including the gap analysis between the complete non-polynomial objective and its polynomial relaxation. Keywords: Polynomial optimization, spectral relaxations, sum of squares, graph optimization, certified bounds, hybrid algorithms, MAGNEO, LMBM.