Optimizing CVXPY SDP Performance for Large Sparse Matrices

Below are some strategies you can try to speed up the SDP, especially when d (and thus num) is large:

---

1. Reformulate the Constraint via the Schur Complement

Since the block matrix

  M = [ V  Xᵀ·R* ]
    [ R·X I ]

is PSD if and only if I ≻ 0 and

  V – Xᵀ·R*·R·X ⪰ 0,

you may try to remove the block structure and impose the Schur complement directly. In CVXPY, this means replacing

PYTHONCopied
constraints = [cp.bmat([[V, X.T @ R.conj().T],
                          [R @ X, np.identity(num)]]) >> 0]

with

PYTHONCopied
constraints = [V - X.T @ R.conj().T @ R @ X >> 0]

This reformulation often leads to fewer “matrix variables” in your constraints and may allow MOSEK to detect and exploit structure better.

---

2. Properly Exploit Sparsity

Even though you already attempted converting R to a sparse matrix form (using scipy’s csr_matrix), you can further ensure that CVXPY sees the sparsity by:

• Wrapping R (and similarly dersmatrix) as a CVXPY constant with sparse flag:

  PYTHONCopied
  R_const = cp.Constant(R_spr)  # R_spr is already a csr_matrix
  dersmatrix_const = cp.Constant(dersmatrix)  # if dersmatrix is sparse too

• Then using these constants in the constraints. For example:

  PYTHONCopied
  constraints = [V - X.T @ R_const.conj().T @ R_const @ X >> 0]
  constraints += [X.T @ dersmatrix_const == np.identity(p)]

This can help CVXPY/MOSEK to maintain the inherent sparsity of the data rather than converting them to dense matrices.

---

3. Consider a Direct MOSEK Interface

If CVXPY’s abstraction is adding overhead, consider writing the problem in MOSEK’s native Python API. MOSEK often provides more control over the structure and sparsity of the data when you construct the optimization problem directly. This can be particularly important when the problem size is huge.

---

4. Problem Scaling and Preprocessing

When d is large, it helps to:

• Pre-scale variables and constraints to avoid numerical issues.
• Check that the sparse constants are indeed in an efficient format (e.g., CSC may sometimes work better than CSR in MOSEK).

---

5. Warm-Starting and Tuning Solver Parameters

MOSEK offers numerous parameters that can be tuned. For instance:

• Allow multiple threads if available.
• Use warm starts if you are solving a sequence of similar problems.
• Experiment with MOSEK’s settings related to interior-point methods or exploit structure by setting parameters that emphasize sparsity.

An example of setting solver options in CVXPY might be:

PYTHONCopied
prob.solve(solver=cp.MOSEK, mosek_params={'MSK_IPAR_INTPNT_MAX_ITERATIONS': 100, 
                                             'MSK_DPAR_INTPNT_CO_TOL_REL_GAP': 1e-6},
           verbose=True)

You will need to consult the MOSEK documentation for the exact parameter names and their recommended usage.

---

Summary

• Replace the block matrix PSD constraint with an equivalent Schur complement form.
• Use CVXPY constants with the sparsity flag for R and dersmatrix.
• Consider a formulation that minimizes the transformation overhead (for example, by using MOSEK’s direct API).
• Scale the problem and tune the solver parameters.

By making these changes, you are more likely to expose and exploit the underlying structure of your problem, which should help with performance when d >= 81.

Happy coding!