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

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.

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