DCP error: Only scalar quadratic forms can be specified in CVX

(Baban) #1

I’m trying to ‘maximize’ trace(AX) subject to 0<=A<=I (Identity) and trace(A) = k.

I formulate this as:

minimize -trace(A*X)
subject to
    trace(A) = k;
    A >= 0;
    A <= eye(2*p);

but this throws up the captioned error.

(Mark L. Stone) #2

You’re not showing us a complete reproducible problem. If X is a numeric matrix, not a CVX variable or expression, you should not get this error message. From your problem description, it seems that X should be a numeric matrix, i.e., input data to your optimization problem.

Given the error message you received, t would appear that X must be a CVX variable or expression, which is not allowed (A*X ). If that is true, is that just a programming “typo”, or do you really intend X to be a CVX variable or expression, in which case what are you doing with it outside the objective function?

(Mark L. Stone) #4

This does not follow the DCP rules, and is non-convex. Why isn't CVX accepting my model? READ THIS FIRST!

However, the problem is clearly unbounded because there are no constraints on X. So I have “solved” it for you without using CVX. Are you sure you want X to be a CVX variable, and not a numeric input matrix?

(Baban) #5

I see what you’re saying. I’ll ponder over this. Thanks.

(Baban) #6

@Mark_L_Stone: I’m really missing some point here, it seems. I understand from this (https://math.stackexchange.com/questions/1044092/sum-of-k-largest-eigenvalues-of-a-symmetric-matrix-as-an-sdp) that the dual problem is always convex. In my primal problem, I’d some constraint on X and in the dual problem, there are constraints on the dual variable A but ultimately, I’m trying to solve for X (minimize the sum of its k singular values). So, both A & X are variables in the dual problem. But CVX cannot solve this, you’re saying?

I’ve been stuck on this for days and really appreciate a reply/discussion.

(Mark L. Stone) #7

You deleted your post which I wrote did not follow the DCP rules. I don’t remember exactly what that code was. Nevertheless, as I suspected from the beginning, and as is clear from the stack exchange link, X is supposed to be input data (matrix), not an optimization variable.

I will defer to mcg or someone else to resolve this for you.

(Baban) #8

@Mark_L_Stone: I think I was still trying to formulate my question properly, so I deleted it. Sorry about that. Here’s my code again:

k =2; p = 4;
p_init = randi([60, 100]);     
A_m = rand(p, p) > 0.3;           
A = 10.*(rand(p, p) - 0.5).*A_m;   
b_init = randi(p^2, p_init, 1);
b = unique(b_init); p_cons = size(b, 1);
a = setdiff(1:p^2, b);            
c = 10.*(rand(p_cons, 2) - 0.5);    
L = min(c.').';                   
U = max(c.').';                 

(The above are some preliminaries for setting up constraints that follow)

cvx_begin SDP
variable E(p, p) symmetric;
variable t 
variable Z(p,p) symmetric
Z == semidefinite(p);
minimize k*t+trace(Z);
t*eye(p)+Z-E >= 0;
E(a) == A(a);
E(b) >= L;     
E(b) <= U;

I’m trying to form the dual of the above problem and verify that strong duality holds.