Exploring chordal sparsity in YALMIP

[Abdulrahman Aldeek]

Dear Dr.Johan

I hope that you are doing well.

I have a question regarding exploring chordal sparsity for SDP problems. What are my options to do that through YALMIP? I know about SparseCoLO, however, I have been trying to install it by compiling its files through Matlab but I wasn't successful. I'm not sure but it won't compile and I always ended up receiving "mexfunction" errors that I don't know to overcome. These errors are something like this

>> mex -setup
MEX configured to use 'Microsoft Visual C++ 2019 (C)' for C language compilation.

To choose a different C compiler, select one from the following:
MinGW64 Compiler (C)  mex -setup:'C:\Program Files\MATLAB\R2020a\bin\win64\mexopts\mingw64.xml' C
Microsoft Visual C++ 2019 (C)  mex -setup:C:\Users\Abd-PC\AppData\Roaming\MathWorks\MATLAB\R2020a\mex_C_win64.xml C

To choose a different language, select one from the following:
 mex -setup C++
 mex -setup FORTRAN
>> compileSparseCoLO
Compiling Libraries...Building with 'Microsoft Visual C++ 2019'.
MEX completed successfully.
done
Compiling mexForestConvert.cpp...Building with 'Microsoft Visual C++ 2019 (C)'.
Error using mex
LINK : error LNK2001: unresolved external symbol mexFunction
ccputime.lib : fatal error LNK1120: 1 unresolved externals



Error in compileSparseCoLO (line 95)
    eval(command);

I also know and CDCS, however, I always gets NaN answers using it. Do i have any other options?

Regards

[Johan Löfberg]

"I get NaN" is a vague description as you haven't said what really happens. Works here

>> X = sdpvar(2);optimize([X >= eye(2)],trace(X),sdpsettings('solver','cdcs'))

================================================================

CDCS by G. Fantuzzi, Y. Zheng -- v1.0

================================================================

Initializing CDCS...done in 0.0548 seconds.      

Standard form          : primal

Chordalization method  : 1

Adaptive penalty       : 1

Scale data             : 1

Free variables         : 0                

Non-negative variables : 0                

Second-order cones     : 0 (max. size: )

Semidefinite cones     : 1 (max. size: 2)

Affine constraints     : 3                

Consensus constraints  : 3                

================================================================

 iter |   pres   |   dres   |    cost    |   rho    | time (s) |

----------------------------------------------------------------

    1 | 5.40e-01 | 1.85e+00 | -2.00e+00  | 1.00e+00 | 3.30e-02 |

    3 | 1.84e-16 | 4.71e-16 | -2.00e+00  | 1.00e+00 | 4.70e-02 |

================================================================

 SOLUTION SUMMARY:

------------------

 Termination code     :           0

 Number of iterations :           3

 Cost                 : -2.0000e+00

 Primal residual      :  1.8395e-16

 Dual residual        :  4.7103e-16

 Setup time   (s)     :  5.4756e-02

 ADMM  time   (s)     :  4.7962e-02

 Cleanup time (s)     :  2.8312e-02

 Total time   (s)     :  1.3642e-01

================================================================

  struct with fields:

    yalmipversion: '20210331'

    matlabversion: '9.9.0.1524771 (R2020b) Update 2'

       yalmiptime: 0.2244

       solvertime: 0.1386

             info: 'Successfully solved (CDCS)'

          problem: 0

Beyond sparsecolo I am not aware of anything readily available.

However, to me it smells like you are throwing darts randomly, first with dualize without really understanding when/why it is used, and now you are trying to find this new exotic branch of solvers. What is failing with a vanilla SDP solver (mosek) and what makes you think these approaches would help

[Abdulrahman Aldeek]

I'm trying to use SDP for solving optimal power flow for large scale systems. Hence, I'm interested in chordal sparsity. I just tried CDCS for a very small system that is easily solved by Mosek and Sedumi to optimality. I got the following error (and the returned value for the objective function IS FAR from the right solution):

Maximum iterations or time limit exceeded (CDCS)

The log that I got is

===========================================================================

CDCS by G. Fantuzzi, Y. Zheng -- v1.0

===========================================================================
Initializing CDCS...done in 0.2103 seconds.      
Algorithm              : homogeneous self-dual embedding
Scale data             : 1
Free variables         : 30                
Non-negative variables : 42                
Second-order cones     : 9 (max. size: 6)
Semidefinite cones     : 6 (max. size: 5)
Affine constraints     : 42                
Consensus constraints  : 146                
===========================================================================
 iter |   pres   |   dres   |   pcost   |   dcost   |   gap    | time (s) |
---------------------------------------------------------------------------
    1 | 1.38e+00 | 1.01e+02 |  1.17e+04 |  1.16e+04 | 5.49e-03 | 7.65e-02 |
   50 |      NaN |      NaN |       NaN |       NaN |      NaN | 1.42e-01 |
  100 | 1.21e+00 | 5.04e+01 |  2.26e+06 |  2.26e+06 | 1.19e-03 | 2.12e-01 |
  150 | 7.18e-01 | 8.85e+01 |  2.96e+06 |  2.96e+06 | 6.45e-04 | 2.84e-01 |
  200 | 7.29e-01 | 1.30e+02 |  2.75e+06 |  2.75e+06 | 8.57e-06 | 3.55e-01 |
  250 | 2.77e-01 | 1.51e+02 |  2.16e+06 |  2.16e+06 | 4.93e-04 | 4.13e-01 |
  300 | 7.21e-01 | 3.48e+02 |  4.42e+06 |  4.42e+06 | 1.58e-05 | 4.93e-01 |
  350 |      NaN |      NaN |       NaN |       NaN |      NaN | 5.61e-01 |
  400 |      NaN |      NaN |       NaN |       NaN |      NaN | 6.12e-01 |
  450 |      NaN |      NaN |       NaN |       NaN |      NaN | 6.72e-01 |
  500 |      NaN |      NaN |       NaN |       NaN |      NaN | 7.25e-01 |
  550 | 5.13e-01 | 9.77e+01 |  2.25e+06 |  2.24e+06 | 9.48e-04 | 7.92e-01 |
  600 | 1.91e-01 | 2.70e+01 |  6.61e+05 |  6.59e+05 | 9.66e-04 | 8.40e-01 |
  650 | 2.53e-01 | 9.34e+00 |  2.93e+05 |  2.93e+05 | 4.04e-05 | 9.00e-01 |
  700 | 1.63e-01 | 1.59e+01 |  7.52e+04 |  7.60e+04 | 5.44e-03 | 9.65e-01 |
  750 | 9.47e-02 | 2.09e+01 |  4.78e+04 |  4.81e+04 | 2.55e-03 | 1.01e+00 |
  800 | 5.50e-02 | 2.79e+01 |  6.64e+04 |  6.74e+04 | 7.26e-03 | 1.07e+00 |
  850 | 1.95e-01 | 3.28e+01 |  8.66e+04 |  8.75e+04 | 5.31e-03 | 1.12e+00 |
  900 | 4.27e-01 | 2.99e+01 |  1.09e+05 |  1.10e+05 | 2.75e-03 | 1.20e+00 |
  950 | 5.66e-01 | 1.08e+01 |  1.12e+05 |  1.11e+05 | 1.04e-03 | 1.25e+00 |
 1000 | 5.07e-01 | 1.32e+01 |  9.73e+04 |  9.66e+04 | 3.67e-03 | 1.32e+00 |
Warning: CDCS reached the maximum number of iterations, and will not attempt
to complete the positive semidefinite variable. Your output will most
likely contain NaNs!
> In cdcs_hsde.setOutputs (line 58)
  In cdcs_utils.setOutputs (line 14)
  In cdcs (line 194)
  In callcdcs (line 49)
  In solvesdp (line 371)
  In optimize (line 31)
  In YALMIP_LWSDP_OPF (line 220)
===========================================================================
 SOLUTION SUMMARY:
------------------
 Termination code     :           3
 Number of iterations :        1000
 Cost                 :  9.7314e+04
 Primal residual      :  5.0736e-01
 Dual residual        :  1.3213e+01
 Setup time   (s)     :  2.1028e-01
 ADMM  time   (s)     :  1.3193e+00
 Avg. conic proj (s)  :  7.8837e-04
 Avg. affine proj (s) :  2.8846e-04
 Cleanup time (s)     :  1.8965e-02
 Total time   (s)     :  1.5582e+00
===========================================================================
  -9.6602e+04

[Johan Löfberg]

your best bet is to contact the developers to see what an be done with settings (or simply experiment), and hear if your intended model is relevant for cdcs

[Abdulrahman Aldeek]

I read this on their website, could it be related to this issue?

The termination codes have changed. This means that if you use CDCS from YALMIP, the termination code returned by YALMIP will be incorrect. This should be fixed in the next YALMIP release!

[Johan Löfberg]

reading the log it is rather obvious that it has given up