Sign symmetry

Adapted from: Example 4 of [L09]

[L09] Lofberg, Johan. Pre-and post-processing sum-of-squares programs in practice. IEEE transactions on automatic control 54, no. 5 (2009): 1007-1011.

using DynamicPolynomials
@polyvar x[1:3]

(DynamicPolynomials.PolyVar{true}[x₁, x₂, x₃],)

We would like to determine whether the following polynomial is a sum-of-squares.

poly = 1 + x[1]^4 + x[1] * x[2] + x[2]^4 + x[3]^2

\[ x_{1}^{4} + x_{2}^{4} + x_{1}x_{2} + x_{3}^{2} + 1 \]

In order to do this, we can solve the following Sum-of-Squares program.

import CSDP
solver = CSDP.Optimizer
using SumOfSquares
function sos_check(sparsity)
    model = Model(solver)
    con_ref = @constraint(model, poly in SOSCone(), sparsity = sparsity)
    optimize!(model)
    println(solution_summary(model))
    return gram_matrix(con_ref)
end

g = sos_check(Sparsity.NoPattern())
g.basis.monomials

7-element DynamicPolynomials.MonomialVector{true}:
 x₁²
 x₁x₂
 x₂²
 x₁
 x₂
 x₃
 1

As detailed in the Example 4 of [L09], we can exploit the sign symmetry of the polynomial to decompose the large positive semidefinite matrix into smaller ones.

g = sos_check(Sparsity.SignSymmetry())
monos = [sub.basis.monomials for sub in g.sub_gram_matrices]

3-element Vector{DynamicPolynomials.MonomialVector{true}}:
 [x₁, x₂]
 [x₃]
 [x₁², x₁x₂, x₂², 1]

This page was generated using Literate.jl.