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.Variable{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[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

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

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{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}:
 1
 x₃
 x₂
 x₁
 x₂²
 x₁x₂
 x₁²

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.blocks]

3-element Vector{DynamicPolynomials.MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}}:
 [x₂, x₁]
 [x₃]
 [1, x₂², x₁x₂, x₁²]

This page was generated using Literate.jl.