search

cvxgrp / scs

Splitting Conic Solver
MIT License
553 stars 136 forks source link

SCS Not Run to Run Deterministic #229

Closed imbacalvin closed 2 years ago

imbacalvin commented 2 years ago

It seems that SCS is not run to run deterministic. Is there a way to make it deterministic (e.g. by setting a seed variable)? Thanks!

bodono commented 2 years ago

It should be deterministic up to floating point roundoff error. What non-determinism are you seeing?

imbacalvin commented 2 years ago

Hi Brendan, thanks for the instantaneous reply!

Specifications

Description

Using SCS to solve the same problem multiple times gives slightly different solution/objective value each time.

How to reproduce

import cvxpy as cp
import numpy as np

Id=np.eye(2)
P=np.array([[0.5,0,0,-0.5],[0,1,0,0],[0,0,1,0],[-0.5,0,0,0.5]])
X=cp.Variable((4,4),hermitian=True)
XTP=sum(np.kron(Id[j],Id) @ X @ (np.kron(Id[j],Id).T) for j in range(2))
A=np.eye(4)
obj = cp.Minimize(cp.norm(X-A,'fro'))
constraints = [P@X@P>>0, cp.pnorm(XTP,1)<=1e-8]
prob = cp.Problem(obj,constraints)

print(prob.solve(solver=cp.SCS))
print(prob.solve(solver=cp.SCS))
print(prob.solve(solver=cp.SCS))
print(prob.solve(solver=cp.SCS))
print(prob.solve(solver=cp.SCS))
bodono commented 2 years ago

That's because CVXPY is warm-starting the solve from the previous solution, which is already a solution so SCS is terminating after one step (it always takes at least one step):

===============================================================================
                                     CVXPY
                                     v1.2.1
===============================================================================
(CVXPY) Aug 23 11:51:51 AM: Your problem has 16 variables, 2 constraints, and 0 parameters.
(CVXPY) Aug 23 11:51:51 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Aug 23 11:51:51 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Aug 23 11:51:51 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Compiling problem (target solver=SCS).
(CVXPY) Aug 23 11:51:51 AM: Reduction chain: Complex2Real -> Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> SCS
(CVXPY) Aug 23 11:51:51 AM: Applying reduction Complex2Real
(CVXPY) Aug 23 11:51:51 AM: Applying reduction Dcp2Cone
(CVXPY) Aug 23 11:51:51 AM: Applying reduction CvxAttr2Constr
(CVXPY) Aug 23 11:51:51 AM: Applying reduction ConeMatrixStuffing
(CVXPY) Aug 23 11:51:51 AM: Applying reduction SCS
(CVXPY) Aug 23 11:51:51 AM: Finished problem compilation (took 1.340e-02 seconds).
-------------------------------------------------------------------------------
                                Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Invoking solver SCS  to obtain a solution.
------------------------------------------------------------------
           SCS v3.2.1 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 51, constraints m: 122
cones:    l: linear vars: 9
      q: soc vars: 77, qsize: 21
      s: psd vars: 36, ssize: 1
settings: eps_abs: 1.0e-05, eps_rel: 1.0e-05, 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): 189, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 2.00e+01  1.00e+00  2.04e+01 -9.79e+00  1.00e-01  7.02e-04
   150| 1.42e-05  3.98e-07  3.91e-06  2.00e+00  1.00e-01  3.57e-03
------------------------------------------------------------------
status:  solved
timings: total: 3.58e-03s = setup: 4.33e-04s + solve: 3.15e-03s
     lin-sys: 2.92e-04s, cones: 8.51e-04s, accel: 1.81e-03s
------------------------------------------------------------------
objective = 2.000002
------------------------------------------------------------------
-------------------------------------------------------------------------------
                                    Summary
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Problem status: optimal
(CVXPY) Aug 23 11:51:51 AM: Optimal value: 2.000e+00
(CVXPY) Aug 23 11:51:51 AM: Compilation took 1.340e-02 seconds
(CVXPY) Aug 23 11:51:51 AM: Solver (including time spent in interface) took 3.750e-03 seconds
2.0000125717653163
===============================================================================
                                     CVXPY
                                     v1.2.1
===============================================================================
(CVXPY) Aug 23 11:51:51 AM: Your problem has 16 variables, 2 constraints, and 0 parameters.
(CVXPY) Aug 23 11:51:51 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Aug 23 11:51:51 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Aug 23 11:51:51 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Using cached ASA map, for faster compilation (bypassing reduction chain).
(CVXPY) Aug 23 11:51:51 AM: Finished problem compilation (took 7.620e-04 seconds).
-------------------------------------------------------------------------------
                                Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Invoking solver SCS  to obtain a solution.
------------------------------------------------------------------
           SCS v3.2.1 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 51, constraints m: 122
cones:    l: linear vars: 9
      q: soc vars: 77, qsize: 21
      s: psd vars: 36, ssize: 1
settings: eps_abs: 1.0e-05, eps_rel: 1.0e-05, 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): 189, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 1.33e-05  3.69e-07  8.77e-06  2.00e+00  1.00e-01  3.65e-04
------------------------------------------------------------------
status:  solved
timings: total: 3.70e-04s = setup: 2.83e-04s + solve: 8.66e-05s
     lin-sys: 2.67e-06s, cones: 1.97e-05s, accel: 0.00e+00s
------------------------------------------------------------------
objective = 2.000005
------------------------------------------------------------------
-------------------------------------------------------------------------------
                                    Summary
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Problem status: optimal
(CVXPY) Aug 23 11:51:51 AM: Optimal value: 2.000e+00
(CVXPY) Aug 23 11:51:51 AM: Compilation took 7.620e-04 seconds
(CVXPY) Aug 23 11:51:51 AM: Solver (including time spent in interface) took 5.131e-04 seconds
2.0000121014031516
===============================================================================
                                     CVXPY
                                     v1.2.1
===============================================================================
(CVXPY) Aug 23 11:51:51 AM: Your problem has 16 variables, 2 constraints, and 0 parameters.
(CVXPY) Aug 23 11:51:51 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Aug 23 11:51:51 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Aug 23 11:51:51 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Using cached ASA map, for faster compilation (bypassing reduction chain).
(CVXPY) Aug 23 11:51:51 AM: Finished problem compilation (took 6.919e-04 seconds).
-------------------------------------------------------------------------------
                                Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Invoking solver SCS  to obtain a solution.
------------------------------------------------------------------
           SCS v3.2.1 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 51, constraints m: 122
cones:    l: linear vars: 9
      q: soc vars: 77, qsize: 21
      s: psd vars: 36, ssize: 1
settings: eps_abs: 1.0e-05, eps_rel: 1.0e-05, 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): 189, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 1.24e-05  3.64e-07  1.41e-05  2.00e+00  1.00e-01  4.21e-04
------------------------------------------------------------------
status:  solved
timings: total: 4.24e-04s = setup: 3.47e-04s + solve: 7.73e-05s
     lin-sys: 2.25e-06s, cones: 1.38e-05s, accel: 4.20e-08s
------------------------------------------------------------------
objective = 2.000008
------------------------------------------------------------------
-------------------------------------------------------------------------------
                                    Summary
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Problem status: optimal
(CVXPY) Aug 23 11:51:51 AM: Optimal value: 2.000e+00
(CVXPY) Aug 23 11:51:51 AM: Compilation took 6.919e-04 seconds
(CVXPY) Aug 23 11:51:51 AM: Solver (including time spent in interface) took 6.042e-04 seconds
2.0000112673483987
===============================================================================
                                     CVXPY
                                     v1.2.1
===============================================================================
(CVXPY) Aug 23 11:51:51 AM: Your problem has 16 variables, 2 constraints, and 0 parameters.
(CVXPY) Aug 23 11:51:51 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Aug 23 11:51:51 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Aug 23 11:51:51 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Using cached ASA map, for faster compilation (bypassing reduction chain).
(CVXPY) Aug 23 11:51:51 AM: Finished problem compilation (took 6.428e-04 seconds).
-------------------------------------------------------------------------------
                                Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Invoking solver SCS  to obtain a solution.
------------------------------------------------------------------
           SCS v3.2.1 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 51, constraints m: 122
cones:    l: linear vars: 9
      q: soc vars: 77, qsize: 21
      s: psd vars: 36, ssize: 1
settings: eps_abs: 1.0e-05, eps_rel: 1.0e-05, 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): 189, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 1.30e-05  2.96e-07  1.62e-05  2.00e+00  1.00e-01  3.56e-04
------------------------------------------------------------------
status:  solved
timings: total: 3.62e-04s = setup: 2.75e-04s + solve: 8.71e-05s
     lin-sys: 2.75e-06s, cones: 2.05e-05s, accel: 0.00e+00s
------------------------------------------------------------------
objective = 2.000008
------------------------------------------------------------------
-------------------------------------------------------------------------------
                                    Summary
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Problem status: optimal
(CVXPY) Aug 23 11:51:51 AM: Optimal value: 2.000e+00
(CVXPY) Aug 23 11:51:51 AM: Compilation took 6.428e-04 seconds
(CVXPY) Aug 23 11:51:51 AM: Solver (including time spent in interface) took 4.900e-04 seconds
2.0000129752354017
===============================================================================
                                     CVXPY
                                     v1.2.1
===============================================================================
(CVXPY) Aug 23 11:51:51 AM: Your problem has 16 variables, 2 constraints, and 0 parameters.
(CVXPY) Aug 23 11:51:51 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Aug 23 11:51:51 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Aug 23 11:51:51 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Using cached ASA map, for faster compilation (bypassing reduction chain).
(CVXPY) Aug 23 11:51:51 AM: Finished problem compilation (took 5.682e-04 seconds).
-------------------------------------------------------------------------------
                                Numerical solver
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Invoking solver SCS  to obtain a solution.
------------------------------------------------------------------
           SCS v3.2.1 - Splitting Conic Solver
    (c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 51, constraints m: 122
cones:    l: linear vars: 9
      q: soc vars: 77, qsize: 21
      s: psd vars: 36, ssize: 1
settings: eps_abs: 1.0e-05, eps_rel: 1.0e-05, 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): 189, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 1.14e-05  2.70e-07  1.76e-05  2.00e+00  1.00e-01  2.91e-04
------------------------------------------------------------------
status:  solved
timings: total: 2.94e-04s = setup: 2.24e-04s + solve: 6.96e-05s
     lin-sys: 1.50e-06s, cones: 9.08e-06s, accel: 0.00e+00s
------------------------------------------------------------------
objective = 2.000008
------------------------------------------------------------------
-------------------------------------------------------------------------------
                                    Summary
-------------------------------------------------------------------------------
(CVXPY) Aug 23 11:51:51 AM: Problem status: optimal
(CVXPY) Aug 23 11:51:51 AM: Optimal value: 2.000e+00
(CVXPY) Aug 23 11:51:51 AM: Compilation took 5.682e-04 seconds
(CVXPY) Aug 23 11:51:51 AM: Solver (including time spent in interface) took 4.129e-04 seconds
2.0000114385341132
imbacalvin commented 2 years ago

Ok, this makes sense. Thanks for your quick help and explanation!