Optimizers

mutable struct Model{T} <: MOI.ModelLike

Model storing a polynomial optimization problem

min  f(x)
s.t. x ∈ S

where f is the polynomial of the field objective_function (or nothing for a feasibility problem) whose optimization sense is given by the field objective_sense, and S is the semialgebraic set of the field set, starting from SemialgebraicSets.FullSpace() and intersected with each added polynomial constraint. The field variables maps each MOI.VariableIndex to the corresponding polynomial variable.

struct Solution{T}
    values::Vector{T}
    objective_value::T
    max_constraint_violation::T
    status::MOI.ResultStatusCode
end

Candidate solution of the polynomial optimization problem stored in a Model, where values are the values of the variables sorted as MP.variables(model), objective_value is the value of the objective function at values, max_constraint_violation is the maximum violation of the constraints at values and status is MOI.FEASIBLE_POINT, MOI.NEARLY_FEASIBLE_POINT or MOI.INFEASIBLE_POINT depending on max_constraint_violation.

Solution(values::Vector{T}, model::Model{T}, feasibility_tolerance::T)

Compute the solution with values values for model, where status is MOI.FEASIBLE_POINT if max_constraint_violation < feasibility_tolerance, MOI.NEARLY_FEASIBLE_POINT if it is smaller than 100feasibility_tolerance and MOI.INFEASIBLE_POINT otherwise.

abstract type AbstractPolynomialOptimizer{T} <: MOI.AbstractOptimizer end

Optimizer for polynomial optimization problems storing the problem in a Model.

Subtypes should be mutable structs with the fields

model::PolyJuMP.Model{T}
solve_time::Float64

and implement _invalidate! and _optimize!.

abstract type AbstractRelaxationOptimizer{T} <: AbstractPolynomialOptimizer{T} end

Optimizer computing a bound on the objective value of a polynomial optimization problem

min  f(x)
s.t. g_i(x) ≥ 0
     h_j(x) = 0

by solving the relaxation

max  t
s.t. f - t - Σ_i σ_i * g_i - Σ_j μ_j * h_j ∈ C
     σ_i ∈ C

where μ_j are free polynomials and C is the cone of certified nonnegative polynomials returned by nonnegativity_cone (and conversely for a max problem). The bound is the objective value of this relaxation and is returned as the MOI.ObjectiveBound. The degrees of the multipliers σ_i and μ_j are given by the MultiplierMaxdegree constraint attribute. Candidate primal solutions may in addition be recovered from the solution of the relaxation by implementing recover_solutions; the MOI.ResultCount is the number of recovered candidates.

Subtypes should be mutable structs with the fields

model::PolyJuMP.Model{T}
multiplier_maxdegree::Dict{MOI.ConstraintIndex,Int}
solver::Any
relaxation::Union{Nothing,JuMP.GenericModel{T}}
solutions::Vector{PolyJuMP.Solution{T}}
feasibility_tolerance::T
solve_time::Float64

and implement nonnegativity_cone and recover_solutions.

nonnegativity_cone(model::AbstractRelaxationOptimizer)

Return the set (e.g., PolyJuMP.SAGE.Polynomials() or SumOfSquares.SOSCone()) in which a polynomial is constrained to belong as a sufficient condition for its nonnegativity.

recover_solutions(
    model::AbstractRelaxationOptimizer{T},
    relaxation::JuMP.GenericModel{T},
    cref::JuMP.ConstraintRef,
    lagrangian,
) where {T}

Return a vector of candidate Solutions recovered from the solution of relaxation, where cref is the constraint of the lagrangian polynomial in the cone nonnegativity_cone. Return an empty vector if no solution is recovered; PolyJuMP.SAGE.Optimizer implements the recovery from the dual of cref of [MCW21, Section 4.2].

[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

MultiplierMaxdegree()

A constraint attribute for the maximum degree of the multiplier of the constraint in the certificate of nonnegativity of the Lagrangian used by an AbstractRelaxationOptimizer. Increasing this degree gives a higher level of the hierarchy of relaxations, hence a possibly tighter objective bound at the price of a larger relaxation. By default, the degree d - maxdegree(g) is used for a constraint of polynomial g where d is the smallest even number larger than the maximum degree of the objective and constraint polynomials.

Optimizer{T}(solver)

Optimizer computing a bound on the objective value of a polynomial optimization problem using its Lasserre / Sum-of-Squares relaxation, see PolyJuMP.AbstractRelaxationOptimizer with the cone SOSCone as certificate of nonnegativity. The level of the hierarchy is chosen for each constraint with the PolyJuMP.MultiplierMaxdegree constraint attribute. The relaxation is solved with solver and the bound can be queried with MOI.ObjectiveBound().

Optimizer{T}(solver; feasibility_tolerance = sqrt(Base.rtoldefault(T)))

Optimizer computing a bound on the objective value of a polynomial optimization problem using its SAGE relaxation, see PolyJuMP.AbstractRelaxationOptimizer with the cone Polynomials as certificate of nonnegativity [CP16; MCW21]. The relaxation is solved with solver and the bound can be queried with MOI.ObjectiveBound(). Candidate solutions are in addition recovered from the dual of the relaxation following [MCW21, Section 4.2]; the candidates are classified as feasible up to feasibility_tolerance (see MOI.PrimalStatus) and sorted by objective value.

[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