Certificate

default_maxdegree(monos, domain)

Return the default maxdegree to use for certifying a polynomial with monomials monos to be Sum-of-Squares over the domain domain. By default, the maximum of the maxdegree of monos and of all multipliers of the domain are used so that at least constant multipliers can be used with a Putinar certificate.

struct Sparsity.Variable <: Sparsity.Pattern end

Variable or correlative sparsity as developed in [WSMM06].

[WSMM06] Waki, Hayato, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. "Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity." SIAM Journal on Optimization 17, no. 1 (2006): 218-242.

struct Sparsity.Monomial{C<:CEG.AbstractCompletion} <: Sparsity.Pattern
    completion::C
    k::Int
    use_all_monomials::Bool
end

Monomial or term sparsity as developed in [WML20a, WML20b]. The completion field should be ClusterCompletion() [default] for the block-closure or cluster completion [WML20a], and ChordalCompletion() for chordal completion [WML20b]. The integer k [default=0] corresponds to Σ_k defined in [(3.2), WML20a] and k = 0 corresponds to Σ_* defined in [(3.3), WML20a]. If use_all_monomials is false then some monomials of the basis might be dropped from the basis if not needed.

[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).

struct SignSymmetry <: Sparsity.Pattern end

Sign symmetry as developed in [Section III.C, L09]. Let n be the number of variables. A sign-symmetry is a binary vector r of {0, 1}^n such that dot(r, e) is even for all exponent e.

Let o(e) be the binary vector of {0, 1}^n for which the ith bit is i iff the ith entry of e is odd. Let O be the set of o(e) for exponents of e. A binary vector r is a sign-symmetry if an only if it is orthogonal to all the elements of O.

Since we are only interested in the orthogonal subspace, say R, of O, even if O is not a linear subspace (i.e., it is not invariant under xor), we compute its span. We start by creating row echelon form of the span of O using XORSpace. We then compute a basis for R. The set R of sign symmetries will be the span of this basis.

Let a, b be exponents of monomials of the gram basis. For any r in R,

⟨r, o(a + b)⟩ = ⟨r, xor(o(a), o(b)⟩ = xor(⟨r, o(a)⟩, ⟨r, o(b)⟩)

For o(a, b) to be sign symmetric, this scalar product should be zero for all sign symmetry r. This is equivalent to saying that ⟨r, o(a)⟩ and ⟨r, o(b)⟩ are equal for all r in R. In other words, the projection of o(a) and o(b) to R have the same coordinates in the basis. If we order the monomials by grouping them by equal coordinates of projection, we see that the product that are sign symmetric form a block diagonal structure. This means that we can group the monomials by these coordinates.

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

mutable struct XORSpace{T<:Integer}
    dimension::Int
    basis::Vector{T}
end

Basis for a linear subspace of the Hamming space (i.e. set of binary string {0, 1}^n of length n) represented in the bits of an integer of type T. This is used to implement Certificate.Sparsity.SignSymmetry.

Consider the scalar product ⟨a, b⟩ which returns the the xor of the bits of a & b. It is a scalar product since ⟨a, b⟩ = ⟨b, a⟩ and ⟨a, xor(b, c)⟩ = xor(⟨a, b⟩, ⟨a, c⟩).

We have two options here to compute the orthogonal space.

The first one is to build an orthogonal basis with some kind of Gram-Schmidt process and then to obtain the orthogonal space by removing the projection from each vector of the basis.

The second option, which is the one we use here is to compute the row echelon form and then read out the orthogonal subspace directly from it. For instance, if the row echelon form is

1 a 0 c e
  b 1 d f

then the orthogonal basis is

a 1 b 0 0
c 0 d 1 0
e 0 f 0 1

The basis vector has dimension nonzero elements. Any element added with push! can be obtained as the xor of some of the elements of basis. Moreover, the basis is kept in row echelon form in the sense that the first, second, ..., i - 1th bits of basis[i] are zero and basis[i] is zero if its ith bit is not one.

struct MaxDegree{C<:SumOfSquares.SOSLikeCone,G<:SA.AbstractBasis,Z<:SA.AbstractBasis} <:
    SimpleIdealCertificate{C,G,Z}
    cone::C
    gram_basis::G
    zero_basis::Z
    maxdegree::Int
end

The MaxDegree certificate ensures the nonnegativity of p(x) for all x such that h_i(x) = 0 by exhibiting a Sum-of-Squares polynomials σ(x) such that p(x) - σ(x) is guaranteed to be zero for all x such that h_i(x) = 0. The polynomial σ(x) is search over cone with a basis of type basis such that the degree of σ(x) does not exceed maxdegree.

struct FixedBasis{C<:SumOfSquares.SOSLikeCone,G<:SA.ExplicitBasis,Z<:SA.AbstractBasis} <:
    SimpleIdealCertificate{C,G,Z}
    cone::C
    gram_basis::G
    zero_basis::Z
end

The FixedBasis certificate ensures the nonnegativity of p(x) for all x such that h_i(x) = 0 by exhibiting a Sum-of-Squares polynomials σ(x) such that p(x) - σ(x) is guaranteed to be zero for all x such that h_i(x) = 0. The polynomial σ(x) is search over cone with basis basis.

struct Newton{
    C<:SumOfSquares.SOSLikeCone,
    G<:SA.AbstractBasis,
    Z<:SA.AbstractBasis,
    N<:AbstractNewtonPolytopeApproximation,
} <: SimpleIdealCertificate{C,G,Z}
    cone::C
    gram_basis::G
    zero_basis::Z
    newton::N
end

The Newton certificate ensures the nonnegativity of p(x) for all x such that h_i(x) = 0 by exhibiting a Sum-of-Squares polynomials σ(x) such that p(x) - σ(x) is guaranteed to be zero for all x such that h_i(x) = 0. The polynomial σ(x) is search over cone with a basis of type basis chosen using the multipartite Newton polytope with parts variable_groups. If variable_groups = tuple() then it falls back to the classical Newton polytope with all variables in the same part.

struct Remainder{C<:AbstractIdealCertificate} <: AbstractIdealCertificate
    gram_certificate::C
end

The Remainder certificate ensures the nonnegativity of p(x) for all x such that h_i(x) = 0 by guaranteeing the remainder of p(x) modulo the ideal generated by ⟨h_i⟩ to be nonnegative for all x such that h_i(x) = 0 using the certificate gram_certificate. For instance, if gram_certificate is SumOfSquares.Certificate.Newton, then the certificate Remainder(gram_certificate) will take the remainder before computing the Newton polytope hence might generate a much smaller Newton polytope hence a smaller basis and smaller semidefinite program. However, this then corresponds to a lower degree of the hierarchy which might be insufficient to find a certificate.

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 Symmetry.Ideal{C,GT,AT<:SymbolicWedderburn.Action} <: SumOfSquares.Certificate.AbstractIdealCertificate
    pattern::Symmetry.Pattern{GT,AT}
    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 Symbolic Wedderburn decomposition of the symmetry pattern specified by pattern.

struct Putinar{
    MC<:AbstractIdealCertificate,
    IC<:AbstractIdealCertificate,
} <: AbstractPreorderCertificate
    multipliers_certificate::MC
    ideal_certificate::IC
    maxdegree::Int
end

The Putinar certificate ensures the nonnegativity of p(x) for all x such that g_i(x) >= 0 and h_i(x) = 0 by exhibiting Sum-of-Squares polynomials σ_i(x) such that p(x) - ∑ σ_i(x) g_i(x) is guaranteed to be nonnegativity for all x such that h_i(x) = 0. The polynomials σ_i(x) are search over cone with a basis of type basis such that the degree of σ_i(x) g_i(x) does not exceed maxdegree.

struct Sparsity.Preorder{S <: Sparsity.Pattern, C <: SumOfSquares.Certificate.AbstractPreorderCertificate} <: SumOfSquares.Certificate.AbstractPreorderCertificate
    sparsity::S
    certificate::C
end

Same certificate as C except that the Sum-of-Squares polynomials σ_i are modelled as a sum of Sum-of-Squares polynomials with smaller basis using the sparsity reduction sparsity.

neighbors(G::Graph, node::Int}

Return neighbors of node in G.

is_clique(G::Graph{T}, x::Vector{T})

Return a Bool indication whether x is a clique in G.

struct LabelledGraph{T}
    n2int::Dict{T,Int}
    int2n::Vector{T}
    graph::Graph
end

Type to represend a graph with nodes of type T.

add_node!(G::LabelledGraph{T}, i::T) where T

Add the node i to graph G. If i is already a node of G, only return the reference.

add_edge!(G::LabelledGraph{T}, i::T, j::T) where T

Add the unweighted edge (i, j) to graph G. Duplicate edges are not taken into account.

add_edge!(G::LabelledGraph{T}, e::Tuple{T,T}) where T

Add the unweighted edge e to graph G. Duplicate edges are not taken into account.

add_clique!(G::LabelledGraph{T}, x::Vector{T}) where T

Add all elements of x as nodes to G and add edges such that x is fully connected in G.

completion(G::Graph, comp::ClusterCompletion)

Return a cluster completion of G and the corresponding maximal cliques.

completion(G::Graph, comp::ChordalCompletion)

Return a chordal extension of G and the corresponding maximal cliques.

The algoritm is Algorithm 3 in [BA10] with the GreedyFillIn heuristic of Table I.

[BA10] Bodlaender, Hans L., and Arie MCA Koster. Treewidth computations I. Upper bounds. Information and Computation 208, no. 3 (2010): 259-275. Utrecht University, Utrecht, The Netherlands www.cs.uu.nl