search

jump-dev / SumOfSquares.jl

Sum of Squares Programming for Julia
Other
115 stars 24 forks source link

unexpected behavior switching between Mosek and SCS solvers -- different optimal values #269

Closed samhopkins closed 1 year ago

samhopkins commented 1 year ago

I am working on a problem involving optimizing a polynomial over an ideal. I've put together an SoS-style SDP for this, using SumOfSquares.jl. I'll give a full example replicating this behavior below, but the flavor of the thing is:

model = SoSModel(...)
x = PolyVar{true}("x")
y = PolyVar{true}("y")
z = PolyVar{true}("z")

p = (some polynomial of x,y,z)
obj = (some polynomial of x,y,z)

mons = monomials([x,y,z], 0:2)

@variable(model, multiplier_coeffs[1:length(mons)])

q = (multiplier_coeffs' * mons) * p

@variable(model, t)
@objective(model, Min, t)
@constraint(model, t - obj - q >= 0)

JuMP.optimize!(model)

The weird thing is: I get different optimal values if i use SoSModel(SCS.Optimizer) versus SoSModel(Mosek.Optimizer). Unless I am misreading the outputs of Mosek and SCS, the difference in optimal values is well outside the error tolerance/duality gaps. I would love some help diagnosing this issue -- is this a bug in SoSTools? JuMP? My code?

Here's the smallest counterexample I have so far:

using SumOfSquares
using DynamicPolynomials
using MosekTools
using LinearAlgebra
using SCS
using JuMP

X = [0.5459627556242905,
    1.7288950489507429,
    0.7167681447476535]

Y = [ -54.06002080721971,
    173.77393714162503,
    71.48154370522498]

model = SOSModel(SCS.Optimizer)

n = 3

W = [PolyVar{true}("w" * string(i)) for i=1:n]
alpha = PolyVar{true}("alpha")
beta = PolyVar{true}("beta")

d = 2

ab_mons = monomials([alpha,beta], 0:d)

# build boolean ideal
@variable(model, p_coeff[1:n,1:length(ab_mons)])
p = sum([(p_coeff[i,:]' * ab_mons) * (W[i] - W[i]^2) for i in 1:n])

# build objective function
@variable(model, t)
obj = sum(W)

# one more ideal generator
r1_gen = sum([W[i] * X[i] * ( beta * X[i] + alpha - Y[i]) for i in 1:n])

# multiplier for the ideal
@variable(model, r1_coeff[1:length(ab_mons)])
r1 = (r1_coeff' * ab_mons) * r1_gen 

@constraint(model, t - obj - p - r1>= 0)
@objective(model, Min, t)

@show objective_value(model)

On my machine, using SCS I get objective value 2.039893, while using Mosek I get objective value 2.9999121506536075 (i.e., 3, up to numerical error).

Please let me know if there's anything else I can provide. In the meantime I'll start looking for a smaller counterexample.

samhopkins commented 1 year ago

For reference, here's the full output when run with Mosek:

Problem
  Name                   :                 
  Objective sense        : minimize        
  Type                   : CONIC (conic optimization problem)
  Constraints            : 67              
  Affine conic cons.     : 0               
  Disjunctive cons.      : 0               
  Cones                  : 0               
  Scalar variables       : 25              
  Matrix variables       : 1               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 9
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 2                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : minimize        
  Type                   : CONIC (conic optimization problem)
  Constraints            : 67              
  Affine conic cons.     : 0               
  Disjunctive cons.      : 0               
  Cones                  : 0               
  Scalar variables       : 25              
  Matrix variables       : 1               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 46
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 14                conic                  : 14              
Optimizer  - Semi-definite variables: 1                 scalarized             : 55              
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 1081              after factor           : 1081            
Factor     - dense dim.             : 0                 flops                  : 4.44e+04        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   1.0e+00  1.0e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.00  
1   2.7e-01  2.7e-01  3.0e-01  -6.58e-03  8.306264924e-01   1.494043574e+00   2.7e-01  0.00  
2   2.4e-02  2.4e-02  4.9e-03  6.92e-01   1.753264970e+00   1.743134319e+00   2.4e-02  0.00  
3   5.4e-03  5.4e-03  7.8e-04  7.45e-01   1.683748734e+00   1.689436447e+00   5.4e-03  0.00  
4   1.1e-03  1.1e-03  9.0e-05  6.32e-01   1.611692762e+00   1.614206562e+00   1.1e-03  0.00  
5   3.1e-04  3.1e-04  3.3e-05  3.07e-01   1.658378874e+00   1.666942976e+00   3.1e-04  0.00  
6   8.7e-05  8.7e-05  7.6e-06  3.28e-01   1.689764442e+00   1.696514310e+00   8.7e-05  0.00  
7   1.9e-05  1.9e-05  2.9e-06  -1.67e-01  1.804147181e+00   1.826683476e+00   1.9e-05  0.00  
8   4.7e-06  4.7e-06  5.6e-07  2.64e-01   1.912918054e+00   1.927301381e+00   4.7e-06  0.00  
9   1.2e-06  1.2e-06  1.4e-07  1.61e-01   1.987100031e+00   2.000923905e+00   1.2e-06  0.00  
10  2.3e-07  2.3e-07  3.9e-08  -5.19e-02  2.085190584e+00   2.115464744e+00   2.3e-07  0.00  
11  7.2e-08  5.2e-08  1.4e-08  -4.82e-01  2.357908276e+00   2.428966265e+00   5.4e-08  0.00  
12  2.6e-08  1.5e-08  3.3e-09  4.36e-02   2.723577891e+00   2.772203720e+00   1.5e-08  0.00  
13  9.3e-09  4.3e-09  4.5e-10  7.51e-01   2.917392397e+00   2.928514207e+00   4.2e-09  0.00  
14  5.6e-09  9.5e-10  4.9e-11  8.92e-01   2.988493611e+00   2.991112942e+00   9.5e-10  0.00  
15  1.1e-09  1.5e-10  3.4e-12  9.91e-01   2.997348779e+00   2.997820897e+00   1.6e-10  0.01  
16  8.0e-10  4.8e-12  1.8e-14  9.98e-01   2.999912136e+00   2.999926599e+00   4.8e-12  0.01  
17  8.0e-10  4.8e-12  1.8e-14  9.98e-01   2.999912136e+00   2.999926599e+00   4.8e-12  0.01  
18  8.0e-10  4.8e-12  1.8e-14  9.98e-01   2.999912136e+00   2.999926599e+00   4.8e-12  0.01  
19  7.9e-10  6.4e-12  1.8e-14  1.00e+00   2.999912151e+00   2.999926611e+00   4.8e-12  0.01  
20  7.9e-10  5.5e-12  1.8e-14  1.00e+00   2.999912151e+00   2.999926611e+00   4.8e-12  0.01  
Optimizer terminated. Time: 0.01    

  0.012575 seconds (9.42 k allocations: 723.805 KiB)
objective_value(model) = 2.9999121506536075

and with SCS:

------------------------------------------------------------------
           SCS v3.2.1 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 80, constraints m: 122
cones:    z: primal zero / dual free vars: 67
      s: psd vars: 55, ssize: 1
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
lin-sys:  sparse-direct-amd-qdldl
      nnz(A): 201, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 2.21e+01  1.00e+00  2.23e+01 -1.10e+01  1.00e-01  5.67e-03 
   250| 3.77e-03  2.10e-04  1.23e-03  1.58e+00  1.00e-01  1.28e-02 
   500| 3.44e-03  2.86e-05  9.75e-04  1.58e+00  1.00e-01  2.27e-02 
   750| 3.13e-03  4.89e-05  1.18e-03  1.58e+00  1.00e-01  3.40e-02 
  1000| 3.14e+01  3.50e+00  8.30e-03  1.56e+00  1.00e-01  3.90e-02 
  1250| 2.43e-03  6.64e-05  1.55e-03  1.59e+00  1.00e-01  4.48e-02 
  1500| 2.64e-03  7.25e-05  1.69e-03  1.59e+00  1.00e-01  5.35e-02 
  1750| 2.81e-03  7.75e-05  1.79e-03  1.59e+00  1.00e-01  5.97e-02 
  2000| 2.93e-03  8.12e-05  1.87e-03  1.60e+00  1.00e-01  6.53e-02 
  2250| 9.41e-03  1.35e-04  5.99e-03  1.62e+00  1.00e-01  7.44e-02 
  2500| 1.11e-02  5.50e-04  7.20e-03  1.64e+00  1.00e-01  8.14e-02 
  2750| 2.59e-03  7.58e-05  1.64e-03  1.64e+00  1.00e-01  9.09e-02 
  3000| 2.66e-03  7.32e-05  1.62e-03  1.64e+00  1.00e-01  1.06e-01 
  3250| 2.74e-03  7.14e-05  1.59e-03  1.65e+00  1.00e-01  1.23e-01 
  3500| 2.81e-03  6.98e-05  1.55e-03  1.65e+00  1.00e-01  1.38e-01 
  3750| 2.88e-03  6.84e-05  1.52e-03  1.65e+00  1.00e-01  1.46e-01 
  4000| 2.94e-03  6.70e-05  1.49e-03  1.65e+00  1.00e-01  1.50e-01 
  4250| 3.01e-03  6.56e-05  1.46e-03  1.66e+00  1.00e-01  1.58e-01 
  4500| 3.06e-03  6.42e-05  1.43e-03  1.66e+00  1.00e-01  1.66e-01 
  4750| 7.29e+00  6.59e-01  3.81e-04  1.85e+00  1.00e-01  1.71e-01 
  5000| 3.16e-03  6.14e-05  1.37e-03  1.66e+00  1.00e-01  1.79e-01 
  5250| 3.20e-03  6.01e-05  1.34e-03  1.67e+00  1.00e-01  1.95e-01 
  5500| 3.25e-03  5.89e-05  1.31e-03  1.67e+00  1.00e-01  2.04e-01 
  5750| 3.28e-03  5.77e-05  1.29e-03  1.67e+00  1.00e-01  2.14e-01 
  6000| 3.32e-03  5.66e-05  1.26e-03  1.67e+00  1.00e-01  2.20e-01 
  6250| 3.35e-03  5.55e-05  1.24e-03  1.68e+00  1.00e-01  2.26e-01 
  6500| 3.38e-03  5.44e-05  1.21e-03  1.68e+00  1.00e-01  2.36e-01 
  6750| 3.41e-03  5.33e-05  1.19e-03  1.68e+00  1.00e-01  2.43e-01 
  7000| 3.44e-03  5.23e-05  1.17e-03  1.68e+00  1.00e-01  2.59e-01 
  7250| 3.46e-03  5.13e-05  1.14e-03  1.69e+00  1.00e-01  2.77e-01 
  7500| 4.53e+01  5.79e+00  2.39e-04  3.05e+00  1.00e-01  2.92e-01 
  7750| 3.51e-03  4.94e-05  1.10e-03  1.69e+00  1.00e-01  3.10e-01 
  8000| 3.53e-03  4.86e-05  1.08e-03  1.69e+00  1.00e-01  3.21e-01 
  8250| 3.54e-03  4.77e-05  1.06e-03  1.70e+00  1.00e-01  3.40e-01 
  8500| 3.56e-03  4.68e-05  1.04e-03  1.70e+00  1.00e-01  3.54e-01 
  8750| 3.58e-03  4.60e-05  1.02e-03  1.70e+00  1.00e-01  3.65e-01 
  9000| 3.59e-03  4.52e-05  1.00e-03  1.71e+00  1.00e-01  3.79e-01 
  9250| 3.61e-03  4.45e-05  9.85e-04  1.71e+00  1.00e-01  4.20e-01 
  9500| 3.62e-03  4.37e-05  9.68e-04  1.71e+00  1.00e-01  4.72e-01 
  9750| 3.63e-03  4.30e-05  9.51e-04  1.71e+00  1.00e-01  4.84e-01 
 10000| 3.64e-03  4.23e-05  9.35e-04  1.72e+00  1.00e-01  4.96e-01 
 10250| 1.53e+02  1.95e+01  1.20e-03  6.36e+00  1.00e-01  5.09e-01 
 10500| 3.66e-03  4.10e-05  9.04e-04  1.72e+00  1.00e-01  5.20e-01 
 10750| 3.67e-03  4.04e-05  8.89e-04  1.72e+00  1.00e-01  5.26e-01 
 11000| 3.68e-03  3.98e-05  8.74e-04  1.73e+00  1.00e-01  5.42e-01 
 11250| 3.68e-03  3.92e-05  8.60e-04  1.73e+00  1.00e-01  5.46e-01 
 11500| 3.69e-03  3.86e-05  8.46e-04  1.73e+00  1.00e-01  5.61e-01 
 11750| 3.70e-03  3.81e-05  8.32e-04  1.73e+00  1.00e-01  5.71e-01 
 12000| 3.70e-03  3.75e-05  8.19e-04  1.74e+00  1.00e-01  5.90e-01 
 12250| 3.71e-03  3.70e-05  8.07e-04  1.74e+00  1.00e-01  6.04e-01 
 12500| 3.71e-03  3.65e-05  7.94e-04  1.74e+00  1.00e-01  6.18e-01 
 12750| 3.71e-03  3.60e-05  7.82e-04  1.74e+00  1.00e-01  6.27e-01 
 13000| 1.19e+02  1.52e+01  2.74e-03  5.50e+00  1.00e-01  6.42e-01 
 13250| 3.52e-03  3.46e-04  2.26e-03  1.75e+00  3.16e-01  6.47e-01 
 13500| 3.57e-03  3.25e-04  2.17e-03  1.76e+00  3.16e-01  6.53e-01 
 13750| 3.58e-03  3.13e-04  2.08e-03  1.76e+00  3.16e-01  6.66e-01 
 14000| 1.79e+01  6.80e+00  7.37e+00 -3.81e+00  3.16e-01  6.69e-01 
 14250| 3.60e-03  2.92e-04  1.93e-03  1.78e+00  3.16e-01  6.77e-01 
 14500| 3.61e-03  2.82e-04  1.86e-03  1.79e+00  3.16e-01  6.82e-01 
 14750| 3.61e-03  2.73e-04  1.79e-03  1.80e+00  3.16e-01  7.04e-01 
 15000| 3.61e-03  2.65e-04  1.73e-03  1.80e+00  3.16e-01  7.20e-01 
 15250| 3.60e-03  2.57e-04  1.67e-03  1.81e+00  3.16e-01  7.35e-01 
 15500| 3.60e-03  2.50e-04  1.61e-03  1.82e+00  3.16e-01  7.40e-01 
 15750| 3.60e-03  2.43e-04  1.55e-03  1.83e+00  3.16e-01  7.47e-01 
 16000| 3.59e-03  2.36e-04  1.50e-03  1.83e+00  3.16e-01  7.61e-01 
 16250| 3.58e-03  2.29e-04  1.45e-03  1.84e+00  3.16e-01  7.65e-01 
 16500| 3.57e-03  2.23e-04  1.41e-03  1.85e+00  3.16e-01  7.85e-01 
 16750| 1.34e+01  5.43e+00  4.48e-04  3.17e+00  3.16e-01  7.93e-01 
 17000| 3.55e-03  2.12e-04  1.32e-03  1.86e+00  3.16e-01  8.02e-01 
 17250| 3.53e-03  2.07e-04  1.28e-03  1.87e+00  3.16e-01  8.09e-01 
 17500| 3.52e-03  2.01e-04  1.24e-03  1.88e+00  3.16e-01  8.17e-01 
 17750| 3.50e-03  1.96e-04  1.20e-03  1.88e+00  3.16e-01  8.24e-01 
 18000| 3.49e-03  1.92e-04  1.17e-03  1.89e+00  3.16e-01  8.29e-01 
 18250| 3.47e-03  1.87e-04  1.14e-03  1.90e+00  3.16e-01  8.37e-01 
 18500| 3.45e-03  1.83e-04  1.10e-03  1.90e+00  3.16e-01  8.47e-01 
 18750| 3.43e-03  1.78e-04  1.07e-03  1.91e+00  3.16e-01  8.63e-01 
 19000| 3.41e-03  1.74e-04  1.04e-03  1.92e+00  3.16e-01  8.74e-01 
 19250| 3.39e-03  1.70e-04  1.01e-03  1.92e+00  3.16e-01  8.88e-01 
 19500| 1.70e+02  6.70e+01  7.49e+00 -1.12e+01  3.16e-01  9.00e-01 
 19750| 3.34e-03  1.62e-04  9.59e-04  1.94e+00  3.16e-01  9.20e-01 
 20000| 3.31e-03  1.59e-04  9.33e-04  1.94e+00  3.16e-01  9.46e-01 
 20250| 3.28e-03  1.56e-04  9.08e-04  1.95e+00  3.16e-01  9.52e-01 
 20500| 3.24e-03  1.54e-04  8.82e-04  1.96e+00  3.16e-01  9.55e-01 
 20750| 3.19e-03  1.55e-04  8.56e-04  1.96e+00  3.16e-01  9.63e-01 
 21000| 3.13e-03  1.62e-04  8.28e-04  1.97e+00  3.16e-01  9.71e-01 
 21250| 3.06e-03  1.81e-04  7.95e-04  1.97e+00  3.16e-01  9.77e-01 
 21500| 2.95e-03  2.21e-04  7.55e-04  1.98e+00  3.16e-01  9.87e-01 
 21750| 2.80e-03  2.87e-04  7.07e-04  1.98e+00  3.16e-01  9.92e-01 
 22000| 2.57e-03  3.77e-04  6.50e-04  1.99e+00  3.16e-01  9.96e-01 
 22250| 1.02e+01  2.92e+00  5.53e-05  2.01e+00  3.16e-01  1.01e+00 
 22500| 1.86e-03  5.90e-04  5.24e-04  1.99e+00  3.16e-01  1.01e+00 
 22750| 1.47e-03  6.66e-04  4.62e-04  1.99e+00  3.16e-01  1.02e+00 
 23000| 1.23e-03  6.97e-04  4.02e-04  1.99e+00  3.16e-01  1.02e+00 
 23250| 1.07e-03  6.80e-04  3.45e-04  2.00e+00  3.16e-01  1.03e+00 
 23500| 9.12e-04  6.20e-04  2.91e-04  2.00e+00  3.16e-01  1.04e+00 
 23750| 7.67e-04  5.23e-04  2.43e-04  2.00e+00  3.16e-01  1.06e+00 
 24000| 6.41e-04  4.03e-04  2.02e-04  2.00e+00  3.16e-01  1.07e+00 
 24250| 5.57e-04  2.80e-04  1.71e-04  2.00e+00  3.16e-01  1.07e+00 
 24500| 5.26e-04  1.79e-04  1.49e-04  2.00e+00  3.16e-01  1.08e+00 
 24750| 5.05e-04  1.12e-04  1.34e-04  2.00e+00  3.16e-01  1.09e+00 
 25000| 1.07e+00  3.68e-01  5.65e-03  2.00e+00  3.16e-01  1.10e+00 
 25250| 4.79e-04  5.68e-05  1.19e-04  2.00e+00  3.16e-01  1.11e+00 
 25500| 4.71e-04  4.47e-05  1.15e-04  2.00e+00  3.16e-01  1.12e+00 
 25750| 4.64e-04  3.78e-05  1.13e-04  2.00e+00  3.16e-01  1.13e+00 
 26000| 4.58e-04  3.34e-05  1.10e-04  2.00e+00  3.16e-01  1.14e+00 
 26250| 4.53e-04  3.01e-05  1.08e-04  2.00e+00  3.16e-01  1.15e+00 
 26500| 4.48e-04  2.73e-05  1.06e-04  2.00e+00  3.16e-01  1.15e+00 
 26750| 4.43e-04  2.50e-05  1.04e-04  2.00e+00  3.16e-01  1.16e+00 
 27000| 4.39e-04  2.30e-05  1.03e-04  2.00e+00  3.16e-01  1.16e+00 
 27250| 4.35e-04  2.13e-05  1.01e-04  2.00e+00  3.16e-01  1.17e+00 
 27500| 4.32e-04  1.97e-05  9.99e-05  2.00e+00  3.16e-01  1.18e+00 
 27750| 6.91e-01  1.98e-01  1.08e-04  2.04e+00  3.16e-01  1.18e+00 
 28000| 4.25e-04  1.72e-05  9.74e-05  2.00e+00  3.16e-01  1.19e+00 
 28250| 4.22e-04  1.61e-05  9.62e-05  2.00e+00  3.16e-01  1.21e+00 
 28500| 4.19e-04  1.52e-05  9.51e-05  2.00e+00  3.16e-01  1.22e+00 
 28750| 4.16e-04  1.43e-05  9.41e-05  2.00e+00  3.16e-01  1.23e+00 
 29000| 4.13e-04  1.35e-05  9.31e-05  2.00e+00  3.16e-01  1.24e+00 
 29250| 4.11e-04  1.28e-05  9.21e-05  2.00e+00  3.16e-01  1.24e+00 
 29500| 4.10e-04  1.21e-05  9.12e-05  2.00e+00  3.16e-01  1.25e+00 
 29750| 4.13e-04  1.15e-05  9.03e-05  2.00e+00  3.16e-01  1.26e+00 
 30000| 4.15e-04  1.10e-05  8.95e-05  2.01e+00  3.16e-01  1.26e+00 
 30250| 4.17e-04  1.05e-05  8.87e-05  2.01e+00  3.16e-01  1.27e+00 
 30500| 4.95e-01  1.75e-01  2.36e-05  2.05e+00  3.16e-01  1.28e+00 
 30750| 4.21e-04  9.54e-06  8.71e-05  2.01e+00  3.16e-01  1.29e+00 
 31000| 4.23e-04  9.13e-06  8.64e-05  2.01e+00  3.16e-01  1.29e+00 
 31250| 4.24e-04  8.75e-06  8.57e-05  2.01e+00  3.16e-01  1.31e+00 
 31500| 4.26e-04  8.39e-06  8.50e-05  2.01e+00  3.16e-01  1.31e+00 
 31750| 4.27e-04  8.06e-06  8.43e-05  2.01e+00  3.16e-01  1.32e+00 
 32000| 4.29e-04  7.75e-06  8.37e-05  2.01e+00  3.16e-01  1.34e+00 
 32250| 4.30e-04  7.45e-06  8.30e-05  2.01e+00  3.16e-01  1.35e+00 
 32500| 4.31e-04  7.18e-06  8.24e-05  2.01e+00  3.16e-01  1.36e+00 
 32750| 4.32e-04  6.91e-06  8.18e-05  2.01e+00  3.16e-01  1.36e+00 
 33000| 4.33e-04  6.67e-06  8.12e-05  2.01e+00  3.16e-01  1.36e+00 
 33250| 5.88e-01  2.38e-01  1.66e-04  2.06e+00  3.16e-01  1.38e+00 
 33500| 4.35e-04  6.29e-06  8.01e-05  2.01e+00  3.16e-01  1.39e+00 
 33750| 4.36e-04  6.22e-06  7.95e-05  2.01e+00  3.16e-01  1.39e+00 
 34000| 4.36e-04  6.16e-06  7.90e-05  2.01e+00  3.16e-01  1.39e+00 
 34250| 4.37e-04  6.09e-06  7.84e-05  2.01e+00  3.16e-01  1.41e+00 
 34500| 4.38e-04  6.03e-06  7.79e-05  2.01e+00  3.16e-01  1.42e+00 
 34750| 4.38e-04  5.97e-06  7.74e-05  2.01e+00  3.16e-01  1.44e+00 
 35000| 4.39e-04  5.91e-06  7.69e-05  2.01e+00  3.16e-01  1.44e+00 
 35250| 4.39e-04  5.86e-06  7.64e-05  2.01e+00  3.16e-01  1.44e+00 
 35500| 4.39e-04  5.80e-06  7.59e-05  2.01e+00  3.16e-01  1.46e+00 
 35750| 4.40e-04  5.75e-06  7.54e-05  2.01e+00  3.16e-01  1.47e+00 
 36000| 7.88e-01  3.19e-01  1.83e-05  2.07e+00  3.16e-01  1.48e+00 
 36250| 4.40e-04  5.65e-06  7.45e-05  2.01e+00  3.16e-01  1.49e+00 
 36500| 4.41e-04  5.60e-06  7.40e-05  2.01e+00  3.16e-01  1.50e+00 
 36750| 4.41e-04  5.55e-06  7.36e-05  2.01e+00  3.16e-01  1.50e+00 
 37000| 4.41e-04  5.50e-06  7.31e-05  2.01e+00  3.16e-01  1.51e+00 
 37250| 4.41e-04  5.46e-06  7.27e-05  2.01e+00  3.16e-01  1.52e+00 
 37500| 4.41e-04  5.41e-06  7.23e-05  2.01e+00  3.16e-01  1.52e+00 
 37750| 4.41e-04  5.37e-06  7.18e-05  2.01e+00  3.16e-01  1.53e+00 
 38000| 4.41e-04  5.33e-06  7.14e-05  2.01e+00  3.16e-01  1.53e+00 
 38250| 4.41e-04  5.29e-06  7.10e-05  2.01e+00  3.16e-01  1.54e+00 
 38500| 4.41e-04  5.25e-06  7.06e-05  2.01e+00  3.16e-01  1.55e+00 
 38750| 9.94e-01  4.02e-01  2.48e-05  2.09e+00  3.16e-01  1.55e+00 
 39000| 4.41e-04  5.17e-06  6.98e-05  2.01e+00  3.16e-01  1.56e+00 
 39250| 4.42e-04  5.13e-06  6.94e-05  2.01e+00  3.16e-01  1.57e+00 
 39500| 4.42e-04  5.09e-06  6.90e-05  2.01e+00  3.16e-01  1.58e+00 
 39750| 4.41e-04  5.06e-06  6.86e-05  2.01e+00  3.16e-01  1.59e+00 
 40000| 4.41e-04  5.02e-06  6.82e-05  2.01e+00  3.16e-01  1.60e+00 
 40250| 4.41e-04  4.98e-06  6.79e-05  2.01e+00  3.16e-01  1.61e+00 
 40500| 4.41e-04  4.95e-06  6.75e-05  2.01e+00  3.16e-01  1.61e+00 
 40750| 4.41e-04  4.91e-06  6.71e-05  2.01e+00  3.16e-01  1.62e+00 
 41000| 4.41e-04  4.88e-06  6.67e-05  2.01e+00  3.16e-01  1.63e+00 
 41250| 4.41e-04  4.85e-06  6.64e-05  2.01e+00  3.16e-01  1.63e+00 
 41500| 1.29e+00  5.22e-01  1.46e-04  2.11e+00  3.16e-01  1.64e+00 
 41750| 4.40e-04  4.78e-06  6.57e-05  2.01e+00  3.16e-01  1.65e+00 
 42000| 4.40e-04  4.75e-06  6.53e-05  2.01e+00  3.16e-01  1.66e+00 
 42250| 4.40e-04  4.72e-06  6.50e-05  2.01e+00  3.16e-01  1.66e+00 
 42500| 4.40e-04  4.69e-06  6.46e-05  2.01e+00  3.16e-01  1.67e+00 
 42750| 4.39e-04  4.66e-06  6.43e-05  2.01e+00  3.16e-01  1.68e+00 
 43000| 4.39e-04  4.63e-06  6.39e-05  2.01e+00  3.16e-01  1.69e+00 
 43250| 4.39e-04  4.60e-06  6.36e-05  2.01e+00  3.16e-01  1.69e+00 
 43500| 4.38e-04  4.57e-06  6.33e-05  2.01e+00  3.16e-01  1.70e+00 
 43750| 4.38e-04  4.54e-06  6.29e-05  2.01e+00  3.16e-01  1.71e+00 
 44000| 4.38e-04  4.51e-06  6.26e-05  2.01e+00  3.16e-01  1.71e+00 
 44250| 1.64e+00  6.62e-01  2.46e-04  2.13e+00  3.16e-01  1.72e+00 
 44500| 4.37e-04  4.46e-06  6.20e-05  2.01e+00  3.16e-01  1.73e+00 
 44750| 4.36e-04  4.43e-06  6.16e-05  2.01e+00  3.16e-01  1.74e+00 
 45000| 4.36e-04  4.41e-06  6.13e-05  2.01e+00  3.16e-01  1.75e+00 
 45250| 4.36e-04  4.38e-06  6.10e-05  2.01e+00  3.16e-01  1.75e+00 
 45500| 4.35e-04  4.35e-06  6.07e-05  2.01e+00  3.16e-01  1.76e+00 
 45750| 4.35e-04  4.33e-06  6.04e-05  2.01e+00  3.16e-01  1.77e+00 
 46000| 4.34e-04  4.30e-06  6.01e-05  2.01e+00  3.16e-01  1.78e+00 
 46250| 4.34e-04  4.28e-06  5.98e-05  2.01e+00  3.16e-01  1.78e+00 
 46500| 4.33e-04  4.25e-06  5.95e-05  2.01e+00  3.16e-01  1.79e+00 
 46750| 4.33e-04  4.23e-06  5.92e-05  2.01e+00  3.16e-01  1.80e+00 
 47000| 2.01e+00  8.12e-01  4.58e-04  2.15e+00  3.16e-01  1.82e+00 
 47250| 4.32e-04  4.18e-06  5.86e-05  2.02e+00  3.16e-01  1.83e+00 
 47500| 4.31e-04  4.15e-06  5.83e-05  2.02e+00  3.16e-01  1.84e+00 
 47750| 4.31e-04  4.13e-06  5.80e-05  2.02e+00  3.16e-01  1.85e+00 
 48000| 4.30e-04  4.11e-06  5.77e-05  2.02e+00  3.16e-01  1.86e+00 
 48250| 4.30e-04  4.08e-06  5.74e-05  2.02e+00  3.16e-01  1.86e+00 
 48500| 4.29e-04  4.06e-06  5.71e-05  2.02e+00  3.16e-01  1.87e+00 
 48750| 4.27e-04  3.71e-05  1.78e-04  2.02e+00  1.00e+00  1.87e+00 
 49000| 4.25e-04  3.90e-05  1.74e-04  2.02e+00  1.00e+00  1.88e+00 
 49250| 4.23e-04  3.84e-05  1.71e-04  2.02e+00  1.00e+00  1.89e+00 
 49500| 4.21e-04  3.78e-05  1.69e-04  2.02e+00  1.00e+00  1.89e+00 
 49750| 4.20e-04  3.72e-05  1.67e-04  2.02e+00  1.00e+00  1.90e+00 
 50000| 4.18e-04  3.66e-05  1.64e-04  2.02e+00  1.00e+00  1.91e+00 
 50250| 1.28e+00  1.64e+00  1.30e-03  2.27e+00  1.00e+00  1.91e+00 
 50500| 4.14e-04  3.55e-05  1.59e-04  2.02e+00  1.00e+00  1.92e+00 
 50750| 4.13e-04  3.49e-05  1.57e-04  2.02e+00  1.00e+00  1.93e+00 
 51000| 4.11e-04  3.44e-05  1.55e-04  2.02e+00  1.00e+00  1.93e+00 
 51250| 4.09e-04  3.39e-05  1.53e-04  2.02e+00  1.00e+00  1.93e+00 
 51500| 4.08e-04  3.34e-05  1.51e-04  2.02e+00  1.00e+00  1.94e+00 
 51750| 4.06e-04  3.29e-05  1.48e-04  2.02e+00  1.00e+00  1.95e+00 
 52000| 4.04e-04  3.24e-05  1.46e-04  2.02e+00  1.00e+00  1.95e+00 
 52250| 4.02e-04  3.19e-05  1.44e-04  2.02e+00  1.00e+00  1.96e+00 
 52500| 4.01e-04  3.14e-05  1.42e-04  2.02e+00  1.00e+00  1.97e+00 
 52750| 3.99e-04  3.10e-05  1.40e-04  2.02e+00  1.00e+00  1.97e+00 
 53000| 8.58e-01  1.10e+00  1.03e-03  2.21e+00  1.00e+00  1.98e+00 
 53250| 3.96e-04  3.01e-05  1.37e-04  2.02e+00  1.00e+00  1.99e+00 
 53500| 3.94e-04  2.97e-05  1.35e-04  2.02e+00  1.00e+00  1.99e+00 
 53750| 3.92e-04  2.92e-05  1.33e-04  2.02e+00  1.00e+00  2.00e+00 
 54000| 3.91e-04  2.88e-05  1.31e-04  2.02e+00  1.00e+00  2.01e+00 
 54250| 3.89e-04  2.84e-05  1.30e-04  2.02e+00  1.00e+00  2.01e+00 
 54500| 3.87e-04  2.81e-05  1.28e-04  2.02e+00  1.00e+00  2.02e+00 
 54750| 3.86e-04  2.77e-05  1.26e-04  2.02e+00  1.00e+00  2.03e+00 
 55000| 3.84e-04  2.73e-05  1.25e-04  2.02e+00  1.00e+00  2.04e+00 
 55250| 3.83e-04  2.69e-05  1.23e-04  2.02e+00  1.00e+00  2.05e+00 
 55500| 3.81e-04  2.66e-05  1.22e-04  2.02e+00  1.00e+00  2.05e+00 
 55750| 6.54e-01  8.36e-01  6.88e-04  2.18e+00  1.00e+00  2.06e+00 
 56000| 3.78e-04  2.59e-05  1.19e-04  2.02e+00  1.00e+00  2.07e+00 
 56250| 3.77e-04  2.56e-05  1.17e-04  2.03e+00  1.00e+00  2.08e+00 
 56500| 3.75e-04  2.52e-05  1.16e-04  2.03e+00  1.00e+00  2.10e+00 
 56750| 3.74e-04  2.49e-05  1.14e-04  2.03e+00  1.00e+00  2.11e+00 
 57000| 3.72e-04  2.46e-05  1.13e-04  2.03e+  2.761732 seconds (7.15 k allocations: 628.164 KiB)
objective_value(model) = 2.0398619151667488
00  1.00e+00  2.12e+00 
 57250| 3.71e-04  2.43e-05  1.12e-04  2.03e+00  1.00e+00  2.13e+00 
 57500| 3.69e-04  2.40e-05  1.10e-04  2.03e+00  1.00e+00  2.14e+00 
 57750| 3.68e-04  2.37e-05  1.09e-04  2.03e+00  1.00e+00  2.16e+00 
 58000| 3.67e-04  2.34e-05  1.08e-04  2.03e+00  1.00e+00  2.17e+00 
 58250| 3.65e-04  2.31e-05  1.06e-04  2.03e+00  1.00e+00  2.18e+00 
 58500| 5.27e-01  6.73e-01  4.65e-04  2.17e+00  1.00e+00  2.19e+00 
 58750| 3.62e-04  2.26e-05  1.04e-04  2.03e+00  1.00e+00  2.20e+00 
 59000| 3.61e-04  2.23e-05  1.03e-04  2.03e+00  1.00e+00  2.21e+00 
 59250| 3.60e-04  2.21e-05  1.02e-04  2.03e+00  1.00e+00  2.21e+00 
 59500| 3.59e-04  2.18e-05  1.01e-04  2.03e+00  1.00e+00  2.23e+00 
 59750| 3.57e-04  2.16e-05  9.95e-05  2.03e+00  1.00e+00  2.24e+00 
 60000| 3.56e-04  2.13e-05  9.85e-05  2.03e+00  1.00e+00  2.25e+00 
 60250| 3.55e-04  2.11e-05  9.74e-05  2.03e+00  1.00e+00  2.25e+00 
 60500| 3.54e-04  2.09e-05  9.64e-05  2.03e+00  1.00e+00  2.26e+00 
 60750| 3.52e-04  2.07e-05  9.54e-05  2.03e+00  1.00e+00  2.27e+00 
 61000| 3.51e-04  2.04e-05  9.44e-05  2.03e+00  1.00e+00  2.28e+00 
 61250| 4.34e-01  5.55e-01  4.48e-04  2.15e+00  1.00e+00  2.28e+00 
 61500| 3.49e-04  2.00e-05  9.24e-05  2.03e+00  1.00e+00  2.29e+00 
 61750| 3.48e-04  1.98e-05  9.15e-05  2.03e+00  1.00e+00  2.30e+00 
 62000| 3.46e-04  1.96e-05  9.06e-05  2.03e+00  1.00e+00  2.31e+00 
 62250| 3.45e-04  1.94e-05  8.97e-05  2.03e+00  1.00e+00  2.32e+00 
 62500| 3.44e-04  1.92e-05  8.88e-05  2.03e+00  1.00e+00  2.34e+00 
 62750| 3.43e-04  1.90e-05  8.79e-05  2.03e+00  1.00e+00  2.35e+00 
 63000| 3.42e-04  1.88e-05  8.71e-05  2.03e+00  1.00e+00  2.37e+00 
 63250| 3.41e-04  1.86e-05  8.63e-05  2.03e+00  1.00e+00  2.39e+00 
 63500| 3.40e-04  1.84e-05  8.54e-05  2.03e+00  1.00e+00  2.39e+00 
 63750| 3.39e-04  1.83e-05  8.46e-05  2.03e+00  1.00e+00  2.40e+00 
 64000| 3.65e-01  4.67e-01  2.79e-04  2.14e+00  1.00e+00  2.41e+00 
 64250| 3.36e-04  1.79e-05  8.31e-05  2.03e+00  1.00e+00  2.42e+00 
 64500| 3.35e-04  1.77e-05  8.23e-05  2.03e+00  1.00e+00  2.43e+00 
 64750| 3.34e-04  1.76e-05  8.16e-05  2.03e+00  1.00e+00  2.45e+00 
 65000| 3.33e-04  1.74e-05  8.08e-05  2.03e+00  1.00e+00  2.46e+00 
 65250| 3.32e-04  1.72e-05  8.01e-05  2.03e+00  1.00e+00  2.48e+00 
 65500| 3.31e-04  1.71e-05  7.94e-05  2.03e+00  1.00e+00  2.50e+00 
 65750| 3.30e-04  1.69e-05  7.87e-05  2.03e+00  1.00e+00  2.50e+00 
 66000| 3.29e-04  1.68e-05  7.80e-05  2.03e+00  1.00e+00  2.52e+00 
 66250| 3.28e-04  1.66e-05  7.74e-05  2.03e+00  1.00e+00  2.54e+00 
 66500| 3.27e-04  1.65e-05  7.67e-05  2.03e+00  1.00e+00  2.55e+00 
 66750| 3.15e-01  4.03e-01  2.26e-04  2.14e+00  1.00e+00  2.55e+00 
 67000| 3.25e-04  1.62e-05  7.54e-05  2.04e+00  1.00e+00  2.56e+00 
 67250| 3.25e-04  1.61e-05  7.48e-05  2.04e+00  1.00e+00  2.57e+00 
 67500| 3.24e-04  1.59e-05  7.42e-05  2.04e+00  1.00e+00  2.57e+00 
 67750| 3.23e-04  1.58e-05  7.36e-05  2.04e+00  1.00e+00  2.58e+00 
 68000| 3.22e-04  1.57e-05  7.30e-05  2.04e+00  1.00e+00  2.59e+00 
 68250| 3.21e-04  1.55e-05  7.24e-05  2.04e+00  1.00e+00  2.60e+00 
 68500| 3.20e-04  1.54e-05  7.19e-05  2.04e+00  1.00e+00  2.60e+00 
 68750| 3.19e-04  1.53e-05  7.13e-05  2.04e+00  1.00e+00  2.61e+00 
 69000| 3.18e-04  1.52e-05  7.07e-05  2.04e+00  1.00e+00  2.62e+00 
 69250| 3.17e-04  1.50e-05  7.02e-05  2.04e+00  1.00e+00  2.63e+00 
 69500| 2.79e-01  3.57e-01  2.39e-04  2.14e+00  1.00e+00  2.63e+00 
 69750| 3.16e-04  1.48e-05  6.91e-05  2.04e+00  1.00e+00  2.64e+00 
 70000| 3.15e-04  1.47e-05  6.86e-05  2.04e+00  1.00e+00  2.65e+00 
 70250| 3.14e-04  1.46e-05  6.81e-05  2.04e+00  1.00e+00  2.66e+00 
 70500| 3.13e-04  1.45e-05  6.76e-05  2.04e+00  1.00e+00  2.67e+00 
 70750| 3.12e-04  1.44e-05  6.71e-05  2.04e+00  1.00e+00  2.67e+00 
 71000| 3.12e-04  1.43e-05  6.66e-05  2.04e+00  1.00e+00  2.68e+00 
 71250| 3.11e-04  1.41e-05  6.61e-05  2.04e+00  1.00e+00  2.69e+00 
 71500| 3.10e-04  1.40e-05  6.57e-05  2.04e+00  1.00e+00  2.70e+00 
 71750| 3.09e-04  1.39e-05  6.52e-05  2.04e+00  1.00e+00  2.70e+00 
 72000| 3.08e-04  1.38e-05  6.47e-05  2.04e+00  1.00e+00  2.71e+00 
 72250| 2.53e-01  3.23e-01  1.45e-04  2.13e+00  1.00e+00  2.72e+00 
 72500| 3.07e-04  1.36e-05  6.39e-05  2.04e+00  1.00e+00  2.72e+00 
 72750| 3.06e-04  1.35e-05  6.34e-05  2.04e+00  1.00e+00  2.73e+00 
 73000| 3.05e-04  1.34e-05  6.30e-05  2.04e+00  1.00e+00  2.73e+00 
 73250| 3.04e-04  1.34e-05  6.26e-05  2.04e+00  1.00e+00  2.74e+00 
 73425| 3.04e-04  1.33e-05  6.23e-05  2.04e+00  1.00e+00  2.75e+00 
------------------------------------------------------------------
status:  solved
timings: total: 2.75e+00s = setup: 2.70e-03s + solve: 2.75e+00s
     lin-sys: 2.67e-01s, cones: 2.02e+00s, accel: 3.65e-01s
------------------------------------------------------------------
objective = 2.039893
------------------------------------------------------------------
samhopkins commented 1 year ago

One more followup, explaining the example a little bit --

In the example we have 5 symbolic variables, $w_1,w_2,w_3,\alpha,\beta$, and six numbers $X_1,X_2,X_3,Y_1,Y_2,Y_3$, and we are trying to maximize $\sum w_i$ subject to $w_i^2 = w_i$ (i.e. $w_i$'s are boolean) and $\sum w_i X_i (X_i \beta + \alpha - Y_i) = 0$.

Note that this optimization problem has a nearly-feasible solution with $w_1 = w_2 = w_3 = 1$, $\alpha = -96.6442179237748$, and $\beta = 160.8249567162244$. Which means that what SCS is saying can't be right; the best upper bound here has to be $3$ (via the constraints $w_i^2 = w_i$ you should get the upper bound of $3$).

For fun, I ran with CSDP as well; it agrees (more or less) with SCS. Here's the output:

CSDP 6.2.0
Iter:  0 Ap: 0.00e+00 Pobj:  0.0000000e+00 Ad: 0.00e+00 Dobj:  0.0000000e+00 
Iter:  1 Ap: 9.31e-01 Pobj: -1.6135092e+00 Ad: 9.01e-01 Dobj: -3.4160350e+00 
Iter:  2 Ap: 8.98e-01 Pobj: -5.7107815e+00 Ad: 6.52e-01 Dobj: -2.1654628e+01 
Iter:  3 Ap: 7.95e-01 Pobj: -6.3717702e+00 Ad: 8.84e-01 Dobj: -1.2646548e+00 
Iter:  4 Ap: 9.15e-01 Pobj: -4.7156275e+00 Ad: 9.42e-01 Dobj: -1.0205745e+00 
Iter:  5 Ap: 8.11e-01 Pobj: -2.4310395e+00 Ad: 9.50e-01 Dobj: -1.2787369e+00 
Iter:  6 Ap: 7.14e-01 Pobj: -2.2031852e+00 Ad: 7.31e-01 Dobj: -2.0111946e+00 
Iter:  7 Ap: 7.32e-01 Pobj: -2.1301561e+00 Ad: 7.99e-01 Dobj: -2.1757786e+00 
Iter:  8 Ap: 8.77e-01 Pobj: -2.0852556e+00 Ad: 9.40e-01 Dobj: -2.2458908e+00 
Iter:  9 Ap: 8.79e-01 Pobj: -2.0191882e+00 Ad: 9.03e-01 Dobj: -2.2527854e+00 
Iter: 10 Ap: 1.00e+00 Pobj: -2.0141262e+00 Ad: 8.87e-01 Dobj: -2.2543288e+00 
Iter: 11 Ap: 1.00e+00 Pobj: -2.0123325e+00 Ad: 1.00e+00 Dobj: -2.2545924e+00 
Iter: 12 Ap: 1.00e+00 Pobj: -2.0122468e+00 Ad: 9.93e-01 Dobj: -2.2546185e+00 
  0.507623 seconds (14.60 k allocations: 1.061 MiB)
objective_value(model) = 2.012251800157392
Stuck at edge of primal feasibility, giving up. 
Failure: return code is 5 
Primal objective value: -2.0122518e+00 
Dual objective value: -2.2546326e+00 
Relative primal infeasibility: 2.06e-05 
Relative dual infeasibility: 5.86e-07 
Real Relative Gap: -4.60e-02 
XZ Relative Gap: 2.47e-06 
DIMACS error measures: 2.81e-05 0.00e+00 9.34e-07 0.00e+00 -4.60e-02 2.47e-06

So, CSDP doesn't solve all the way, but it says that opt should be between 2.01 and 2.25, which is consistent with SCS but inconsistent with Mosek.

blegat commented 1 year ago

It seems Mosek doesn't converge, the solution_summary gives

* Solver : Mosek

* Status
  Result count       : 1
  Termination status : SLOW_PROGRESS
  Message from the solver:
  "Mosek.MSK_RES_TRM_STALL"

* Candidate solution (result #1)
  Primal status      : UNKNOWN_RESULT_STATUS
  Dual status        : UNKNOWN_RESULT_STATUS
  Objective value    : 2.96375e+00
  Objective bound    : 2.96375e+00
  Relative gap       : 0.00000e+00
  Dual objective value : 2.96955e+00

* Work counters
  Solve time (sec)   : 1.01804e-02
  Simplex iterations : 0
  Barrier iterations : 18
  Node count         : 0
samhopkins commented 1 year ago

Maybe I'm misreading the output of solution summary, but it looks like Mosek has bounded the optimum value between 2.96375 and 2.96955, no? (That is pretty confusing because we're solving a minimization problem, so the dual bound should be less than the best primal feasible solution...)

odow commented 1 year ago

Maybe I'm misreading the output of solution summary

The bits to read are:

Termination status : SLOW_PROGRESS Primal status : UNKNOWN_RESULT_STATUS Dual status : UNKNOWN_RESULT_STATUS

Mosek failed. It didn't find an optimal solution, and it isn't sure what the current solution values represent. Typically, we'd expect

Termination status : OPTIMAL Primal status : FEASIBLE_POINT Dual status : FEASIBLE_POINT

samhopkins commented 1 year ago

a) thanks for the quick attention -- I really appreciate it!! b) that's very strange to me -- it's not such a crazy SDP. Is there some rule of thumb advice for what to do when Mosek doesn't converge? c) the issue with SCS and CSDP still seems unresolved -- it seems like they are giving optimal values which should be infeasible (their optimal values are around 2, and it shouldn't be possible to do better than 3)

odow commented 1 year ago

c) the issue with SCS and CSDP still seems unresolved

In most cases, I would say trust Mosek over SCS and CSDP. If Mosek can't solve it and SCS and CSDP are reporting solutions, then it's likely that the solutions they report are incorrect, and that Mosek is "correct" in it being a difficult SDP to solve.

lkapelevich commented 1 year ago

Hi @samhopkins. Not sure if this helps, but regarding the output from the second-order solvers: we can't use the objective values early on to conclude that the optimal objective value is in some interval. It's normal for the primal/dual objectives to oscillate throughout the solve.

odow commented 1 year ago

Closing because this is not a bug in SumOfSquares.jl. Mosek doesn't converge for this problem.