Lasserre Hierarchy: SOS Relaxations, Root System A_n, and Lattice Symmetry — E8 Intelligence Research

Abstract

FINDING: Lasserre hierarchy (sum-of-squares SDP) provides a convergent sequence of semidefinite relaxations for polynomial optimization, with strong links to root system A_n and lattice symmetry. MATH: - Lasserre hierarchy: For polynomial optimization \( \min_{x \in K} p(x) \), the \( r \)-th relaxation solves an SDP of size \( O(n^{2r}) \) using moment matrices \( M_r(y) \succeq 0 \) and localizing matrices. - Sum-of-squares (SOS) representation: A polynomial \( f(x) \) is SOS if \( f(x) = \sum_i q_i(x)^2 \). The hierarchy uses SOS certificates of nonnegativity. - Root system \( A_n \): The lattice \( A_n = \{ x \in \mathbb{Z}^{n+1} : \sum_i x_i = 0 \} \) with simple roots \( e_i - e_{i+1} \). The symmetry group is the Weyl group \( S_{n+1} \). - Lattice \( D_n \): \( D_n = \{ x \in \mathbb{Z}^n : \sum_i x_i \equiv 0 \pmod{2} \} \), with root system of type \( D_n \). CONNECTION: - The moment matrix \( M_r(y) \) in Lasserre hierarchy has a block-diagonal structure that c Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com