Scaled diagonally dominant programming

Specific Domains Optimization (Mathematical)
,
1

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?

2

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
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> 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
3

Exactly that’s what I meant. Thank you.

1 Like