Crystallographic groups and Chebyshev polynomials in global optimization
Groupes cristallographiques et polynômes de Chebyshev en optimisation globale
Résumé
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 A, B, C, D and G, 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.
Cette thèse étudie le problème de l'optimisation d'un polynôme trigonométrique avec symétrie cristallographique. L'optimisation des polynômes trigonométriques était l'objet de nombreux travaux récents, mais une théorie permettant d'exploiter les symétries n'a pas été développée ou généralisée. Nous considérons l'action d'un groupe cristallographique, également connu sous le nom de groupe de Weyl, sur les exposants. Cette action admet une définition des polynômes de Chebychev généralisés. Si un polynôme trigonométrique est invariant sous l'action, il peut être écrit comme une somme de polynômes de Chebyshev généralisés dans les invariants fondamentaux.En réécrivant un polynôme trigonométrique invariant comme un polynôme classique, la région d'optimisation est transformée en l'espace d'orbite de l'action du groupe de Weyl multiplicatif. Cet espace d'orbite est l'image des invariants fondamentaux et nous montrons que, pour les groupes de Weyl de types A, B, C, D et G, il s'agit d'un ensemble compact basique semi-algébrique. En plus, nous donnons les inégalités polynomiales descriptives à par un matrix polynomial positif de Hermite.En ce qui concerne l'optimisation, notre approche de réécriture transforme le problème d'optimisation trigonométrique dans un problème d'optimisation polynomiale sur un ensemble basique semi-algébrique. Pour résoudre de tels problèmes, on peut appliquer la hiérarchie des relaxations de moment et de somme de carrés de Lasserre. Nous adaptons et implémentons cette hiérarchie sur la base de polynômes de Chebyshev généralisés avec une nouvelle notion de degré. La valeur optimale du problème d'optimisation trigonométrique original est alors approximée par des solutions de programmes semi-définis, qui sont résolus numériquement.Dans l'optimisation polynomiale classique et d'autres applications, l'adaptation des symétries a été étudiée et implémenté, mais les symétries cristallographiques n'ont pas été exploitées en optimisation trigonométrique auparavant. Avec notre approche, nous fournissons une alternative aux stratégies connues pour l'optimisation trigonométrique. Alors que d'autres techniques utilisent des sommes de carrés Hermitiens ou en généralisant l'hiérarchie de Lasserre au cadre complexe, nous exploitons d'abord la symétrie et appliquons ensuite des techniques d'optimisation polynomiale classique. Cela réduit la taille des relaxations semi-définies qui en découlent et peut également améliorer la qualité de l'approximation.En guise d'application, nous étudions le problème de calcul des bornes inférieurs pour le nombre chromatique des graphes géométriques. Étant donné une norme et un ensemble de sommets, ce problème demande de trouver le nombre minimal de couleurs nécessaires pour peindre les sommets, de sorte que deux de ceux de distance 1 entre eux n'aient pas la même couleur. La borne spectrale a été généralisée des graphes finis aux graphes infinis pour traiter de tels problèmes. Cette limite implique l'optimisation d'un polynôme trigonométrique. Nous nous concentrons sur les normes qui sont données par des polytopes avec une symétrie cristallographique. Le problème peut alors être abordé avec les techniques développées dans cette thèse. Nous donnons plusieurs bornes à travers des calculs analytiques et numériques.
Origine : Version validée par le jury (STAR)