Optimizing the running time of solving an SDP with Mosek

[Jayanth Jayakumar]

Dear All,

I'm working on a convex optimization problem formulated as follows (you can find the explanation below):

This problem is cast as a semi-definite programming (SDP), fed to the CVXPY modelling framework, and solved using the Mosek solver. Please find attached the full code containing the definition of a function that computes the solution of the SDP and the input data.

The following is the explanation of the objects in the code:

The optimization variables V and X are matrices of size p x p and num x p respectively, where num = d^2 is typically very large i.e., > 6000 and p=2 (for my case).

The constraint for positive semi-definiteness in terms of X and V is given through the positive semi-definiteness of the block matrix (say M) M=cp.bmat([[V, X.T @ R.conj().T], [R @ X, np.identity(num)]]) >> 0. This is inferred from the positive semi-definiteness condition on the Schur complement of the identity block of M i.e., V - X.T @ R.conj().T @ R @ X. Another constraint reads: X.T @ dersmatrix == np.identity(p).

R and dersmatrix are matrices of size num x num and num x p respectively, which are constructed previously in my code. W is a p x p weight matrix in the objective function cp.trace(W @ V). Note that: p --> n, num --> \tilde{r}, dersmatrix --> partial derivative of s_\theta in the above image.

For example, when d=81, num=6561, resulting in extremely large sizes for X, R, and dersmatrix, which significantly slows down the solution.

As one possible solution to obtain speed-up, I identified that R is quite sparse and tried to exploit its sparsity using R_spr=csr_matrix(R), which modifies the positive semi-definiteness constraint to cp.bmat([[V, X.T @ R_spr.conj().T], [R_spr @ X, np.identity(num)]]) >> 0. However, this still does not seem to yield faster results. 

Having already optimized my code for the construction of the R matrix, I am looking for some suggestions to optimize the SDP part of my code when dealing such very large matrices using Mosek solver, especially for d>=81. In addition to this, it is possible that the block matrix form of the constraint could be slowing down the CVXPY compilation as it is of size (d^2+p) x (d^2+p).

As working examples, I have also attached the input data for NumPy arrays for d=25 and d=81. Any ideas on increasing the performance of Mosek for this problem would be much helpful. Thanks.

Kind regards,

[Michal Adamaszek]

Hi,

It looks like cvxpy is doing a good job processing your model into an efficient formulation for Mosek. It is just a very large model. Even after CVXPY dualized you can't avoid roughly d^2*p constraints involving semidefinite terms (times two because complex), the dimension of the RX block. Internally complexity and memory complexity grows as the square of this number, which for d,p=81,2 puts it in the very large category. So it seems as good as it gets.

The solution is very nice though

14  5.1e-10  3.1e-07  8.7e-15  1.00e+00   2.334369651e-01   2.334369751e-01   7.6e-13  9822.11
Optimizer terminated. Time: 9970.82


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 2.3343696505e-01    nrm: 1e+00    Viol.  con: 2e-10    var: 0e+00    barvar: 0e+00  
  Dual.    obj: 2.3343697506e-01    nrm: 3e+01    Viol.  con: 0e+00    var: 8e-13    barvar: 2e-13

Michal

[Jayanth Jayakumar]

Hi Michal,

Thanks for checking the code. In that case, I will try parallel computation to run the code for d>=81.

Kind regards,

Jayanth.