Constraints

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.

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} <: AbstractGramMatrix{T, B, U}
    Q::SymMatrix{T}
    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_sum(p, q)).

gram_operate(/, p::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_sum(p, q)).

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}

Represend SOSDecomposition without domain

struct SOSDecompositionWithDomain{T, PT, S}

Represend SOSDecomposition on a basic semi-algebraic domain.

function sos_decomposition(cref::JuMP.ConstraintRef, ranktol::Float64, dec::MultivariateMoments.lowrankchol)

Return representation as a sum of squares.

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

Return representation in the quadraic module associated with K.

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 constrained variables in S 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.

chordal_extension(G::LabelledGraph{T})

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