Constraints

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 PositiveSemidefinite2x2ConeTriangle <: MOI.AbstractSymmetricMatrixSetTriangle end

Cone of positive semidefinite matrices of 2 rows and 2 columns.

struct DiagonallyDominantConeTriangle <: MOI.AbstractSymmetricMatrixSetTriangle
    side_dimension::Int
end

See Definition 4 of [AM17] for a precise definition of the last two items.

[AM17] Ahmadi, A. A. & Majumdar, A. DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ArXiv e-prints, 2017.

struct ScaledDiagonallyDominantConeTriangle <: MOI.AbstractSymmetricMatrixSetTriangle
    side_dimension::Int
end

See Definition 4 of [AM17] for a precise definition of the last two items.

[AM17] Ahmadi, A. A. & Majumdar, A. DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ArXiv e-prints, 2017.

struct NonnegPolyInnerCone{MCT <: MOI.AbstractVectorSet}
end

Inner approximation of the cone of nonnegative polynomials defined by the set of polynomials of the form

X^\top Q X

where X is a vector of monomials and Q is a symmetric matrix that belongs to the cone psd_inner.

const SOSCone = NonnegPolyInnerCone{MOI.PositiveSemidefiniteConeTriangle}

Sum-of-squares cone; see NonnegPolyInnerCone.

const SDSOSCone = NonnegPolyInnerCone{ScaledDiagonallyDominantConeTriangle}

Scaled-diagonally-dominant-sum-of-squares cone; see [Definition 2, AM17] and NonnegPolyInnerCone.

[AM17] Ahmadi, A. A. & Majumdar, A. DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ArXiv e-prints, 2017.

const DSOSCone = NonnegPolyInnerCone{DiagonallyDominantConeTriangle}

Diagonally-dominant-sum-of-squares cone; see [Definition 2, AM17] and NonnegPolyInnerCone.

[AM17] Ahmadi, A. A. & Majumdar, A. DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ArXiv e-prints, 2017.

struct PSDMatrixInnerCone{MCT <: MOI.AbstractVectorSet} <: PolyJuMP.PolynomialSet
end

Inner approximation of the cone of polynomial matrices P(x) that are positive semidefinite for any x defined by the set of $n \times n$ polynomial matrices such that the polynomial $y^\top P(x) y$ belongs to NonnegPolyInnerCone{MCT} where y is a vector of $n$ auxiliary polynomial variables.

const SOSMatrixCone = PSDMatrixInnerCone{MOI.PositiveSemidefiniteConeTriangle}

Sum-of-squares matrices cone; see [Section 3.3.2, BPT12] and PSDMatrixInnerCone.

[BPT12] Blekherman, G.; Parrilo, P. A. & Thomas, R. R. Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, 2012.

struct ConvexPolyInnerCone{MCT} <: PolyJuMP.PolynomialSet end

Inner approximation of the set of convex polynomials defined by the set of polynomials such that their hessian belongs to to the set PSDMatrixInnerCone{MCT}()

const SOSConvexCone = ConvexPolyInnerCone{MOI.PositiveSemidefiniteConeTriangle}

Sum-of-squares convex polynomials cone; see [Section 3.3.3, BPT12] and ConvexPolyInnerCone.

[BPT12] Blekherman, G.; Parrilo, P. A. & Thomas, R. R. Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, 2012.

struct CopositiveInner{S} <: PolyJuMP.PolynomialSet
    # Inner approximation of the PSD cone, i.e. typically either
    # `SOSCone`, `DSOSCone` or `SDSOSCone`,
    psd_inner::S
end

A symmetric matrix $Q$ is copositive if $x^{\top} Q x \ge 0$ for all vector $x$ in the nonnegative orthant. Checking copositivity is a co-NP-complete problem [MK87] and this cone is only the inner approximation of the cone of copositive symmetric matrices given by Minknowski sum of psd_inner and the cone of symmetric matrices with nonnegative entries (the diagonal entries can be chosen to be zero) [Lemma 3.164, BPT12].

The matrix with nonnegative entries can be interpreted as lagrangian multipliers. For instance,

@polyvar x y
@constraint(model, x^2 - 2x*y + y^2 in CopositiveInner(SOSCone()))

is equivalent to

# Matrix that we require to be copositive
Q = [ 1 -1
     -1  1]
λ = @variable(model, lower_bound=0)
# Symmetric matrix of nonnegative entries
Λ = [0 λ
     λ 0]
using LinearAlgebra # For `Symmetric`
@constraint(model, Symmetric(Q - Λ) in PSDCone())

which is equivalent to

@polyvar x y
λ = @variable(model, lower_bound=0)
@constraint(model, x^2 - 2x*y + y^2 - 2*λ * x*y in SOSCone())

which is the same as, using the domain keyword,

@polyvar x y
@constraint(model, x^2 - 2x*y + y^2 in SOSCone(), domain = @set x*y ≥ 0)

As an important difference with its equivalent forms, the GramMatrixAttribute for the copositive constraint is given by matrix Q while for the equivalent form using the domainkeyword, the value of the attribute would correspond to the the gram matrix in thepsd_innercone, i.e. which should be equal toQ - Λ`.

[BPT12] Blekherman, G.; Parrilo, P. A. & Thomas, R. R. Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, 2012.

[MK87] K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical programming, 39:117–129, 1987.

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{CT <: SumOfSquares.SOSLikeCone, BT <: MB.AbstractPolynomialBasis} <: SimpleIdealCertificate{CT, BT}
    cone::CT
    basis::Type{BT}
    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{CT <: SumOfSquares.SOSLikeCone, BT <: MB.AbstractPolynomialBasis} <: SimpleIdealCertificate{CT, BT}
    cone::CT
    basis::BT
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{CT <: SumOfSquares.SOSLikeCone, BT <: MB.AbstractPolynomialBasis, NPT <: Tuple} <: SimpleIdealCertificate{CT, BT}
    cone::CT
    basis::Type{BT}
    variable_groups::NPT
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{GCT<:AbstractIdealCertificate} <: AbstractIdealCertificate
    gram_certificate::GCT
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.

MomentsAttribute(N)
MomentsAttribute()

A constraint attribute for the vector of moments corresponding to the constraint that a polynomial is zero in the full space in result N. If the polynomial is constrained to be zero in an algebraic set, it is the moments for the constraint once it is rewritten into an constraint on the full space. If N is omitted, it is 1 by default.

Examples

Consider the following program:

@variable(model, α)
@variable(model, β ≤ 1)

using DynamicPolynomials
@polyvar x y
cref = @constraint(model, α * x - β * y == 0, domain = @set x == y)

The constraint is equivalent to

@constraint(model, (α - β) * y == 0)

for which the dual is the 1-element vector with the moment of y of value -1. This is the result of moments(cref). However, the dual of cref obtained by dual(cref) is the 2-elements vector with both the moments of x and y of value -1.

moments(cref::JuMP.ConstraintRef)

Return the MomentsAttribute of cref.

struct GramMatrix{T, B, U, MT <: AbstractMatrix{T}} <: AbstractGramMatrix{T, B, U}
    Q::MT
    basis::B
end

Gram matrix $x^\top Q x$ where Q is a symmetric matrix indexed by the vector of polynomials of the basis basis.

GramMatrixAttribute(N)
GramMatrixAttribute()

A constraint attribute for the GramMatrix of a constraint, that is, the positive semidefinite matrix Q indexed by the monomials in the vector X such that $X^\top Q X$ is the sum-of-squares certificate of the constraint.

gram_matrix(cref::JuMP.ConstraintRef)

Return the GramMatrixAttribute of cref.

gram_operate(::typeof(+), p::GramMatrix, q::GramMatrix)

Computes the Gram matrix equal to the sum between p and q. On the opposite, p + q gives a polynomial equal to p + q. The polynomial p + q can also be obtained by polynomial(gram_operate(+, p, q)).

gram_operate(/, p::GramMatrix, α)

Computes the Gram matrix equal to p / α. On the opposite, p / α gives a polynomial equal to p / α. The polynomial p / α can also be obtained by polynomial(gram_operate(/, p, α)).

MomentMatrixAttribute(N)
MomentMatrixAttribute()

A constraint attribute fot the MomentMatrix of a constraint.

moment_matrix(cref::JuMP.ConstraintRef)

Return the MomentMatrixAttribute of cref.

struct CertificateBasis <: MOI.AbstractConstraintAttribute end

A constraint attribute for the basis indexing the GramMatrixAttribute and MomentMatrixAttribute certificates.

certificate_basis(cref::JuMP.ConstraintRef)

Return the CertificateBasis of cref.

certificate_monomials(cref::JuMP.ConstraintRef)

Return the monomials of certificate_basis. If the basis if not MultivariateBases.AbstractMonomialBasis, an error is thrown.

LagrangianMultipliers(N)
LagrangianMultipliers()

A constraint attribute fot the LagrangianMultipliers associated to the inequalities of the domain of a constraint. There is one multiplier per inequality and no multiplier for equalities as the equalities are handled by reducing the polynomials over the ideal they generate instead of explicitely creating multipliers.

lagrangian_multipliers(cref::JuMP.ConstraintRef)

Return the LagrangianMultipliers of cref.

struct SOSDecomposition{T, PT}

Represents a Sum-of-Squares decomposition without domain.

struct SOSDecompositionWithDomain{T, PT, S}

Represents a Sum-of-Squares decomposition on a basic semi-algebraic domain.

struct SOSDecompositionAttribute
    ranktol::Real
    dec::MultivariateMoments.LowRankLDLTAlgorithm
end

A constraint attribute for the SOSDecomposition of a constraint. By default, it is computed using SOSDecomposition(gram, ranktol, dec) where gram is the value of the GramMatrixAttribute.

sos_decomposition(cref::JuMP.ConstraintRef)

Return the SOSDecompositionAttribute of cref.

sos_decomposition(cref::JuMP.ConstraintRef, K<:AbstractBasicSemialgebraicSet)

Return representation in the quadraic module associated with K.

bridgeable(c::JuMP.AbstractConstraint, S::Type{<:MOI.AbstractSet})

Wrap the constraint c in JuMP.BridgeableConstraints that may be needed to bridge variables constrained in S on creation.

bridgeable(c::JuMP.AbstractConstraint, F::Type{<:MOI.AbstractFunction},
           S::Type{<:MOI.AbstractSet})

Wrap the constraint c in JuMP.BridgeableConstraints that may be needed to bridge F-in-S constraints.

bridges(F::Type{<:MOI.AbstractFunction}, S::Type{<:MOI.AbstractSet})

Return a list of bridges that may be needed to bridge F-in-S constraints but not the bridges that may be needed by constraints added by the bridges.

bridges(S::Type{<:MOI.AbstractSet})

Return a list of bridges that may be needed to bridge variables constrained in S on creation but not the bridges that may be needed by constraints added by the bridges.

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

Return neighbors of node in G.

fill_in(G::Graph{T}, i::T}

Return number of edges that need to be added to make the neighbors of i a clique.

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::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

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

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

struct ScalarPolynomialFunction{P<:MP.AbstractPolynomialLike} <: MOI.AbstractScalarFunction
    p::P
    variables::Vector{MOI.VariableIndex}
end

Defines the polynomial function of the variables variables where the variable variables(p)[i] corresponds to variables[i].

ToPolynomialBridge{T}

ToPolynomialBridge implements the following reformulations:

• $\min \{f(x)\}$ into $\min\{p(x)\}$
• $\max \{f(x)\}$ into $\max\{p(x)\}$

where $f(x)$ is a scalar function and $p(x)$ is a polynomial.

Source node

ToPolynomialBridge supports:

• MOI.ObjectiveFunction{F} where F is a MOI.AbstractScalarFunction for which convert(::Type{PolyJuMP.ScalarPolynomialFunction}, ::Type{F}). That is for instance the case for MOI.VariableIndex, MOI.ScalarAffineFunction and MOI.ScalarQuadraticFunction.

Target nodes

ToPolynomialBridge creates:

• One objective node: MOI.ObjectiveFunction{PolyJuMP.ScalarPolynomialFunction{T}}

ToPolynomialBridge{T,S} <: Bridges.Constraint.AbstractBridge

ToPolynomialBridge implements the following reformulations:

• $f(x) \in S$ into $p(x) \in S$ where $f(x)$ is a scalar function and $p(x)$ is a polynomial.

Source node

ToPolynomialBridge supports:

• F in S where F is a MOI.AbstractScalarFunction for which

convert(::Type{PolyJuMP.ScalarPolynomialFunction}, ::Type{F}). That is for instance the case for MOI.VariableIndex, MOI.ScalarAffineFunction and MOI.ScalarQuadraticFunction.

Target nodes

ToPolynomialBridge creates:

• PolyJuMP.ScalarPolynomialFunction{T} in S

orthogonal_transformation_to(A, B)

Return an orthogonal transformation U such that A = U' * B * U

Given Schur decompositions A = Z_A * S_A * Z_A' B = Z_B * S_B * Z_B' Since P' * S_A * P = D' * S_B * D, we have A = Z_A * P * Z_B' * B * Z_B * P' * Z_A'

_reorder!(F::LinearAlgebra.Schur{T}) where {T}

Given a Schur decomposition of a, reorder it so that its eigenvalues are in in increasing order.

Note that if T<:Real, F.Schur is quasi upper triangular. By (quasi), we mean that there may be nonzero entries in S[i+1,i] representing complex conjugates. In that case, the complex conjugate are permuted together. If T<:Complex, then S is triangular.

_rotate_complex(A::AbstractMatrix{T}, B::AbstractMatrix{T}; tol = Base.rtoldefault(real(T))) where {T}

Given (quasi) upper triangular matrix A and B that have the eigenvalues in the same order except the complex pairs which may need to be (signed) permuted, returns an othogonal matrix P such that P' * A * P and B have matching low triangular part. The upper triangular part will be dealt with by _sign_diag.

By (quasi), we mean that if S is a Matrix{<:Real}, then there may be nonzero entries in S[i+1,i] representing complex conjugates. If S is a Matrix{<:Complex}, then S is upper triangular so there is nothing to do.