Symmetry Reduction in AM/GM-Based Optimization
Authors: 
Philippe Moustrou, Helen Naumann, Cordian Riener, Thorsten Theobald, Hugues VerdureAuthors Info & Claims
Abstract
The arithmetic mean/geometric mean inequality (AM/GM inequality) facilitates classes of nonnegativity 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 reduced problem stabilizes. Finally, we provide some numerical results, emphasizing the computational speedup.
References
[1]
G. Averkov, Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization, SIAM J. Appl. Algebra Geom., 3 (2019), pp. 128--151.
[2]
C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin, Invariant Semidefinite Programs, Handbook on Semidefinite, Conic and Polynomial Optimization, Springer-Verlag, Barlin, 2012 pp. 219--269.
[3]
C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc., 21 (2008), pp. 909--924.
[4]
E. R. Bazan and E. Hubert, Multivariate interpolation: Preserving and exploiting symmetry, J. Symbolic Comput., 107 (2021), pp. 1--22.
[5]
G. Blekherman, A. Raymond, M. Singh, and R. Thomas, Simple graph density inequalities with no sum of squares proofs, Combinatorica, 40 (2020), pp. 455--471.
[6]
G. Blekherman and C. Riener, Symmetric non-negative forms and sums of squares, Discrete Comput. Geom., 65 (2021), pp. 764--799.
[7]
V. Chandrasekaran and P. Shah, Relative entropy relaxations for signomial optimization, SIAM J. Optim., 26 (2016), pp. 1147--1173.
[8]
V. Chandrasekaran and P. Shah, Relative entropy optimization and its applications, Math. Program. Ser. A, 161 (2017), pp. 1--32.
[9]
E. de Klerk and R. Sotirov, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Math. Program., 122 (2010), 225.
[10]
S. Debus and C. Riener, Reflection Groups and Cones of Sums of Squares, preprint, arXiv:2011.09997, 2020.
[11]
C. Dobre and J. Vera, Exploiting symmetry in copositive programs via semidefinite hierarchies, Math. Program., 151 (2015), pp. 659--680.
[12]
M. Dressler, J. Heuer, H. Naumann, and T. de Wolff, Global optimization via the dual SONC cone and linear programming, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, 2020, pp. 138--145.
[13]
M. Dressler and R. Murray, Algebraic Perspectives on Signomial Optimization, preprint, arXiv:2107.00345, 2021.
[14]
M. Dressler, S. Iliman, and T. de Wolff, An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming, J. Symbolic Comput., 91 (2019), pp. 149--172.
[15]
T. Friedl, C. Riener, and R. Sanyal, Reflection groups, reflection arrangements, and invariant real varieties, Proc. Amer. Math. Soc., 146 (2018), pp. 1031--1045.
[16]
K. Gatermann and P. A. Parrilo, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192 (2004), pp. 95--128.
[17]
A. Heaton, S. Hoşten, and I. Shankar, Symmetry adapted Gram spectrahedra, SIAM J. Appl. Algebra Geom., 5 (2021), pp. 140--164.
[18]
S. Iliman and T. de Wolff, Amoebas, nonnegative polynomials and sums of squares supported on circuits, Res. Math. Sci., 3 (2016) 9.
[19]
S. Iliman and T. de Wolff, Lower bounds for polynomials with simplex Newton polytopes based on geometric programming, SIAM J. Optim., 26 (2016), pp. 1128--1146.
[20]
O. Karaca, G. Darivianakis, P. Beuchat, A. Georghiou, and J. Lygeros, The REPOP Toolbox: Tackling Polynomial Optimization Using Relative Entropy Relaxations, 20th IFAC World Congress, IFAC PapersOnLine, Vol. 50, 2017, Elsevier, Amsterdam, pp. 11652--11657.
[21]
L. Katthän, H. Naumann, and T. Theobald, A unified framework of SAGE and SONC polynomials and its duality theory, Math. Comput., 90 (2021), pp. 1297--1322.
[22]
J. B. Lasserre, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17 (2006), pp. 822--843.
[23]
P. Moustrou, C. Riener, and H. Verdure, Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations, J. Symbolic Comput., 107 (2021), pp. 106--121.
[24]
R. Murray, V. Chandrasekaran, and A. Wierman, Newton polytopes and relative entropy optimization, Found. Comput. Math., 21 (2021), pp. 1703--1737.
[25]
R. Murray, V. Chandrasekaran, and A. Wierman, Signomial and polynomial optimization via relative entropy and partial dualization, Math. Program. Comput., 13 (2021), pp. 257--295.
[26]
R. Murray, H. Naumann, and T. Theobald, Sublinear circuits and the constrained signomial optimization problem, Math. Program. Ser. A, (2022), https://doi.org/10.1007/s10107-022-01776-w.
[27]
H. Naumann and T. Theobald, The $\mathcal{S}$-cone and a primal-dual view on second-order representability, Beitr. Algebra Geom., 62 (2021), pp. 229--249.
[28]
C. Pantea, H. Koeppl, and G. Craciun, Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), pp. 2153--2170.
[29]
A. Raymond, J. Saunderson, M. Singh, and R. R. Thomas, Symmetric sums of squares over $k$-subset hypercubes, Math. Program. Ser. A, 167 (2018), pp. 315--354.
[30]
B. Reznick, Forms derived from the arithmetic-geometric inequality, Math. Ann., 283 (1989), pp. 431--464.
[31]
C. Riener, On the degree and half-degree principle for symmetric polynomials, J. Pure Appl. Algebra, 216 (2012), pp. 850--856.
[32]
C. Riener, T. Theobald, L. Jansson-Andrén, and J. B. Lasserre, Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res., 38 (2013), pp. 122--141.
[33]
H. Seidler and T. de Wolff, An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization, preprint, arXiv:1808.08431, https://www3.math.tu-berlin.de/combi/RAAGConOpt/comparison_paper, 2018.
[34]
R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.
[35]
V. Timofte, On the positivity of symmetric polynomial functions. Part I: General results, J. Math. Anal. and Appl., 284 (2003), pp. 174--190.
[36]
H. Waki, S. Kim, M. Kojima, and M. Muramatsu, Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17 (2006), pp. 218--242.
[37]
J. Wang and V. Magron, A second order cone characterization for sums of nonnegative circuits, Proceeding of the 45th International Symposium on Symbolic and Algebraic Computation, 2020, pp. 450--457.
[38]
J. Wang, V. Magron, and J. B. Lasserre, Chordal-TSSOS: A moment-SOS hierarchy that exploits term sparsity with chordal extension, SIAM J. Optim., 31 (2021), pp. 114--141.
[39]
J. Wang, V. Magron, and J. B. Lasserre, TSSOS: A moment-SOS hierarchy that exploits term sparsity, SIAM J. Optim., 31 (2021), pp. 1--29.
[40]
J. Wang, V. Magron, J. B. Lasserre, and N. H. A. Mai, CS-TSSOS: Correlative and Term Sparsity for Large-Scale Polynomial Optimization, preprint, arXiv:2005.02828, 2020.
[41]
W. C. Waterhouse, Do symmetric problems have symmetric solutions?, Amer. Math. Monthly, 90 (1983), pp. 378--387.
Index Terms
- Symmetry Reduction in AM/GM-Based Optimization
Index terms have been assigned to the content through auto-classification.
Recommendations
Solving Disjunctive Optimization Problems by Generalized Semi-infinite Optimization Techniques
We describe a new possibility to model disjunctive optimization problems as generalized semi-infinite programs. In contrast to existing methods in disjunctive programming, our approach does not expect any special formulation of the underlying logical ...
H∞ structured model reduction algorithms for linear discrete systems via LMI-based optimisation
In this article, H∞ structured model reduction is addressed for linear discrete systems. Two important classes of systems are considered for structured model reduction, i.e. Markov jump systems and uncertain systems. The problem we deal with is the ...
Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjope8.32.2
Issue’s Table of Contents© 2022, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2022
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024