PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploiting symmetries in SDP-relaxations for polynomial optimization

Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, Jean B. Lasserre

arXiv:1103.0486v3math.OCcs.SYeess.SY

TL;DR

Constrained polynomial optimization is difficult to scale because standard SDP relaxations grow rapidly. This paper develops symmetry-aware relaxations and reductions, especially for the symmetric group, and derives size bounds and bounds for certain quotient-space problems.

  • Problem

    Standard SDP relaxations for constrained polynomial optimization grow rapidly with problem size, limiting their applicability to small or medium problems without additional structure.

    Source: §1 · p. 1

  • Method

    The paper exploits symmetries through adapted polynomial bases and block structure, degree-principle reductions, and optimization in the geometric quotient.

    Source: §1 · pp. 2–3

  • Results

    For fixed order k, the symmetric-group relaxation has numbers and sizes of LMIs bounded independently of n, and certain power-sum quotient problems yield simply computed lower and upper bounds.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper provides symmetry-based tools for constrained optimization, including lower-dimensional formulations and quotient-space bounds for specified problem classes.

    Source: §1 · pp. 2–3

    Some algebraic techniques may be unfamiliar to optimizers, raising doubts about systematic software implementation in the near future.

    Source: §1 · p. 3

Abstract

from arXiv · show

In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited and also propose some methods to efficiently compute in the geometric quotient.

1. Introduction

Constrained polynomial optimization is difficult, and standard SDP relaxations grow rapidly with the number of variables. The paper develops symmetry-based approaches, especially for the symmetric group, spanning adapted relaxations, degree-principle reductions, and geometric quotients.

1. Introduction

  • For fixed relaxation order k, the symmetric-group formulation bounds the number and sizes of LMIs independently of the number of variables.It also yields symmetric sums-of-squares representation results, including Hilbert cases.Source: §1 · p. 2
  • The paper systematically adapts Lasserre relaxations to symmetry, using polynomial bases that expose structure in moment and localizing matrices.For the symmetric group, generalized Specht polynomials provide a basis for the construction.Source: §1 · p. 2
  • The degree principle transforms symmetric-group-invariant problems into lower-dimensional problems and yields finite convergence in some cases.The approach also gives an SOS-based non-negativity criterion for symmetric quartics.Source: §1 · p. 2
  • For certain power-sum problems, the geometric quotient leads to a polynomial matrix inequality and simply computable lower and upper bounds.This generalizes a situation studied by Brandenberg and Theobald.Source: §1 · pp. 2–3
  • A practical boundary is that some algebraic techniques may be unfamiliar to optimizers, raising doubts about systematic software implementation in the near future.The paper notes that SDP relaxations are otherwise limited to modest-sized problems unless sparsity or symmetry is used.Source: §1 · pp. 1, 3

2. Preliminaries

The preliminaries establish the optimization and algebraic tools used later: Lasserre’s hierarchy, polynomial matrix inequalities, and representation theory, with particular attention to the symmetric group.

2.1. Lasserre’s method.

  • Lasserre’s method represents constrained polynomial optimization through moment and localizing matrices, whose truncated SDP hierarchy gives monotonically increasing lower bounds converging to the global minimum.The stated convergence result assumes the feasible set satisfies the paper’s compactness condition.Source: §2.1 · pp. 4–5

2.2. Polynomial matrix inequalities.

  • Polynomial matrix inequality relaxations handle polynomial-matrix semidefiniteness directly, avoiding the high-degree scalar inequalities that can arise from entrywise constraints.The passage notes that even linear matrix entries can produce inequalities of degree m.Source: §2.2 · pp. 5–6

2.3. Linear representation theory.

  • The section introduces finite-group representation concepts used to organize the later symmetry analysis, including irreducible decompositions and Schur’s lemma.It notes that real representations may require attention to their complexification.Source: §2.3 · pp. 6–7

2.4. Symmetric group.

  • For the symmetric group, irreducible representations correspond to partitions of n and are given by Specht modules; permutation modules decompose according to Kostka numbers.The section introduces tableaux and related combinatorial descriptions used for these decompositions.Source: §2.4 · pp. 7–9

3. Symmetry-adapted relaxation

Section 3 uses invariant measures and symmetry-adapted polynomial bases to reduce and block-structure constrained polynomial optimization relaxations. Under the stated assumptions, the resulting hierarchy is monotone and converges to the global optimum.

3. Symmetry-adapted relaxation

  • A G-linear map represents integration against a G-invariant measure on K exactly when its associated bilinear forms are positive semidefinite on each component space Si.This reduces the measure characterization to positivity checks on the symmetry-adapted components.Source: §3 · p. 12
  • For G-invariant f strictly positive on K, the symmetry-adapted Positivstellensatz gives a representation with sums of squares from the component spaces Si.The representation also includes the invariant constraint polynomials.Source: §3 · p. 13
  • The symmetry-adapted moment matrix is block diagonal, with variables indexed by a basis of the invariant ring and blocks indexed by isotypic components.Its variable count is the size of that invariant-ring basis, and its block sizes are the dimensions of the corresponding component bases.Source: §3 · pp. 9, 11, 14
  • The symmetry-adapted relaxation hierarchy remains monotonically non-decreasing and converges to f*.This convergence holds under the section’s assumptions on the invariant objective, constraints, and feasible set.Source: §3 · p. 14
  • When K is invariant but some defining polynomials are not, invariant moments remain usable, but the block structure generally applies only to matrices for invariant polynomials.Source: §3 · p. 15
  • With symmetry exploited, the construction gives four diagonal blocks, three of them elementary, and a 2 × 2 semidefiniteness constraint instead of 5 × 5 without exploiting symmetry.Source: §3 · p. 15

4. Optimizing with symmetric Polynomials

For symmetric polynomials, the paper constructs polynomial realizations of the symmetric group’s representations and uses them to describe symmetry-adapted moment matrices. The resulting block structure stabilizes once n ≥ 2k, and the paper also derives sums-of-squares representations for symmetric polynomials.

4.1. Moment matrices for the symmetric group.

  • Generalized Specht polynomials realize Specht modules inside monomial spaces, providing polynomial bases for constructing the symmetric-group moment-matrix blocks.The module generated by each generalized Specht polynomial is isomorphic to the corresponding Specht module.Source: §4.1 · pp. 16–17
  • For all n ≥ 2k, the order-k symmetry-adapted moment matrix has the same block structure, so the SOS decision complexity for degree 2k depends only on k, up to computing the decomposition.Source: §4.1 · p. 19
  • For n = 3 and k = 2, the example replaces one 10 × 10 moment-matrix constraint with 4 × 4 and 3 × 3 constraints.Source: §4.1 · p. 20

4.2. Sums of squares-representations for symmetric polynomials.

  • A symmetric homogeneous polynomial of degree 2d that is a sum of squares admits a decomposition using sums of squares from the Specht-module spaces indexed by partitions.The theorem specifies the unique tableau with increasing rows and columns and nonnegative partitions of d with n parts.Source: §4.2 · p. 20
  • The displayed symmetric-polynomial decomposition uses M4, M22, M31, and M211 with coefficients subject to nonnegativity and product constraints.The stated conditions include α, γ, δ, ε ≥ 0, αγ ≥ β^2, and δε ≥ ω^2.Source: §4.2 · p. 21

5. Using the degree principle

The degree principle turns symmetric polynomial optimization into a family of lower-dimensional problems indexed by partitions. The section establishes finite-convergence and sum-of-squares consequences, including a test for non-negativity of symmetric quartics.

5. Using the degree principle

  • The principle reduces a symmetric-polynomial SDP relaxation to a family of lower-dimensional relaxations, with r determined by polynomial degrees.The reduced problems are indexed by r-partitions of n.Source: §5 · pp. 21–22
  • For fixed r, the number of r-partitions grows polynomially with n, making the family of r-variable relaxations potentially more efficient than an n-variable relaxation.The passage contrasts at most (n+r)^r partitions with moment matrices of size O(n^k).Source: §5 · pp. 21–22
  • Under the stated degree bounds and codimension condition, the degree-principle relaxation sequence converges to the minimum in finitely many steps.The conditions are deg gj ≤ m, deg f ≤ 2m, and codimension m for V(g1, . . . , gm).Source: §5 · p. 22
  • For symmetric quartics, non-negativity is equivalent to every two-variable polynomial obtained from a 2-partition being a sum of squares.This reduces deciding non-negativity to semidefinite feasibility.Source: §5 · p. 23
  • Choi and Lam’s [8] nonnegative quartic in four variables, which is not itself a sum of squares, is handled through two-variable sum-of-squares reductions.The passage reports that the reductions establish the quartic’s non-negativity.Source: §5 · p. 23

6. PMI-relaxations via the geometric quotient

The geometric quotient converts invariant polynomial optimization into a polynomial matrix inequality (PMI), which can be relaxed using semidefinite programming. In power-sum problems, the paper derives simple lower bounds and, under a sparsity condition on an optimizer, matching upper bounds.

6. PMI-relaxations via the geometric quotient

  • The orbit-space approach yields simple SDP bounds for power-sum problems and can strongly reduce polynomial degrees in some cases.The section reports lower bounds and sometimes upper bounds for minimization problems.Source: §6 · pp. 23–24

6.1. The general setup.

  • For a finite group, the orbit space is characterized in invariant coordinates by algebraic relations and the positive-semidefiniteness of J.The characterization is R^n//G = {z in V(I) : J(z) ⪰ 0}.Source: §6.1 · p. 24
  • Expressing the objective and constraints in fundamental invariants gives an equivalent PMI, whose SDP-relaxation hierarchy converges under Assumption 2.5.The hierarchy is monotonically non-decreasing and converges to f* when the stated assumption holds.Source: §6.1 · p. 25

6.2. Lower and upper bounds for power sum problems.

  • A Hankel-matrix semidefinite optimization problem provides lower bounds on min P_nmq for the stated power-sum parameter range.For q = m = 2r, the passage also gives a refinement using a smaller Hankel matrix and Schur’s complement.Source: §6.2 · p. 26
  • The proposed upper bound is exact when P_nmq has an optimal solution with at most m nonzero entries.In that case, the problem has the equivalent convex formulation (6.7).Source: §6.2 · pp. 26–27
Loading 1103.0486v3…