model PSD as the variable domain or as a constraint

[Sof Dem]

Hi,

I tested 3 formulations with the Python Fusion API and get very different results for this SDP:

min_{x inPSD(n)} <c,x>:  <a,x>=1,  0<=x<=1

1/ define variable x in domain inPSDCone(n) and set 1 constraint  (x, inRange(0.0,1.0))

2/ define variable x in domain inPSDCone(n) and set 2 constraints  (x, greaterThan(0.0)) and (x, lessThan(1.0))

3/ define variable x in domain [n,n] inRange(0.0,1.0) and set 1 constraint  (x, inPSDCone())

For an instance of size n=66, the CPU times are respectively:

1/ 5s, 2/ 33s, 3/ 0.8s

I didn't expect such volatily or is there an explanation ?

In particular, the examples of SDP in the documentation tend to encourage the "bad" formulations 1 or 2 (i.e. declare conic variable).

Thank you very much for your time and answer

Sophie.

[Michal Adamaszek]

In model 3 you additionally have to enforce the constraint that x is symmetric. Otherwise it is not the same model as 1, 2 (see the info in https://docs.mosek.com/latest/pythonfusion/domain.html#domain.inpsdcone )

Regardless, in models 1, 2, 3, you have respectively

n^2,   2n^2,    n^2/2

constraints involving the semidefinite matrix variable (in case 3 it is the semidefinite matrix X>>0 implicitly introduced by the PSD constraint, that is upper_triang(x)==upper_triang(X), X>>0). That number has the main impact on efficiency, see the discussion in 

https://docs.mosek.com/latest/faq/faq.html#why-is-my-sdp-lmi-slow-or-running-out-of-memory

 https://groups.google.com/g/mosek/c/xP_KtAJ3xSQ

Presolve does not do much about SDP terms.

The difference from the documentation is that you have the x\in [0,1] bounds i.e. order of n^2 constraints on x to begin with. If x is free as mostly in our examples then switching to formulation 3 increases the number of constraints on x from O(1) to \Omega(n^2) and then 3 is worst.

Best,

Michal

[Sof Dem]

Thank you so much Michal for your quick and helpful answer. 

I didn't pay attention to the symmetry definition in inPSDcone, and missed examples with side constraints.

So model 1 is the one I need, but I'll give a try to model 3 in my tests after tricking objective and constraints to only apply to upper_triang(x).

Thank you again. Sophie.