Small Numerical Discrepancy in CVX SDP Solution

ageha · September 10, 2024, 7:28pm

I am solving an SDP problem using CVX in MATLAB, and I encountered a small numerical discrepancy in the result. Specifically, the solution provided by CVX is 0.160006294144051, while the theoretical value should be 0.16000000000000.

I set cvx_precision to high, but the result remains unchanged. I also saw in other threads that large differences in the coefficients of parameters could cause this issue, but in my case, the coefficient differences are at most around 10^4, which doesn’t seem too extreme.

I would like to understand why this discrepancy occurs and whether there are any methods to reduce it or achieve a more accurate result. I suspect it might be related to numerical precision or solver tolerances, but I would appreciate any insights or suggestions on how to address this issue.

Thank you in advance for your help!

Below is the log from the CVX run for more details:

Calling Mosek 9.1.9: 707 variables, 146 equality constraints
------------------------------------------------------------

MOSEK Version 10.2.3 (Build date: 2024-8-12 11:17:21)
Copyright (c) MOSEK ApS, Denmark WWW: mosek.com
Platform: MACOSX/64-X86

MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #18 (nearly) zero elements are specified in sparse col '' (15) of matrix 'A'.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #18 (nearly) zero elements are specified in sparse col '' (21) of matrix 'A'.
Problem
  Name                   :                 
  Objective sense        : minimize        
  Type                   : CONIC (conic optimization problem)
  Constraints            : 146             
  Affine conic cons.     : 0               
  Disjunctive cons.      : 0               
  Cones                  : 8               
  Scalar variables       : 27              
  Matrix variables       : 22 (scalarized: 680)
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - primal attempts        : 1                 successes              : 1               
Lin. dep.  - dual attempts          : 0                 successes              : 0               
Lin. dep.  - primal deps.           : 0                 dual deps.             : 0               
Presolve terminated. Time: 0.00    
Optimizer  - threads                : 56              
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 146             
Optimizer  - Cones                  : 7               
Optimizer  - Scalar variables       : 24                conic                  : 20              
Optimizer  - Semi-definite variables: 22                scalarized             : 680             
Factor     - setup time             : 0.00            
Factor     - dense det. time        : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 8228              after factor           : 8236            
Factor     - dense dim.             : 0                 flops                  : 8.41e+05        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   1.4e+01  1.0e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.00  
1   5.3e+00  3.8e-01  2.8e-01  1.04e+00   -8.642941885e-01  -7.562546407e-01  3.8e-01  0.01  
2   1.3e+00  9.7e-02  3.7e-02  6.42e-01   -1.323864542e+00  -1.295695865e+00  9.7e-02  0.01  
3   6.4e-01  4.6e-02  6.5e-03  2.31e+00   -6.722591205e-01  -6.820932417e-01  4.6e-02  0.01  
4   2.4e-01  1.7e-02  1.0e-03  2.04e+00   -3.618708413e-01  -3.653232575e-01  1.7e-02  0.02  
5   1.3e-01  9.2e-03  3.6e-04  1.73e+00   -2.670499885e-01  -2.684586274e-01  9.2e-03  0.02  
6   7.7e-02  5.6e-03  1.8e-04  1.20e+00   -2.397593407e-01  -2.405651806e-01  5.6e-03  0.03  
7   5.4e-02  3.9e-03  1.1e-04  9.31e-01   -2.280449787e-01  -2.286071755e-01  3.9e-03  0.03  
8   2.7e-02  1.9e-03  3.9e-05  1.01e+00   -2.084128795e-01  -2.087208689e-01  1.9e-03  0.03  
9   1.7e-02  1.2e-03  2.6e-05  4.67e-01   -2.032193218e-01  -2.034107212e-01  1.2e-03  0.04  
10  7.2e-03  5.2e-04  7.1e-06  8.02e-01   -1.906731746e-01  -1.907659311e-01  5.2e-04  0.04  
11  3.3e-03  2.4e-04  3.1e-06  4.20e-01   -1.851429754e-01  -1.851578091e-01  2.4e-04  0.04  
12  1.8e-03  1.3e-04  1.2e-06  4.25e-01   -1.797035874e-01  -1.797264605e-01  1.3e-04  0.05  
13  6.9e-04  5.0e-05  5.1e-07  9.19e-02   -1.760036684e-01  -1.759743045e-01  5.0e-05  0.05  
14  1.8e-04  1.3e-05  7.3e-08  6.31e-01   -1.695938591e-01  -1.695846216e-01  1.3e-05  0.06  
15  6.2e-05  4.5e-06  2.5e-08  2.48e-01   -1.670486118e-01  -1.670305447e-01  4.5e-06  0.06  
16  2.2e-05  1.6e-06  6.4e-09  6.14e-01   -1.648845831e-01  -1.648738783e-01  1.6e-06  0.06  
17  1.1e-05  8.1e-07  3.4e-09  2.21e-01   -1.640083066e-01  -1.639946386e-01  8.1e-07  0.07  
18  4.2e-06  3.0e-07  9.0e-10  6.90e-01   -1.627940954e-01  -1.627870895e-01  3.0e-07  0.07  
19  2.0e-06  1.5e-07  4.7e-10  2.43e-01   -1.622510819e-01  -1.622425008e-01  1.5e-07  0.07  
20  6.4e-07  4.6e-08  9.7e-11  6.92e-01   -1.614929599e-01  -1.614890555e-01  4.6e-08  0.08  
21  2.6e-07  1.9e-08  4.3e-11  2.61e-01   -1.611586902e-01  -1.611540638e-01  1.9e-08  0.08  
22  8.2e-08  6.0e-09  8.9e-12  6.68e-01   -1.607592659e-01  -1.607571658e-01  6.0e-09  0.09  
23  3.3e-08  2.4e-09  3.8e-12  2.77e-01   -1.605856906e-01  -1.605833065e-01  2.5e-09  0.09  
24  1.0e-08  7.5e-10  8.0e-13  6.60e-01   -1.603858338e-01  -1.603847373e-01  7.6e-10  0.09  
25  4.5e-09  3.4e-10  3.7e-13  2.61e-01   -1.602997897e-01  -1.602985509e-01  3.3e-10  0.10  
26  1.3e-09  1.3e-10  7.3e-14  6.58e-01   -1.601957319e-01  -1.601951753e-01  1.0e-10  0.11  
27  5.5e-10  3.4e-10  3.3e-14  2.32e-01   -1.601531027e-01  -1.601524484e-01  4.2e-11  0.12  
28  1.6e-10  8.4e-10  6.2e-15  6.72e-01   -1.600975064e-01  -1.600972295e-01  1.2e-11  0.13  
29  5.9e-11  5.0e-10  2.4e-15  3.08e-01   -1.600725799e-01  -1.600722875e-01  4.5e-12  0.13  
30  1.9e-11  8.4e-10  5.2e-16  6.50e-01   -1.600485152e-01  -1.600483751e-01  1.4e-12  0.14  
31  8.2e-12  3.9e-09  2.4e-16  2.62e-01   -1.600381831e-01  -1.600380193e-01  6.2e-13  0.15  
32  2.4e-12  3.7e-09  4.7e-17  6.79e-01   -1.600244335e-01  -1.600243637e-01  1.8e-13  0.15  
33  2.5e-12  4.0e-09  1.9e-17  3.08e-01   -1.600184117e-01  -1.600183371e-01  7.0e-14  0.16  
34  6.1e-13  2.3e-08  4.3e-18  6.53e-01   -1.600124348e-01  -1.600123983e-01  2.3e-14  0.17  
35  5.1e-13  2.5e-08  1.7e-18  3.15e-01   -1.600093680e-01  -1.600093300e-01  9.1e-15  0.18  
36  2.3e-12  6.2e-08  4.7e-19  6.47e-01   -1.600065457e-01  -1.600065258e-01  3.4e-15  0.20  
37  7.3e-12  6.1e-08  4.7e-19  1.00e+00   -1.600065365e-01  -1.600065166e-01  3.4e-15  0.21  
38  1.1e-11  6.1e-08  4.7e-19  3.94e-01   -1.600065323e-01  -1.600065124e-01  3.4e-15  0.22  
39  9.8e-12  6.2e-08  4.2e-19  3.88e-01   -1.600063539e-01  -1.600063342e-01  3.0e-15  0.23  
40  9.8e-12  6.2e-08  4.1e-19  3.57e-01   -1.600063262e-01  -1.600063064e-01  3.0e-15  0.24  
41  9.8e-12  6.2e-08  4.1e-19  3.49e-01   -1.600063231e-01  -1.600063033e-01  3.0e-15  0.26  
42  9.9e-12  6.2e-08  4.1e-19  3.47e-01   -1.600063217e-01  -1.600063020e-01  3.0e-15  0.27  
43  9.9e-12  6.2e-08  4.1e-19  3.53e-01   -1.600063186e-01  -1.600062989e-01  3.0e-15  0.28  
44  1.1e-11  6.2e-08  4.1e-19  1.00e+00   -1.600063162e-01  -1.600062965e-01  2.9e-15  0.29  
45  1.1e-11  6.1e-08  4.1e-19  3.40e-01   -1.600063112e-01  -1.600062915e-01  2.9e-15  0.30  
46  1.1e-11  6.2e-08  4.1e-19  3.53e-01   -1.600063068e-01  -1.600062871e-01  2.9e-15  0.32  
47  1.1e-11  6.2e-08  4.1e-19  3.41e-01   -1.600063067e-01  -1.600062870e-01  2.9e-15  0.33  
48  1.1e-11  6.1e-08  4.1e-19  3.49e-01   -1.600062980e-01  -1.600062784e-01  2.9e-15  0.35  
49  1.1e-11  6.1e-08  4.0e-19  3.51e-01   -1.600062945e-01  -1.600062749e-01  2.9e-15  0.36  
50  1.1e-11  6.1e-08  4.0e-19  3.58e-01   -1.600062942e-01  -1.600062746e-01  2.9e-15  0.38  
51  1.1e-11  6.1e-08  4.0e-19  3.47e-01   -1.600062941e-01  -1.600062746e-01  2.9e-15  0.39  
52  1.1e-11  6.1e-08  4.0e-19  3.47e-01   -1.600062941e-01  -1.600062746e-01  2.9e-15  0.41  
53  1.1e-11  6.1e-08  4.0e-19  3.47e-01   -1.600062941e-01  -1.600062746e-01  2.9e-15  0.42  
Optimizer terminated. Time: 0.44    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -1.6000629414e-01   nrm: 1e+00    Viol.  con: 3e-08    var: 8e-12    barvar: 0e+00    cones: 7e-12  
  Dual.    obj: -1.6000627457e-01   nrm: 5e+04    Viol.  con: 0e+00    var: 2e-08    barvar: 4e-11    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.44    
    Interior-point          - iterations : 54        time: 0.43    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.160006

Mark_L_Stone · September 10, 2024, 7:46pm

Never use cvx_precision high Stock with the default. It was a well-intentioned capability, now known to be ill-advised.

The solution accuracy doesn’t seem too bad. But did you notice Mosek’s warning about (two) near zero elements in the input data? That might degrade accuracy. I recommend you look at all your input data. Perhaps you have some “junk” terms which really should be exactly zero, but are instead small numbers due to the way they were generated - if so, eliminate those terms altogether. Or maybe you need to improve scaling by better choice of units.

ageha · September 11, 2024, 11:17am

Thank you for your response and suggestions.

I did notice the Mosek warning about near-zero elements in the input data, and upon further inspection, I found that there were indeed some “junk” terms that should have been exactly zero. I eliminated those terms and recalculated the solution. This led to a slight improvement, the discrepancy remains relatively small, but it hasn’t changed significantly.

You mentioned the need to “improve scaling by better choice of units.” Could you clarify what exactly this means in practice? Or, any relevant references or literature on this topic would be greatly appreciated. I have already confirmed that the differences in the coefficients of the parameters in my constraints are at most around 10^-4 after junks eliminated.

Mark_L_Stone · September 11, 2024, 11:23am

Perhaps your scaling is o.k. Maybe getting rid of junk terms is all you can do.

As for scaling, you can look at 8.2 Addressing numerical issues — MOSEK Optimizer API for C 10.2.4 , as well as search on this forum.

ageha · September 11, 2024, 12:49pm

I see. Thank you for your support!

Erling · September 12, 2024, 5:06am

All computations are done using 64bit finite precision floating point numbers so you cannot expect to get an exact solution.

To me it seems the accuracy of the solution you obtain from Mosek is pretty good and most likely as good as you can get using off the shelf software.