- Laurent Baratchart (Inria d'Université Cote d'Azur)
- Christine Bachoc (Institut de Mathématiques d’Université de Bordeaux)
- Victor Magron (CNRS LAAS Toulouse)
- Gabriele Nebe (RWTH Aachen University)
- Frédéric Patras (CNRS Université Côte d’Azur)
- Evelyne Hubert (Inria d’Université Côte d’Azur)
This thesis studies the problem of optimizing a trigonometric polynomial with crystallographic symmetry. Optimization of trigonometric polynomials has been subject to many recent works, but a theory for exploiting symmetries has hardly been developed or generalized. We consider the action of a crystallographic group, also known as a Weyl group, on the exponents. This action admits a definition of generalized Chebyshev polynomials. If a trigonometric polynomial is invariant under the action, then it can be written as a sum of generalized Chebyshev polynomial in fundamental invariants.
By rewriting an invariant trigonometric polynomial as a classical polynomial, the region of optimization is transformed into the orbit space of the multiplicative Weyl group action. This orbit space is the image of fundamental invariants and we show that, for the Weyl groups of types An, Bn, Cn, Dn and G2, it is a compact basic semi-algebraic set. Furthermore, we give the describing polynomial inequalities through a positive semi-definite Hermite matrix polynomial.
Concerning the optimization problem, our rewriting approach transforms the trigonometric optimization problem into a classical polynomial optimization problem on a basic semi-algebraic set. To solve such problems, one can apply Lasserre's hierarchy of moment and sum of squares relaxations. We adapt and implement this hierarchy in the basis of generalized Chebyshev polynomials with a new notion of degree. The optimal value of the original trigonometric optimization problem is then approximated through solutions of semi-definite programs, which are solved numerically.
In classical polynomial optimization and other applications, symmetry adaptation has been studied and implemented, but crystallographic symmetries have not been exploited in trigonometric optimization before. With our approach, we provide an alternative to known strategies for trigonometric optimization. Where other techniques utilize sums of Hermitian squares or generalizations of Lasserre's hierarchy to the complex setting, we exploit symmetry first and then apply techniques from classical polynomial optimization. This reduces the size of arising semi-definite relaxations and can also improve the quality of the approximation.
As an application, we study the problem of computing lower bounds for the chromatic number of geometric distance graphs. Given a norm and a set of vertices, this problem asks to find the minimal number of colors needed to paint the vertices, so that no two of those of distance 1 between them have the same color. The spectral bound was generalized from finite to infinite graphs to deal with such problems. This bound involves the optimization of a trigonometric polynomial. We focus on norms which are given by polytopes with crystallographic symmetry. Then the problem can be tackled with the techniques developed in this thesis. We give several bounds through analytical and numerical computations.
Keywords
Crystallographic Groups, Chebyshev Polynomials, Optimization, Root Systems, Symmetry
