How does Dualization.jl solve a SOS but not compute it?

Specific Domains Optimization (Mathematical)
1

Hi,

While solving a conic optimization problem, I needed to compute its dual, so I used Dualization.jl. However, it does not support the constraints modeled by SumOfSquares.jl, resulting in the following error:

Constraints of the Function MathOptInterface.VectorAffineFunction{Float64} in the set SumOfSquares.SOSPolynomialSet{FullSpace, DynamicPolynomials.Monomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}}, MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}}, SumOfSquares.Certificate.Newton{CopositiveInner{SOSCone}, MonomialBasis, SumOfSquares.Certificate.NewtonFilter{SumOfSquares.Certificate.NewtonDegreeBounds{Tuple{}}}}} are not yet implemented.

I am wondering how it can solve the dual problem nonetheless.

using JuMP, MosekTools, LinearAlgebra, SumOfSquares, DynamicPolynomials, Dualization

# Define the data for the optimization problems
Q = [0.0  0.0  0.0; 0.0  1.0  2.0; 0.0  2.0  3.0]
A = [0.0  0.5  0.5; 0.5  0.0  0.0; 0.5  0.0  0.0]
b = 2
n = size(Q, 1)

# Define the dual optimization problem
model_dual = Model(dual_optimizer(Mosek.Optimizer))

@variable(model_dual, v)
@variable(model_dual, Y[1:n, 1:n], Symmetric)

# Using CopositiveInner
@polyvar x[1:n]
@constraint(model_dual, sum(x[i] * Y[i, j] * x[j] for i in 1:n for j in 1:n) in CopositiveInner(SOSCone()))

@objective(model_dual, Max, v * b)

@constraint(model_dual, Q - v * A - Y .== 0)

# Optimize the dual model
optimize!(model_dual)
solution_summary(model_dual)
# dual_model = dualize(model_dual)
2

This is a question for @blegat. I assume we know how to take the dual of CopositiveInner(SOSCone()) but not SumOfSquares.SOSPolynomialSet.

3

The duals of the SOS cones are not implemented yet. You can Dualization.dual_optimizer though. This will work because Dualization knows that it doesn’t support the SOS cones so they will get bridged to the PSD cones before the dualization layer and the solver gets the dual form of the SDP. See On the importance of Dualization · SumOfSquares for more details