TSSOS: A Moment-SOS hierarchy that exploits term sparsity

1. Introduction.

• Polynomial minimization over a basic semialgebraic set is NP-hard.The paper identifies this as the central optimization problem.Source: Background · p. 1
• The moment-SOS hierarchy replaces infinite-dimensional primal and dual linear programs with a sequence of finite-dimensional primal-dual relaxations.Each step requires solving a single semidefinite program.Source: Background · p. 1
• Under assumptions slightly stronger than compactness, the hierarchy’s optimal values converge to the original problem’s optimum.Source: Background · p. 1

Background.

• Prior sparse moment-SOS methods exploit variable links, while term-sparsity methods partition monomial bases into blocks to reduce SDP matrix sizes.Small blocks can improve efficiency and scalability; some sparse hierarchies require the running intersection property for convergence.Source: Background · p. 2
• The paper presents its method as a comprehensive extension of cross sparsity patterns to constrained polynomial optimization.It contrasts the approach with sparse moment-SOS methods based on correlative sparsity.Source: Background · p. 2, Contributions · p. 3
• Alternative SAGE, SONC, DSOS, and SDSOS frameworks can produce converging hierarchies, but their implementation and lower-bound computation are difficult in practice.The cited correlative-sparsity/SDSOS combination [25] lacks a convergence guarantee and currently applies only to unconstrained problems.Source: Background · pp. 2–3

Contributions.

• Each TSSOS iteration applies support extension followed by block closure to construct block-diagonal SDP relaxations.The hierarchy is applied to both unconstrained and constrained polynomial optimization; small blocks can yield computational savings.Source: Contributions · p. 3
• In the constrained hierarchy, fixed-relaxation-order values form a non-decreasing sequence converging to the dense hierarchy’s value at that order, typically in two or three steps.The hierarchy also varies the relaxation order and sparse order.Source: Contributions · p. 3
• The block structure converges to one determined by sign symmetries, supporting a sparse Putinar Positivstellensatz with SOS supports reduced accordingly.Source: Contributions · p. 3
• Across tested random and networked-system examples, TSSOS performs significantly better in efficiency and scalability than existing frameworks.At k = 1, its values matched dense moment-SOS on all tested examples, though this is not guaranteed in theory; usual correlative sparsity was dense or nearly dense except for the Broyden banded function.Source: Contributions · p. 3
• Chordal-TSSOS replaces block closure with chordal extension, while CS-TSSOS combines term and correlative sparsity for large-scale problems.The latter handles examples including Max-Cut and optimal power flow with up to several thousand variables.Source: Contributions · pp. 3–4

2. Notation and Preliminaries.

• The notation section defines polynomial supports and Newton polytopes as exponent-set objects.It also defines cardinality and the sum of two exponent sets.Source: §2.1 · p. 4

2.1. Notation and SOS polynomials.

• An SOS polynomial is a sum of polynomial squares and certifies global nonnegativity; its SDP formulation uses a positive semidefinite Gram matrix.The Newton polytope method can reduce the monomial basis and corresponding SDP size.Source: §2.1 · p. 4

2.2. Moment matrices.

• Moment and localizing matrices are indexed by monomial bases and are associated with moment sequences and polynomial constraints.Source: §2.2 · p. 5

3. Exploiting term sparsity in SOS decompositions.

• Support-extension followed by block-closure builds binary matrices whose graph components are completed into blocks, with connected components computable in linear time.The matrices stabilize after finitely many iterations.Source: §3 · p. 6
• For every finite support set A, the stabilized sparse SOS cone equals the full SOS cone, Σ*(A) = Σ(A).The inner-approximation hierarchy therefore reaches Σ(A) in finitely many steps.Source: §3 · p. 7
• When the blocks are small relative to the original matrix, membership testing uses smaller SDP matrices and may reduce computational cost.The sparse Gram matrix is block-diagonal up to permutation.Source: §3 · p. 7
• For supports containing only terms of degree at most two, the first sparse SOS approximation already equals the full SOS cone.Σ1(A) = Σ(A).Source: §3 · p. 7

4. A block SDP hierarchy for unconstrained POPs.

• The TSSOS hierarchy comprises the relaxations (4.1) and (4.3), with k denoting the sparse order.The construction uses sparse SOS decompositions to form a block SDP hierarchy for the original problem.Source: §4 · pp. 7–8
• For every k ≥ 1, the primal and dual relaxations (Pk) and (Pk)* have no duality gap.Source: §4 · p. 8
• θ1 = θ2 = θtssos = θsos = θ* ≈ 0.4753 in the worked example, with the sparse matrices stabilizing at k = 2.The example solves the SDPs at orders one and two.Source: §4 · p. 9

Relationship with DSOS/SDSOS optimization.

• DSOS uses a diagonally dominant Gram matrix, while SDSOS uses a scaled diagonally dominant Gram matrix.Source: Relationship with DSOS/SDSOS… · p. 9
• The stated set inclusions are DSOS(A) ⊆ SDSOS(A) ⊆ Σ(A).Source: Relationship with DSOS/SDSOS… · p. 9
• For every finite support set A, SDSOS(A) is contained in the first sparse SOS cone, Σ1(A).Source: Relationship with DSOS/SDSOS… · p. 9

5. A block Moment-SOS hierarchy for constrained POPs.

• Support-extension produces block-diagonal moment relaxations, and the associated binary matrices stabilize after finitely many steps.The matrices induce blocks in the monomial basis used for the relaxations.Source: §5 · pp. 11, 13
• At fixed relaxation order, the optimal values of the block relaxations form a monotone nondecreasing sequence.Each relaxation at sparse order k is a relaxation of the next one.Source: §5 · pp. 11–12
• The construction combines two results into a two-level hierarchy of lower bounds, parameterized by relaxation order and sparse order.The paper calls this the TSSOS hierarchy; k is the sparse order.Source: §5 · pp. 10, 12, 13
• If K has nonempty interior, the paper establishes no duality gap for the block relaxation at any allowed relaxation order and sparse order.The stated condition is that the feasible set K has nonempty interior.Source: §5 · p. 13
• The dual representation is a sparse Putinar certificate: f − λ is nonnegative on K when expressed using SOS polynomials with sparse monomial-basis Gram matrices.Each SOS polynomial has a positive semidefinite Gram matrix indexed by its sparse basis.Source: §5 · p. 13

This yields

• The second-iteration display includes moment entries y20, y40, y22, y11, y31, y13, y02, and y04.These entries appear in the displayed matrix representation.Source: This yields · p. 14
• The displayed matrix also includes y00 alongside y20, y11, and y02 among its moment entries.The display lists these symbols in its matrix layout.Source: This yields · p. 14
• Some displayed matrix expressions contain coefficients −2 on y40, y31, and y22, as well as −1 on y22 and y13.These terms appear in the matrix-expression fragment.Source: This yields · p. 14

6. Sign-symmetries and a sparse representation theorem for positive polynomials.

• For the standard monomial basis, β and γ lie in the same block exactly when RT(β + γ) ≡ 0 (mod 2).Here R has columns defining the sign-symmetries of A.Source: §6 · p. 15
• With a smaller monomial basis, Theorem 6.5 guarantees only the “only if” direction; Example 6.7 shows the induced partition can refine the sign-symmetry partition.In the example, the sign-symmetry partition has two blocks, while the induced partition separates xy and x2y into individual blocks.Source: §6 · p. 17
• At each relaxation order, TSSOS block structure converges to the structure determined by sign-symmetries of the input supports when standard monomial bases are used.Source: §6 · p. 18
• The final iterative step retrieves an equivalent SDP with sign-symmetry block structure, but the dense relaxation’s optimal value can often be reached earlier, even at the first step, at lower computational cost.Source: §6 · p. 18
• If Q(g) is Archimedean and f is positive on K, then f has a quadratic-module SOS representation whose terms satisfy RTα ≡ 0 (mod 2) for every α in each SOS support.The sign-symmetries are defined from A = supp(f) ∪ ⋃ supp(gj).Source: §6 · p. 18
• Each s_j is an SOS polynomial because its Gram matrix is positive semidefinite and block-diagonal up to permutation.Source: §6 · p. 18
• Replacing t_i with s_i removes terms whose exponent parities are outside S while preserving coefficient matching in the equality.The support argument places each s_j within the adjacency-graph support, which underlies the parity-based removal.Source: §6 · p. 19

7.1. Unconstrained polynomial optimization problems.

• Up to 12 variables, TSSOS handles unconstrained examples, while GloptiPoly and Yalmip cannot handle more than 8 and 10 variables, respectively; at k=1, it matches dense moment-SOS optima in much less time.Source: §7.1 · p. 21
• Type-II random polynomials show similar efficiency and accuracy comparisons; Yalmip's sign-symmetry option handles slightly more instances than GloptiPoly.Source: §7.1 · p. 22
• For network systems, TSSOS handles up to N=80 nodes, versus 's limit of N=50.Source: §7.1 · p. 24
• For Duffing oscillators, TSSOS selects g up to 2, versus 1.8 in and around 1.5 with SDSOS, using fewer decision variables and less time than SDSOS.Source: §7.1 · pp. 24–25

7.2. Constrained polynomial optimization problems.

• For Example 7.2, ˆd=3 converges at k=2, while ˆd=4 converges at k=1 with optimal value −2.5791 × 10−10.For ˆd=3, the reported optimal values are −5.0324 × 10−8 at k=1 and −1.6016 × 10−7 at k=2.Source: §7.2 · pp. 25–26

7. Numerical experiments.

• TSSOS performs much better than dense moment-SOS on constrained problems without compromising accuracy, and the benchmarks report speedups in both constrained and unconstrained cases.Source: §7.2 · p. 26, §8 · p. 26

• Further work could investigate term-sparsity exploitation in moment-SOS variants for optimal control.Source: §8 · p. 26
• Further work could investigate term-sparsity exploitation in approximations of sets of interest, including maximal invariant and reachable sets in dynamical systems.Source: §8 · p. 26
• Further work could investigate term-sparsity exploitation in variants for eigenvalue and trace optimization of polynomials in non-commuting variables.Source: §8 · p. 26