| _version_ | 1866901202386550784 |
|---|---|
| author | Ben Ammar Chraiti, Mohamed |
| author_facet | Ben Ammar Chraiti, Mohamed |
| contents | <p>We present SNO (Spectral Neighborhood Optimization), a computationally tractable framework for polynomial optimization on graph-structured problems. SNO combines moment-SOS hierarchies with spectral semidefinite programming methods, building upon the constant trace property (CTP) theory of Mai, Lasserre, and Magron (Math. Prog. Comp., 2023).</p> <p>Key Innovation:<br>The framework introduces polynomial-based connectivity penalties specifically designed for compatibility with Sum-of-Squares (SOS) relaxations. Traditional graph connectivity measures use $\det(L)$ (polynomial degree $n$, computationally infeasible) or $\log\det(L)$ (non-polynomial, incompatible with SOS). SNO replaces these with trace-based polynomial penalties:</p> <p>$$P_{\text{conn}}(X) = -\sum_{r=1}^{R} \alpha_r \text{tr}(L(X)^r)$$</p> <p>where $L(X) = D(X) - X$ is the graph Laplacian. This formulation maintains polynomial structure with controlled degree (typically $R \leq 4$) while providing rigorous spectral interpretation: $\text{tr}(L^r) = \sum_{i=1}^{n} \lambda_i(L)^r$ penalizes small algebraic connectivity $\lambda_{n-1}(L)$.</p> <p>Theoretical Contributions:<br>- Sphere lifting transformations inducing constant trace property with $\text{tr}(P_{m+1,k}M_k(y)P_{m+1,k}) = (1+R^2)^k$<br>- Explicit boundedness conditions: $\inf_{X \in \mathcal{F}} f_{\text{SNO}}(X) > -\infty$ with $|f_{\text{SNO}}(X)| \leq M$<br>- Convergence guarantees with explicit $O(k^{-1/c})$ rates under Nie-Schweighofer theory<br>- Spectral dual formulation: $-\tau_k = \inf_{z \in \mathbb{R}^{m_k}} \{\alpha_k \lambda_1(C_k - \mathcal{A}_k^*(z)) + b_k^\top z\}$ solvable by first-order methods</p> <p>Applications:<br>The framework is validated on canonical problems: Traveling Salesman Problem (TSP) with degree constraints $X\mathbf{1} = 2\mathbf{1}$, form nonnegativity testing $\min_{\|x\|_2=1} p(x)$ for homogeneous polynomials $p \in \mathbb{R}[x]_{2d}$, and copositivity verification $\min_{\|y\|_2^2=1, y \geq 0} y^\top A y$.</p> <p>Computational Advantages:<br>- Complexity: $O(T \cdot \omega_k^2)$ per iteration vs. $O(\omega_k^3)$ for interior-point methods, where $\omega_k = \binom{m+k}{k}$<br>- Demonstrated 5-25× speedup over MOSEK/SDPT3 for equality-constrained problems (Mai et al., 2023)<br>- First-order spectral methods scale to $\omega_k \approx 10^5$ vs. $\omega_k < 10^4$ for interior-point</p> <p>Keywords:<br>Polynomial optimization, Moment-SOS hierarchy, Spectral relaxations, Graph connectivity, Combinatorial optimization, Semidefinite programming, Constant trace property, Traveling salesman problem, Laplacian matrix, Algebraic connectivity</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_18610923 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | SNO: A Polynomial Framework for Graph Optimization via Spectral Relaxations and Moment-SOS Hierarchies Ben Ammar Chraiti, Mohamed <p>We present SNO (Spectral Neighborhood Optimization), a computationally tractable framework for polynomial optimization on graph-structured problems. SNO combines moment-SOS hierarchies with spectral semidefinite programming methods, building upon the constant trace property (CTP) theory of Mai, Lasserre, and Magron (Math. Prog. Comp., 2023).</p> <p>Key Innovation:<br>The framework introduces polynomial-based connectivity penalties specifically designed for compatibility with Sum-of-Squares (SOS) relaxations. Traditional graph connectivity measures use $\det(L)$ (polynomial degree $n$, computationally infeasible) or $\log\det(L)$ (non-polynomial, incompatible with SOS). SNO replaces these with trace-based polynomial penalties:</p> <p>$$P_{\text{conn}}(X) = -\sum_{r=1}^{R} \alpha_r \text{tr}(L(X)^r)$$</p> <p>where $L(X) = D(X) - X$ is the graph Laplacian. This formulation maintains polynomial structure with controlled degree (typically $R \leq 4$) while providing rigorous spectral interpretation: $\text{tr}(L^r) = \sum_{i=1}^{n} \lambda_i(L)^r$ penalizes small algebraic connectivity $\lambda_{n-1}(L)$.</p> <p>Theoretical Contributions:<br>- Sphere lifting transformations inducing constant trace property with $\text{tr}(P_{m+1,k}M_k(y)P_{m+1,k}) = (1+R^2)^k$<br>- Explicit boundedness conditions: $\inf_{X \in \mathcal{F}} f_{\text{SNO}}(X) > -\infty$ with $|f_{\text{SNO}}(X)| \leq M$<br>- Convergence guarantees with explicit $O(k^{-1/c})$ rates under Nie-Schweighofer theory<br>- Spectral dual formulation: $-\tau_k = \inf_{z \in \mathbb{R}^{m_k}} \{\alpha_k \lambda_1(C_k - \mathcal{A}_k^*(z)) + b_k^\top z\}$ solvable by first-order methods</p> <p>Applications:<br>The framework is validated on canonical problems: Traveling Salesman Problem (TSP) with degree constraints $X\mathbf{1} = 2\mathbf{1}$, form nonnegativity testing $\min_{\|x\|_2=1} p(x)$ for homogeneous polynomials $p \in \mathbb{R}[x]_{2d}$, and copositivity verification $\min_{\|y\|_2^2=1, y \geq 0} y^\top A y$.</p> <p>Computational Advantages:<br>- Complexity: $O(T \cdot \omega_k^2)$ per iteration vs. $O(\omega_k^3)$ for interior-point methods, where $\omega_k = \binom{m+k}{k}$<br>- Demonstrated 5-25× speedup over MOSEK/SDPT3 for equality-constrained problems (Mai et al., 2023)<br>- First-order spectral methods scale to $\omega_k \approx 10^5$ vs. $\omega_k < 10^4$ for interior-point</p> <p>Keywords:<br>Polynomial optimization, Moment-SOS hierarchy, Spectral relaxations, Graph connectivity, Combinatorial optimization, Semidefinite programming, Constant trace property, Traveling salesman problem, Laplacian matrix, Algebraic connectivity</p> |
| title | SNO: A Polynomial Framework for Graph Optimization via Spectral Relaxations and Moment-SOS Hierarchies |
| url | https://doi.org/10.5281/zenodo.18610923 |