I have a sparse matrix operation as part of the optimization constraint. I can implement the program in Matlab cvx, now I am trying to implement a cvxpy version. The problem is following constraint:
N - M << 0
M is a sparse matrix, with only a few entries are declared variables. I don’t know a decent way to construct this constraint.
For example,
N = cp.Variable((800, 800), PSD=True)
a = cp.Variable((10, 1), nonneg=True)
M is a 800* 800 matrix, with M[i, i]= a[i] for 0<=i<10, and the rest of M are all 0’s.
What I have done now is to declare M as M = cp.Variable((800,800), symmetric=True), and then add constraint like
constraints.append(M[i,i]==a[i]) for 0<=i<10; and constraints.append(M[i,j]==0) for the rest of M. But this way, it take lots of time and also the constraint list is large. I am wondering what is the best way to do so.
I also tried to do things like N[i,i] -= a[i] for 0<=i<10, but the item assignment is not allowed.
Advertisement
Answer
You can use this function to create a variable with a given sparsity pattern:
from typing import List, Tuple
import cvxpy as cp
import scipy.sparse as sp
import numpy as np
def sparse_variable(shape: Tuple[int, int], sparsity: List[Tuple[int, int]]):
"""Create a variable with given sparsity pattern."""
nnz = len(sparsity)
flat_var = cp.Variable(nnz)
# Column major order.
V = np.ones(nnz)
I = []
J = []
# Column-major order.
for idx, (row, col) in enumerate(sparsity):
I.append(row + col * shape[0])
J.append(idx)
reshape_mat = sp.coo_matrix((V, (I, J)), shape=(np.prod(shape), nnz))
return cp.reshape(reshape_mat @ flat_var, shape)