# Term sparsity

[WML20a] Wang, Jie, Victor Magron, and Jean-Bernard Lasserre. TSSOS: A Moment-SOS hierarchy that exploits term sparsity. arXiv preprint arXiv:1912.08899 (2020).

[WML20b] Wang, Jie, Victor Magron, and Jean-Bernard Lasserre. Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension. arXiv preprint arXiv:2003.03210 (2020).

using DynamicPolynomials
@polyvar x[1:3]
(DynamicPolynomials.PolyVar{true}[x₁, x₂, x₃],)

We would like to find the minimum value of the polynomial

poly = x^2 - 2x*x + 3x^2 - 2x^2*x + 2x^2*x^2 - 2x*x + 6x^2 + 18x^2*x - 54x*x^2 + 142x^2*x^2
$$$2x_{1}^{2}x_{2}^{2} + 142x_{2}^{2}x_{3}^{2} - 2x_{1}^{2}x_{2} + 18x_{2}^{2}x_{3} - 54x_{2}x_{3}^{2} + x_{1}^{2} - 2x_{1}x_{2} + 3x_{2}^{2} - 2x_{2}x_{3} + 6x_{3}^{2}$$$

The minimum value of the polynomial can be found to be zero.

import CSDP
solver = CSDP.Optimizer
using SumOfSquares
function sos_min(sparsity)
model = Model(solver)
@variable(model, t)
@objective(model, Max, t)
con_ref = @constraint(model, poly - t in SOSCone(), sparsity = sparsity)
optimize!(model)
return value(t), moment_matrix(con_ref)
end

bound, ν = sos_min(Sparsity.NoPattern())
bound
-3.045195207107554e-10

We find the corresponding minimizer (0, 0, 0) by matching the moments of the moment matrix with a dirac measure centered at this minimizer.

extractatoms(ν, 1e-6)
Atomic measure on the variables x, x, x with 1 atoms:
at [2.0703595321702734e-6, 1.2367907094787687e-6, 2.2362397702348983e-8] with weight 1.0000000014903554

We can see below that the basis contained 6 monomials hence we needed to use 6x6 PSD matrix variables.

ν.basis
MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}(DynamicPolynomials.Monomial{true}[x₁x₂, x₂x₃, x₁, x₂, x₃, 1])

Using the monomial/term sparsity method of [WML20a] based on cluster completion, we find the same bound.

bound, ν = sos_min(Sparsity.Monomial())
bound
-3.045195207107554e-10

Which is not suprising as no sparsity reduction could be performed.

[sub.basis for sub in ν.sub_moment_matrices]
1-element Vector{MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}}:
MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}(DynamicPolynomials.Monomial{true}[x₁x₂, x₂x₃, x₁, x₂, x₃, 1])

Using the monomial/term sparsity method of [WML20b] based on chordal completion, the lower bound is smaller than 0.

bound, ν = sos_min(Sparsity.Monomial(ChordalCompletion()))
bound
-0.0035512009904666852

However, this bound was obtained with an SDP with 4 matrices of size 3x3.

[sub.basis for sub in ν.sub_moment_matrices]
4-element Vector{MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}}:
MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}(DynamicPolynomials.Monomial{true}[x₂x₃, x₂, x₃])
MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}(DynamicPolynomials.Monomial{true}[x₂x₃, x₂, 1])
MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}(DynamicPolynomials.Monomial{true}[x₁, x₂, 1])
MonomialBasis{DynamicPolynomials.Monomial{true}, DynamicPolynomials.MonomialVector{true}}(DynamicPolynomials.Monomial{true}[x₁x₂, x₁, 1])
{"ft_lang_label":"__label__en","ft_lang_prob":0.5570589,"math_prob":0.98300827,"size":3447,"snap":"2022-27-2022-33","text_gpt3_token_len":1234,"char_repetition_ratio":0.24135928,"word_repetition_ratio":0.08115942,"special_character_ratio":0.31708732,"punctuation_ratio":0.19115324,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992498,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-07-05T13:06:38Z\",\"WARC-Record-ID\":\"<urn:uuid:bb39b154-f35b-4833-b008-30d6704294f5>\",\"Content-Length\":\"15003\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:73c1ace0-714a-4b62-9aa9-15ada3e82c59>\",\"WARC-Concurrent-To\":\"<urn:uuid:af121391-2559-460f-b942-e688d9a6d6b4>\",\"WARC-IP-Address\":\"185.199.110.153\",\"WARC-Target-URI\":\"https://jump.dev/SumOfSquares.jl/stable/generated/Sparsity/term_sparsity/\",\"WARC-Payload-Digest\":\"sha1:UC5N3GLD4P2TFMA2NKDWQL5UNSZIEDKF\",\"WARC-Block-Digest\":\"sha1:4OHQICOTQQMF5UKULZMIAEXPQ64N5E5I\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656104576719.83_warc_CC-MAIN-20220705113756-20220705143756-00514.warc.gz\"}"}