1. Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs
- Author
-
Hubert, Evelyne, Metzlaff, Tobias, Moustrou, Philippe, Riener, Cordian, Université Côte d'Azur (UCA), AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), University of Kaiserslautern [Kaiserslautern], Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT), The Arctic University of Norway [Tromsø, Norway] (UiT), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), and European Project: SFB-TRR 195,DFG
- Subjects
Weyl Groups ,Root Systems ,Chebyshev Polynomials ,Set Avoiding Graphs ,Crystallographic Symmetry ,Lattices ,Chromatic Numbers ,Trigonometric Optimization ,Mathematics - Algebraic Geometry ,Optimization and Control (math.OC) ,Spectral Bounds ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] ,Combinatorics (math.CO) ,Mathematics - Optimization and Control ,05C1517B2233C5252C0790C23 ,Algebraic Geometry (math.AG) - Abstract
Trigonometric polynomials are usually defined on the lattice of integers.We consider the larger class of weight and root lattices with crystallographic symmetry.This article gives a new approach to minimize trigonometric polynomials, which are invariant under the associated reflection group.The invariance assumption allows us to rewrite the objective function in terms of generalized Chebyshev polynomials. The new objective function is defined on a compact basic semi-algebraic set, so that we can benefit from the rich theory of polynomial optimization.We present an algorithm to compute the minimum: Based on the Hol-Scherer Positivstellensatz, we impose matrix-sums of squares conditions on the objective function in the Chebyshev basis.The degree of the sums of squares is weighted, defined by the root system. Increasing the degree yields a converging Lasserre-type hierarchy of lower bounds.This builds a bridge between trigonometric and polynomial optimization, allowing us to compare with existing techniques.The chromatic number of a set avoiding graph in the Euclidean space is defined through an optimal coloring.It can be computed via a spectral bound by minimizing a trigonometric polynomial. If the to be avoided set has crystallographic symmetry, our method has a natural application.Specifically, we compute spectral bounds for the first time for boundaries of symmetric polytopes.For several cases, the problem has such a simplified form that we can give analytical proofs for sharp spectral bounds.In other cases, we certify the sharpness numerically.
- Published
- 2023
- Full Text
- View/download PDF