/
ideal.jl
106 lines (102 loc) · 3.14 KB
/
ideal.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
"""
struct Sparsity.Ideal{S <: Sparsity.Pattern, C <: AbstractIdealCertificate} <: SumOfSquares.Certificate.AbstractIdealCertificate
sparsity::S
certificate::C
end
Same certificate as `certificate` except that the Sum-of-Squares polynomial `σ`
is modelled as a sum of Sum-of-Squares polynomials with smaller bases
using the sparsity reduction `sparsity`.
"""
struct Ideal{S<:Pattern,C<:SumOfSquares.Certificate.AbstractIdealCertificate} <:
SumOfSquares.Certificate.AbstractIdealCertificate
sparsity::S
certificate::C
end
function Ideal(sp::Variable, basis, cone, maxdegree::Nothing, newton_polytope)
return error(
"`maxdegree` cannot be `nothing` when `sparsity` is `Sparsity.Variable`.",
)
end
function Ideal(sp::Variable, basis, cone, maxdegree::Integer, newton_polytope)
return Ideal(sp, SumOfSquares.Certificate.MaxDegree(cone, basis, maxdegree))
end
function Ideal(
sp::Union{Monomial,SignSymmetry},
basis,
cone,
maxdegree,
newton_polytope,
)
return Ideal(
sp,
SumOfSquares.Certificate.Newton(cone, basis, newton_polytope),
)
end
function sparsity(
poly::MP.AbstractPolynomial,
::Variable,
certificate::SumOfSquares.Certificate.MaxDegree,
)
H, cliques = chordal_csp_graph(poly, SemialgebraicSets.FullSpace())
return map(cliques) do clique
return SumOfSquares.Certificate.maxdegree_gram_basis(
certificate.basis,
clique,
certificate.maxdegree,
)
end
end
function sparsity(
monos,
sp::Union{SignSymmetry,Monomial},
gram_basis::MB.MonomialBasis,
)
return MB.MonomialBasis.(sparsity(monos, sp, gram_basis.monomials))
end
function sparsity(
poly::MP.AbstractPolynomial,
sp::Union{SignSymmetry,Monomial},
certificate::SumOfSquares.Certificate.AbstractIdealCertificate,
)
return sparsity(
MP.monomials(poly),
sp,
SumOfSquares.Certificate.gram_basis(certificate, poly),
)
end
function sparsity(v::SumOfSquares.Certificate.WithVariables, sp, certificate)
return sparsity(v.inner, sp, certificate)
end
function SumOfSquares.Certificate.gram_basis(certificate::Ideal, poly)
return sparsity(poly, certificate.sparsity, certificate.certificate)
end
function SumOfSquares.Certificate.gram_basis_type(
::Type{Ideal{S,C}},
) where {S,C}
return Vector{<:SumOfSquares.Certificate.gram_basis_type(C)}
end
function SumOfSquares.Certificate.reduced_polynomial(
certificate::Ideal,
poly,
domain,
)
return SumOfSquares.Certificate.reduced_polynomial(
certificate.certificate,
poly,
domain,
)
end
function SumOfSquares.Certificate.cone(certificate::Ideal)
return SumOfSquares.Certificate.cone(certificate.certificate)
end
function SumOfSquares.matrix_cone_type(::Type{Ideal{S,C}}) where {S,C}
return SumOfSquares.matrix_cone_type(C)
end
function SumOfSquares.Certificate.zero_basis(certificate::Ideal)
return SumOfSquares.Certificate.zero_basis(certificate.certificate)
end
function SumOfSquares.Certificate.zero_basis_type(
::Type{Ideal{S,C}},
) where {S,C}
return SumOfSquares.Certificate.zero_basis_type(C)
end