Symmetry reduction in AM/GM-based optimization

Autor:	Moustrou, Philippe, Naumann, Helen, Riener, Cordian, Theobald, Thorsten, Verdure, Hugues
Rok vydání:	2021
Předmět:	Mathematics - Optimization and Control Mathematics - Algebraic Geometry 14P05 20C30 90C30
Druh dokumentu:	Working Paper
Popis:	The arithmetic mean/geometric mean-inequality (AM/GM-inequality) facilitates classes of non-negativity certificates and of relaxation techniques for polynomials and, more generally, for exponential sums. Here, we present a first systematic study of the AM/GM-based techniques in the presence of symmetries under the linear action of a finite group. We prove a symmetry-adapted representation theorem and develop techniques to reduce the size of the resulting relative entropy programs. We study in more detail the complexity gain in the case of the symmetric group. In this setup, we can show in particular certain stabilization results. We exhibit several sequences of examples in growing dimensions where the size of the problem stabilizes. Finally, we provide some numerical results, emphasizing the computational speed-up. Comment: Revised version
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2102.12913 Zobrazit plný text záznamu View this record from Arxiv