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, MT <: MP.AbstractMonomial, MVT <: AbstractVector{MT}} <: MP.APL{T}
    Q::SymMatrix{T}
    x::MVT
end

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

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{S}, q::GramMatrix{T})

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{S}, q::GramMatrix{T})

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 CertificateMonomials <: MOI.AbstractConstraintAttribute end

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

certificate_monomials(cref::JuMP.ConstraintRef)

Return the CertificateMonomials of cref.

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.

abstract type AbstractPolynomialBasis end

Polynomial basis of a subspace of the polynomials [Section~3.1.5, BPT12].

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

struct MonomialBasis{MT<:MultivariatePolynomials.AbstractMonomial, MV<:AbstractVector{MT}} <: AbstractPolynomialBasis
    monomials::MV
end

Monomial basis with the monomials of the vector monomials. For instance, MonomialBasis([1, x, y, x^2, x*y, y^2]) is the monomial basis for the subspace of quadratic polynomials in the variables x, y.

struct ScaledMonomialBasis{MT<:MultivariatePolynomials.AbstractMonomial, MV<:AbstractVector{MT}} <: AbstractPolynomialBasis
    monomials::MV
end

Scaled monomial basis (see [Section 3.1.5, BPT12]) with the monomials of the vector monomials. Given a monomial $x^\alpha = x_1^{\alpha_1} \cdots x_n^{\alpha_n}$ of degree $d = \sum_{i=1}^n \alpha_i$, the corresponding polynomial of the basis is

For instance, create a polynomial with the basis $[xy^2, xy]$ creates the polynomial $\sqrt{3} a xy^2 + \sqrt{2} b xy$ where a and b are new JuMP decision variables. Constraining the polynomial $axy^2 + bxy$ to be zero with the scaled monomial basis constrains a/√3 and b/√2 to be zero.

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

struct FixedPolynomialBasis{PT<:MultivariatePolynomials.AbstractPolynomialLike, PV<:AbstractVector{PT}} <: AbstractPolynomialBasis
    polynomials::PV
end

Polynomial basis with the polynomials of the vector polynomials. For instance, FixedPolynomialBasis([1, x, 2x^2-1, 4x^3-3x]) is the Chebyshev polynomial basis for cubic polynomials in the variable x.

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.