Sparse Matrix on CVX

(navro) #1

Hello,
Im working my thesis on an energy disaggregation problem via powerlets and i want CVX for a sparse matrix.Now im new in CVX and after reading many forums here i wonder if what i want is even possible.This is my code so far:
cvx_begin

variable Z(a,b)  sparse

for i = 1 : 98 :2      
    minimize((g *norm(Z(i,:),Inf))+ (gg * norm(Z(:,i)-Z(:,i+1))) + (trace(D'*Z)))
    subject to
        Z >= 0
        A'*Z==B
end

cvx_end
Is there is a way to define a sparse matrix via cvx?
Thanks

(Mark L. Stone) #2

You can apply sparse to a CVX variable or expression, but I don’t think it does anything.

help cvx/sparse

Disciplined convex/geometric programming information for sparse:
    For a CVX variable X, sparse(X) just returns X. In the three-
    and five-argument versions sparse(I,J,V,M,N), the index
    arguments I and J and size arguments M and N must be constant.
    If any of the index pairs (I(k),J(k)) are repeated, then the
    corresponding elements V(k) will be added together. Therefore,
    those elements must be compatible with addition; i.e., they
    must have the same curvature.
(navro) #3

I am trying to solve the following problem

7

where j is the j-th column of z,
and this is what i have written so far:

cvx_begin
variable z(100,100)
objective=trace(d’*z);
for i = 1 : 99
objective=objective + sum(norm(z(i,:),Inf),2) + sum(norm(z(:,i)-z(:,i+1)))
end
minimize (objective)
subject to
z >= 0
ones(1,100)*z==ones(1,100)
cvx_end

Am i even close to the right way of coding the problem?Sorry again,i am just new to this and i do not know if the results i get are right ones or cause i want z to be sparse and it is not.

(Mark L. Stone) #4

I think the mixed infinity, one norm in the first term of the objective function should be
sum(norms(z,inf,1)) . No for loop is required for this norm.
Your code for this term would be correct (but not as nice as mine) if the for loop were from 1 to 100 (you got tripped up due to your second term), or if you added the i = 100 term outside the for loop.

I believe the second term is correct, but can be handled more elegantly as sum(norms(diff(z')'))
Edit: See my next post. diff can not be applied to CVX variables or expressions, so the code in the previous sentence will work only for numerical z, not for z being a CVX variable or expression.

You have not included gamma and gamma_prime in your code. Including those, you can use
minimize(gamma*sum(norms(z,inf,1)) + gamma_prime*sum(norms(diff(z')')) + trace(D'*z))

I will let you check to make sure I didn’t make a mistake. Applying the code to numerical matrices is a good way to check that the calculations are what you want.

The last constraint can be written more simply as sum(z) == 1, although your version is correct.

So it looks to me that your code is correct, but for the missing i = 100 term in the first objective term, and neglecting gamma and gamma_prime. I guess the first term in the objective, and perhaps to some extent the second term, are supposed to attempt to induce sparseness in z. However, the weights assigned to these terms via gamma and gamma_prime can have a large impact on the extent to which sparseness is induced. Optimal selection of their values is outside the scope of this form, but it is not atypical for some kind of cross-validation to be used to choose optimal values.

There is no magical “sparse matrix” designation you can use in CVX to accomplish this. Sparseness will have to be induced by your problem formulation. The mixed norm(s) in the formulation in the image are presumably trying to induce sparseness. If you really want to control sparseness, you can do it using the zero “norm” (counting number of non-zeros), but that would be non-convex, and would require use of the MIDCP capability of CVX (making use of variables declared as binary), and would be much more computationally intensive than the formulation in the image, which may not achieve the real goal quite as well, but is convex, and easy and fast to compute compared to the non-convex zero “norm” formulation.

(navro) #5

I got the following error for diff: Undefined function ‘diff’ for input arguments of type ‘cvx’.

(Mark L. Stone) #6

Whoops, you’re correct. diff only works on numerical matrices. The lack of support for diff in CVX has long been noted on this forum, and would be a relatively easy added capability in CVX. But that capability has not been added, and given the very low level of CVX development effort in recent years, there is no reason to believe it will be added soon.

So stick with your code for the 2nd term in the objective function. However, note that your use of sum in that calculation doesn’t do anything, and can be eliminated, because you are only summing over one term.

(navro) #7

Thanks a lot for your response Mark.It helped me a lot.