Standard form

struct Poly{PB<:AbstractPolynomialBasis} <: AbstractPoly
    polynomial_basis::PB
end

Polynomial variable $v^\top p$ where $v$ is a vector of new decision variables and $p$ is a vector of polynomials for the basis polynomial_basis.

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 (Ahmadi and Majumdar, 2017; Definition 2) and NonnegPolyInnerCone.

const DSOSCone = NonnegPolyInnerCone{DiagonallyDominantConeTriangle}

Diagonally-dominant-sum-of-squares cone; see (Ahmadi and Majumdar, 2017; Definition 2) and NonnegPolyInnerCone.

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 (Blekherman et al., 2012; Section 3.3.2) and PSDMatrixInnerCone.

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 (Blekherman et al., 2012; Section 3.3.3) and ConvexPolyInnerCone.

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 (Murty and Kabadi, 1987) 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) (Blekherman et al., 2012; Lemma 3.164).

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 domain keyword, the value of the attribute would correspond to the the gram matrix in the psd_inner cone, i.e. which should be equal to Q - Λ.

struct Polynomials{M<:Union{Nothing,Int,MP.AbstractMonomial}} <: PolyJuMP.PolynomialSet

Sums of AM/GM Exponential for polynomials.

struct Signomials{M<:Union{Nothing,Int,MP.AbstractMonomial}} <: PolyJuMP.PolynomialSet

Sums of AM/GM Exponential for signomials.

SignomialsBridge{T,S,P,F} <: MOI.Bridges.Constraint.AbstractBridge

We use the Signomials Representative SR equation of [MCW21].

[MCW20] Riley Murray, Venkat Chandrasekaran, Adam Wierman "Newton Polytopes and Relative Entropy Optimization" https://arxiv.org/abs/1810.01614 [MCW21] Murray, Riley, Venkat Chandrasekaran, and Adam Wierman. "Signomials and polynomial optimization via relative entropy and partial dualization." Mathematical Programming Computation 13 (2021): 257-295. https://arxiv.org/pdf/1907.00814.pdf

AGEBridge{T,F,G,H} <: MOI.Bridges.Constraint.AbstractBridge

The nonnegativity of x ≥ 0 in

∑ ci x^αi ≥ -c0 x^α0

can be reformulated as

∑ ci exp(αi'y) ≥ -β exp(α0'y)

In any case, it is shown to be equivalent to

∃ ν ≥ 0 s.t. D(ν, exp(1)*c) ≤ β, ∑ νi αi = α0 ∑ νi [CP16, (3)]

where N(ν, λ) = ∑ νj log(νj/λj) is the relative entropy function. The constant exp(1) can also be moved out of D into

∃ ν ≥ 0 s.t. D(ν, c) - ∑ νi ≤ β, ∑ νi αi = α0 ∑ νi [MCW21, (2)]

The relative entropy cone in MOI is (u, v, w) such that D(w, v) ≥ u. Therefore, we can either encode (β, exp(1)*c, ν) [CP16, (3)] or (β + ∑ νi, c, ν) [MCW21, (2)]. In this bridge, we use the second formulation.

∃ ν ≥ 0 s.t. D(ν, exp(1)*c) ≤ -log(-β), ∑ νi αi = α0, ∑ νi = 1 [CP16, (4)]

[CP16] Chandrasekaran, Venkat, and Parikshit Shah. "Relative entropy relaxations for signomial optimization." SIAM Journal on Optimization 26.2 (2016): 1147-1173. [MCW21] Murray, Riley, Venkat Chandrasekaran, and Adam Wierman. "Signomials and polynomial optimization via relative entropy and partial dualization." Mathematical Programming Computation 13 (2021): 257-295. https://arxiv.org/pdf/1907.00814.pdf

struct SOSPolynomialSet{
    D<:AbstractSemialgebraicSet,
    B<:SA.ExplicitBasis,
    C<:Certificate.AbstractCertificate,
} <: MOI.AbstractVectorSet
    domain::D
    basis::B
    certificate::C
end

The Sum-of-Squares cone is the set of vectors of coefficients a for basis for which the polynomial is a sum-of-squares certificate over domain.

struct WeightedSOSCone{
    M,
    B<:SA.ExplicitBasis,
    G<:SA.ExplicitBasis,
    W<:MP.AbstractPolynomialLike,
} <: MOI.AbstractVectorSet
    basis::B
    gram_bases::Vector{G}
    weights::Vector{W}
end

The weighted sum-of-squares cone is the set of vectors of coefficients a in basis that are the sum of weights[i] multiplied by a gram matrix with basis gram_bases[i]. The matrix cone type M is used to decide in which cone the gram matrix is constrained, e.g., MOI.PositiveSemidefiniteConeTriangle or SumOfSquares.ScaledDiagonallyDominantConeTriangle.

See (Papp and Yıldız, 2017; Section 1.1) and (Kapelevich et al., 2023; Section 1).

struct EmptyCone <: MOI.AbstractSymmetricMatrixSetTriangle end

Cone of positive semidefinite matrices of 0 rows and 0 columns. It is reformulated into no constraints which is useful as some solvers do not support positive semidefinite cones of dimension zero.

struct PositiveSemidefinite2x2ConeTriangle <: MOI.AbstractSymmetricMatrixSetTriangle end

Cone of positive semidefinite matrices of 2 rows and 2 columns. It is reformulated into an MOI.RotatedSecondOrderCone constraint, see for instance (Fawzi, 2018; Equation (1)).

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

See (Ahmadi and Majumdar, 2017; Definition 4) for a precise definition of the last two items.

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

See (Ahmadi and Majumdar, 2017; Definition 4) for a precise definition of the last two items.

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.

struct ScalarPolynomialFunction{T,P<:MP.AbstractPolynomial{T}} <: MOI.AbstractScalarFunction
    polynomial::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

ImageBridge{T,F,G,MT,MVT,CT} <: Bridges.Constraint.AbstractBridge

ImageBridge implements a reformulation from SOSPolynomialSet{SemialgebraicSets.FullSpace} into the positive semidefinite cone.

Let Σ be the SOS cone of polynomials of degree 2d and S be the PSD cone. There is a linear relation Σ = A(S). The linear relation reads: p belongs to Σ iff there exists q in S such that A(q) = p. This allows defining a variable bridge that would create variables p and substitute A(q) for p but this is not the purpose of this bridge. This bridge exploit the following alternative read: p belongs to Σ iff there exists q in S such that $q \in A^{-1}(p)$ where $A^{-1}$ is the preimage of p. This preimage can be obtained as $A^\dagger p + \mathrm{ker}(A)$ where $A^\dagger$ is the pseudo-inverse of A. It turns out that for polynomial bases indexed by monomials, A is close to row echelon form so $A^\dagger$ and $\mathrm{ker}(A)$ can easily be obtained.

This is best described in an example. Consider the SOS constraint for the polynomial p = 2x^4 + 2x^3 * y - x^2 * y^2 + 5y^4 with gram basis b = [x^2, y^2, x * y] of (Parrilo, 2003; Example 6.1). The product b * b' is

\[\begin{bmatrix} x^4 & x^2 y^2 & x^3 y\\ x^2 y^2 & y^4 & x y^3\\ x^3 y & x y^3 & x^2 y^2 \end{bmatrix}\]

Except for the entries (1, 2) and (3, 3), all entries are unique so the value of the corresponding gram matrix is given by the corresponding coefficient of p. For the entries (1, 2) and (3, 3), we let -λ be the (1, 2) and (3, 3) entries and we add 2λ for the (3, 3) entry so as to parametrize entries for which the sum is the corresponding coefficient in p, i.e., -1. The gram matrix is therefore:

\[\begin{bmatrix} 2 & -\lambda & 1\\ -\lambda & 5 & 0\\ 1 & 0 & 2\lambda - 1 \end{bmatrix}\]

Source node

ImageBridge supports:

• H in SOSPolynomialSet{SemialgebraicSets.FullSpace}

Target nodes

ImageBridge creates one of the following, depending on the length of the gram basis:

• F in MOI.PositiveSemidefiniteConeTriangle, for gram basis of length at least 3
• F in SumOfSquares.PositiveSemidefinite2x2ConeTriangle, for gram basis of length 2
• F in MOI.Nonnegatives, for gram basis of length 1
• F in SumOfSquares.EmptyCone, for empty gram basis

in addition to

• a constraint G in MOI.Zeros in case there is a monomial in s.monomials that cannot be obtained as product of elements in a gram basis.

struct ScaledDiagonallyDominantBridge{T} <: MOI.Bridges.Variable.AbstractBridge
    side_dimension::Int
    variables::Vector{Vector{MOI.VariableIndex}}
    constraints::Vector{MOI.ConstraintIndex{
        MOI.VectorOfVariables, SOS.PositiveSemidefinite2x2ConeTriangle}}
end

A matrix is SDD iff it is the sum of psd matrices Mij that are zero except for entries ii, ij and jj (Ahmadi and Majumdar, 2017; Lemma 9). This bridge substitute the constrained variables in SOS.ScaledDiagonallyDominantConeTriangle into a sum of constrained variables in SOS.PositiveSemidefinite2x2ConeTriangle.