# Scaled diagonally dominant programming

**URL:** <https://discourse.julialang.org/t/scaled-diagonally-dominant-programming/116853>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, matrices\
**Created:** [July 10, 2024, 6:24am UTC](https://discourse.julialang.org/t/scaled-diagonally-dominant-programming/116853 "2024-07-10T06:24:19Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Khashayar-Neshat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/khashayar-neshat/32/42852_2.png) [@Khashayar-Neshat](https://discourse.julialang.org/u/Khashayar-Neshat)\
**Post date:** [July 10, 2024, 6:24am UTC](https://discourse.julialang.org/t/scaled-diagonally-dominant-programming/116853/1 "2024-07-10T06:24:20Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![blegat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blegat/32/217090_2.png) [@blegat](https://discourse.julialang.org/u/blegat)\
**Post date:** [July 10, 2024, 7:14am UTC](https://discourse.julialang.org/t/scaled-diagonally-dominant-programming/116853/2 "2024-07-10T07:14:07Z")

</div>

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:

```julia
using JuMP, LinearAlgebra, SumOfSquares
model = Model()
# This reformulates the scaled diagonally dominant cone into many 2 x 2 PSD cones
JuMP.add_bridge(model, SumOfSquares.Bridges.Variable.ScaledDiagonallyDominantBridge)
# These reformulate 2 x 2 PSD cones into rotated second order cones
JuMP.add_bridge(model, SumOfSquares.Bridges.Variable.PositiveSemidefinite2x2Bridge)
JuMP.add_bridge(model, SumOfSquares.Bridges.Constraint.PositiveSemidefinite2x2Bridge)
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
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.

---

<div class="post-metadata">

**Author:** ![Khashayar-Neshat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/khashayar-neshat/32/42852_2.png) [@Khashayar-Neshat](https://discourse.julialang.org/u/Khashayar-Neshat)\
**Post date:** [July 11, 2024, 8:47pm UTC](https://discourse.julialang.org/t/scaled-diagonally-dominant-programming/116853/3 "2024-07-11T20:47:52Z")

</div>

Exactly that’s what I meant. Thank you.