Exploiting Term Sparsity in Symmetry-Adapted Basis for Polynomial Optimization
Igor Klep, Victor Magron, Tobias Metzlaff, Jie Wang · 2025
Read Exploiting Term Sparsity in Symmetry-Adapted Basis for Polynomial Optimization by Igor Klep, Victor Magron, Tobias Metzlaff, Jie Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-18019.txt.
Introduction
Igor Klep, Victor Magron, Tobias Metzlaff, and Jie Wang reduce the cost of polynomial optimization, where a hierarchy of semidefinite programs gives bounds but grows expensive. Many such problems are unchanged under a finite symmetry group, and their polynomials use only a few terms, two structures that can both be exploited.
They first rewrite the matrices in a symmetry adapted basis, which splits them into smaller blocks. Then they apply term sparsity on each block to shrink the variables further. Benchmarks on quartic problems with dihedral, cyclic, and symmetric group symmetry compare the method with existing techniques and show the savings.
Catalog record
| CREATOR | Igor Klep, Victor Magron, Tobias Metzlaff, Jie Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-18019
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exploiting Term Sparsity in Symmetry-Adapted Basis for Polynomial Optimization Igor Klep, Victor Magron, Tobias Metzlaff, Jie Wang Abstract Polynomial optimization problems are infinite-dimensional, nonconvex, NP-hard, and are often handled in practice with the moment-sums of squares hierarchy of semidefinite programming bounds. We consider problems where the objective function and constraint polynomials are invariant under the action of a finite group. The present paper simultaneously exploits group symmetry and term sparsity in order to reduce the computational cost of the hierarchy. We first exploit symmetry by writing the semidefinite matrices in a symmetry-adapted basis according to an isotypic decomposition. The matrices in such a basis are block diagonal. Secondly, we exploit term sparsity on each block to further reduce the optimization matrix variables. This is a non-trivial extension of the term sparsity-based hierarchy related to sign symmetry that was introduced by two of the authors. Our method is compared with existing techniques via benchmarks on quartics with dihedral, cyclic and symmetric group symmetry. 1 Introduction Computational problems can be solved more efficiently through the exploitation of algebraic or combinatorial structures that emerge from the underlying data. In the context of constrained polynomial optimization, this article focuses on moment-sums of squares-based semidefinite approximation methods. We present a moment-sums of squares hierarchy – also called Lasserre hierarchy – of lower bounds that simultaneously exploits group symmetry and term sparsity. We prove convergence to the optimal value under the Archimedean hypothesis ( Theorems 3.5 and 3.6 ) and provide benchmarks to compare with existing methods in practice ( Section 4 ). Background. The objective of polynomial optimization is to minimize a given polynomial over a real algebraic or semialgebraic set. The problem is nonconvex, infinite-dimensional, and NP-hard. To solve it in practice, Lasserre has developed in [ 22 ] a hierarchy of semidefinite lower bounds that converges under mild assumptions to the optimal value. The technique involves, on the primal side, the reformulation to a moment problem, and, on the dual side, certifying positivity via sums of squares (SOS). The computational implementation results in a semidefinite program (SDP) and comes from a choice of polynomial basis. Originally, Lasserre formulated the approach in the standard monomial basis. Advanced techniques, such as extraction of minimizers via flat extension [ 25 ] or complex variables [ 17 , 46 ] , are often formulated in this standard basis as well. More on the Lasserre hierarchy can be found in [ 24 , 12 ] . Throughout, we assume that the objective function and the constraint polynomials are invariant under the linear action of a finite group. Our strategy begins with the exploitation of this invariance by reformulating the problem in a symmetry-adapted basis. We strongly emphasize that this does not, at least not in theory, change the numerical value of each bound in the Lasserre hierarchy. More precisely, the SDP matrices in the underlying moment-SOS relaxation are obtained by change of basis (so that trace and positive semidefiniteness are stable) and feature a block-diagonal structure. This significantly benefits the time to solve the SDP at the cost of a general preprocess of computing the basis and assembling the SDP. This preprocess is independent of the objective function and can therefore be applied to a class of problems that share the same group symmetry, number of variables, and relaxation order. Gatermann had already applied symmetry reduction for dynamical systems in [ 10 ] , and, together with Parrilo, given a reduction scheme for SDPs with an indication of how to apply this on the level of polynomial optimization [ 9 ] , see also [ 4 , 41 ] . This was later extended by Riener, Theobald, Andrén and Lasserre in [ 36 ] and to trigonometric optimization by one of the authors in [ 32 ] . On top of that, we employ term sparsity exploitation. If the polynomial is sparse in the symmetry-adapted basis, the idea is to remove superfluous entries from the SDP matrices. The pioneering papers on sparsity exploitation in polynomial optimization [ 21 , 23 ] deal with correlative sparsity, which is concerned with links between the variables. This technique is based on reindexing the matrices in the SDP by considering subsets of the variables to obtain a hierarchy with quasi block-diagonal SDP matrices, each block having a size related to the cardinality of these subsets, see [ 42 ] . These patterns usually arise in large scale industrial problems for optimal power flow [ 18 ] , roundoff error bound analysis [ 27 , 30 ] , and volume approximation [ 40 ] . In the present paper, we focus on term sparsity, which is concerned with links between the monomials instead of the variables. These patterns arise in problems with sign symmetry [ 26 ] , coordinate projection [ 33 ] , and cross-sparsity [ 43 ] , as well as sums of nonnegative circuit polynomials (SONC) [ 14 ] or signomials (SAGE) [ 3 ] . The work [ 45 ] on term sparsity by two of the authors generalizes these concepts to a term sparsity exploiting hierarchy, where, at each step of the Lasserre hierarchy, a sparsity graph is constructed. The nodes of the graph are the monomial basis elements and the edges encapsulate their term sparsity pattern (tsp) in the original data. Through consecutive support and maximal chordal extensions, one obtains another level of the hierarchy, which yields the same SDP block-structure as the one obtained after exploiting sign symmetry. This level is obtained after finitely many steps at a lower cost. Correlative and term sparsities can be successfully combined [ 44 ] . We refer the interested reader to the recent book [ 29 ] dedicated to theoretical and practical aspects of both sparsity types. Contributions. The novelty of the present work is to replace the monomial nodes of the tsp graph with invariant and equivariant elements of the symmetry-adapted basis. We show that this replacement preserves the achievement of the dense bound after finitely many steps in Theorem 3.5 and the asymptotic convergence in Theorem 3.6 when maximal chordal extensions are chosen. Next to these theoretical results, we provide a quantitative comparison with the dense approach, the initial TSSOS reduction, and the pure symmetry reduction. The algorithm is fully implemented and running in the Julia package TSSOS . The essence of our algorithm is to 1. compute a symmetry-adapted basis; 2. construct a tsp graph in the symmetry-adapted basis with respect to the entire symmetry group; 3. perform chordal + support extensions. The approach works for any finite group and comes with convergence guarantees. Note that step 1. is independent of the objective function but depends only on the group action. For the case of the symmetric group \mathfrak{S}_{n} , we can compare with [ 37 ] . The cited work offers a complementary approach where the strategy is to 1. construct a tsp graph with monomial orbits and edge orbits; 2. perform a symmetric chordal extension; 3. apply symmetry reduction to the so-obtained blocks of the tsp graph with respect to stabilizer subgroups. Here, step 2. relies on making an orbit graph simplicial, which is, according to the author of [ 37 ] , an