# Scaled diagonally dominant programming

In polynomial optimization, one can check the certificate of nonnegativity with sums of squares (SOS) optimization which leads to semidefinite programming. Another more conservative approach is to use SDSOS optimization which leads to scaled diagonally dominant programming (SDDP). SDDP problems can be solved by second-order cone programming because the cone of scaled diagonally dominant matrices is a second-order representable cone. SumOfSquares.jl has both SOS and SDSOS optimization. However, it seems it does not have scaled diagonally dominant programming. I am looking for a package to do scaled diagonally dominant programming. JuMP.jl is capable of doing optimization for rotated second-order cones. However, I do not know how to use that to do SDDP. Would you tell me how I can do that or would you inform me of any package in this regard?

If I understand correctly, youβd like to use the scaled diagonally dominant cone without Sum-of-Squares is that correct ?
If thatβs the case you can do it as follows:

``````using JuMP, LinearAlgebra, SumOfSquares
model = Model()
# This reformulates the scaled diagonally dominant cone into many 2 x 2 PSD cones
# These reformulate 2 x 2 PSD cones into rotated second order cones
Q = Symmetric(rand(5, 5))
q = JuMP.vectorize(Q, JuMP.SymmetricMatrixShape(5))
@constraint(model, q in SumOfSquares.ScaledDiagonallyDominantConeTriangle(5))
``````

You can inspect and verify that it was transformed to rotated SOC with

``````julia> using SCS

julia> set_optimizer(model, SCS.Optimizer)

julia> optimize!(model)
------------------------------------------------------------------
SCS v3.2.4 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 30, constraints m: 45
cones: 	  z: primal zero / dual free vars: 15
q: soc vars: 30, qsize: 10
settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
max_iters: 100000, normalize: 1, rho_x: 1.00e-06
acceleration_lookback: 10, acceleration_interval: 10
compiled with openmp parallelization enabled
lin-sys:  sparse-direct-amd-qdldl
nnz(A): 80, nnz(P): 0
------------------------------------------------------------------
iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
0| 1.18e+00  1.48e-01  1.74e+00  8.68e-01  1.00e-01  1.27e-02
25| 1.29e+14  2.86e+11  1.26e+19  6.32e+18  1.00e-01  2.29e-02
------------------------------------------------------------------
status:  infeasible
timings: total: 2.29e-02s = setup: 1.93e-03s + solve: 2.09e-02s
lin-sys: 2.73e-05s, cones: 1.35e-05s, accel: 4.03e-06s
------------------------------------------------------------------
objective = inf
------------------------------------------------------------------

julia> backend(model)
MOIU.CachingOptimizer
β state: ATTACHED_OPTIMIZER
β mode: AUTOMATIC
β model_cache: MOIU.UniversalFallback{MOIU.Model{Float64}}
β β ObjectiveSense: FEASIBILITY_SENSE
β β ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
β β NumberOfVariables: 0
β β NumberOfConstraints: 1
β   β MOI.VectorAffineFunction{Float64} in SumOfSquares.ScaledDiagonallyDominantConeTriangle: 1
β optimizer: MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{SCS.Optimizer, MOIU.UniversalFallback{MOIU.Model{Float64}}}}
β Variable bridges:
β β SumOfSquares.Bridges.Variable.PositiveSemidefinite2x2Bridge{Float64}
β β SumOfSquares.Bridges.Variable.ScaledDiagonallyDominantBridge{Float64}
β Constraint bridges:
β β MOIB.Constraint.RSOCtoSOCBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables}
β β MOIB.Constraint.VectorSlackBridge{Float64, MOI.VectorAffineFunction{Float64}, SumOfSquares.ScaledDiagonallyDominantConeTriangle}
β Objective bridges: none
β model: MOIU.CachingOptimizer
β state: EMPTY_OPTIMIZER
β mode: AUTOMATIC
β model_cache: MOIU.UniversalFallback{MOIU.Model{Float64}}
β β ObjectiveSense: FEASIBILITY_SENSE
β β ObjectiveFunctionType: MOI.ScalarAffineFunction{Float64}
β β NumberOfVariables: 30
β β NumberOfConstraints: 11
β   β MOI.VectorAffineFunction{Float64} in MOI.Zeros: 1
β   β MOI.VectorAffineFunction{Float64} in MOI.SecondOrderCone: 10
β optimizer: SCS.Optimizer
β ObjectiveSense: unknown
β ObjectiveFunctionType: unknown
β NumberOfVariables: unknown
β NumberOfConstraints: unknown
``````

Note that itβs further transformed to second-order-cone by `Constraint.RSOCtoSOCBridge` because SCS does not support the rotated version.

2 Likes

Exactly thatβs what I meant. Thank you.

1 Like