Constraints

MomentsAttribute(result_index)
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(
    multiplier_index::Int = 0,
    result_index::Int = 1,
)

A constraint attribute for the GramMatrix of the multiplier_indexth Sum-of-Squares polynomial $s_i(x)$ where $i$ is multiplier_index of the certificate:

\[p(x) = s_0(x) + w_1(x) s_1(x) + \cdots + w_m(x) s_m(x)\]

The gram matrix of a Sum-of-Squares polynomial $s_i(x)$ is the the positive semidefinite matrix $Q$ such that $s_i(x) = b_i(x)^\top Q b_i(x)$ where $b_i(x)$ is the gram basis.

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(
    multiplier_index::Int = 0,
    result_index::Int = 1,
)

A constraint attribute for the MomentMatrix of the multiplier_indexth Sum-of-Squares polynomial $s_i(x)$ where $i$ is multiplier_index of the certificate:

\[p(x) = s_0(x) + w_1(x) s_1(x) + \cdots + w_m(x) s_m(x)\]

It corresponds to the dual of the Sum-of-Squares constraint for the constraint for $s_i(x)$ to be a Sum-of-Squares.

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.SubBasis, an error is thrown.

LagrangianMultipliers(result_index::Int)
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,A,V,U}

Represents a Sum-of-Squares decomposition without domain.

struct SOSDecompositionWithDomain{A,T,V,U,S}

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

@kwdef struct SOSDecompositionAttribute
    multiplier_index::Int = 0
    ranktol::Real
    dec::MultivariateMoments.LowRankLDLTAlgorithm
    result_index::Int
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.

struct MultiplierIndexBoundsError{AttrType} <: Exception
    attr::AttrType
    range::UnitRange{Int}
end

An error indicating that the requested attribute attr could not be retrieved, because the multiplier index is out of the range of valid indices.

struct Decomposition{T, PT}

Represents a SAGE decomposition.

struct DecompositionAttribute{T} <: MOI.AbstractConstraintAttribute
    tol::T
end

A constraint attribute for the Decomposition of a constraint.

round_solution(
    μ,
    K::AbstractSemialgebraicSet,
    objective = nothing;
    rounding::AbstractRounding = FirstMomentRounding(),
    kws...,
)

Heuristically finds a feasible point of K from the moments of the measure μ, which is usually obtained with moment_matrix after solving a Sum-of-Squares program. Candidate points are generated by rounding and are projected onto K with heuristic_projection to which the keyword arguments kws are passed. If objective is nothing, the first feasible point is returned. Otherwise, the feasible point minimizing objective is returned. Returns nothing if no feasible point was found. The point is a vector of values for the variables variables(μ), sorted in the same order as the center of the atoms returned by atomic_measure.

Unlike atomic_measure, this does not require the moment matrix to be flat. However, the point found is not necessarily a global minimizer, it only provides an upper bound on the optimal objective value of the polynomial optimization problem.

abstract type AbstractRounding end

Strategy used by round_solution to generate candidate points from the moments of a measure. The candidates are then projected onto the feasible set with heuristic_projection.

FirstMomentRounding()

The only candidate is the vector of first-order moments $(\mathbb{E}[x_1], \ldots, \mathbb{E}[x_n])$. If the measure is a Dirac measure at a minimizer, this is the minimizer.

GaussianRounding(; num_samples::Int = 100, rng = Random.default_rng())

The candidates are the vector $\mu$ of first-order moments followed by num_samples samples of the Gaussian distribution $\mathcal{N}(\mu, \Sigma)$ where $\Sigma = \mathbb{E}[x x^\top] - \mu\mu^\top$ is the covariance matrix of the measure. This Gaussian has the same moments of order up to 2 as the measure. For the MAX-CUT problem, this generalizes the random hyperplane rounding of Goemans and Williamson.

rounding_candidates(μ, vars, rounding::AbstractRounding)

Return a vector of candidate points, i.e., vectors of values for the variables vars built from the moments of μ.

heuristic_projection(
    K::AbstractSemialgebraicSet,
    vars,
    x::AbstractVector;
    tol = 1e-8,
    max_guesses::Int = 10length(vars),
)

Heuristically finds a point of K close to the point x of values for the variables vars. Returns nothing if no point was found.

The variables are fixed one by one. If a constraint has only one variable that is not fixed yet, this variable is set to the closest value to its current value that satisfies all constraints in which it is the only non-fixed variable. This is cheap as it amounts to finding the real roots of univariate polynomials. Otherwise, a variable of a constraint with the fewest non-fixed variables is fixed at its current value, backtracking if this leads to an infeasible univariate subproblem. At most max_guesses such guesses are tried. Any point that is returned satisfies the equalities p(x) = 0 with abs(p(x)) <= tol and the inequalities p(x) >= 0 with p(x) >= -tol.

For instance, if K is defined by 0 <= x <= 1 and y <= x^2, x is first projected onto [0, 1] and then y is projected onto (-∞, x^2].