How to add the constraints $trace(power(z,2))==1$ in cvx sdp problem, where z is a matrix?


(Zhiyong Zhou) #1

the constraints Trace(power(z,2))==1


(Mark L. Stone) #2

This is non-convex. Consider the scalar case. Your constraint is z^2 == 1 , which is non-convex (has solutions z = -1 and 1).


(Zhiyong Zhou) #3

Dear, here z is a matrix. power(z,2)=z.^2.


(Mark L. Stone) #4

I gave you an example for a 1 by 1 matrix, using “matrix” power. Things only get worse when the dimension is greater than 1. Please read Why isn’t CVX accepting my model? READ THIS FIRST! .


(Zhiyong Zhou) #5

Thank you so much for your kind information. In fact, I just want constrain norm(z,q)==1 for some q>1, but I don’t know how to add it to the CVX sdp problem by lift Z=z*z’. In the case q=2, we have norm(z,2)^2==Trace(Z)==1, so the constraint Trace(Z)==1 works. But what if q\neq 2? Do you have any idea about that, sir?


(Mark L. Stone) #6

help cvx/norm

Disciplined convex programming information:
    norm is convex, except when P<1, so an error will result if
    these non-convex "norms" are used within CVX expressions. norm 
    is nonmonotonic, so its input must be affine.

norm (with P >= 1) of an affine function is convex, and therefore can be used in a constraint
norm( ) <= affine expression
where affine expression can be a constant. Equality constraints on norms are non-convex (except for trivial cases, such as right-hand side = 0) and are not allowed in CVX.

I don’t know what exactly you’re doing with trace(Z) == 1 , but if trace(Z) is not an affine function of the CVX (optimization) variables, it is non-convex and will be rejected by CVX.


(Zhiyong Zhou) #7

Dear Mark,

I know the rule of CVX. Since “norm(z,q)==1” is not allowed in CVX. I just want to turn it to a equivalent constraint so that it can be allowed in CVX. In the case of q=2, it is equivalent to Trace(Z)==1 with Z=z*z' which is allowed in CVX. But if q\neq 2, then it is equivalent to Trace(Z.^(q/2))==1 which is not allowed in CVX. So I am thinking whether there is some equivalent expression of norm(z,q)==1 by using Z so that it can be allowed in CVX. Generally, I don’t know whether it does exist…

Thanks!


(Mark L. Stone) #8

You are trying to perform convex alchemy. Even your trace(Z) == 1 will be rejected by CVX. If you really need this constraint, or something equivalent to it, you will have to use a different tool, such as a general nonlinear non-convex optimizer.


(Zhiyong Zhou) #9

Dear Mark,

What do you mean by nonlinear non-convex optimizer? In fact, my optimization problem is \min \lVert Az\rVert_2 s.t. \lVert z\rVert_1\leq s^{(q-1)/q} and \lVert z\rVert_q=1. Do you have any idea about how to solve it? This is a problem i meet in my research. One solution is using “fmincon” function in matlab. But I want also use CVX sdp problem by lifting Z=z*z', that is what I have mentioned it. Thanks!


(Mark L. Stone) #10

That is a non-convex problem, and can’t be solved by CVX. FMINCON is a nonlinear non-convex optimizer.

If you want to do something in CVX, you can relax the norm(z,q) == 1 constraint to an inequality constraint norm(z,q) <= 1. If the solution to the relaxed problem has norm(z,q) = 1, or it is close enough for your purposes, then you have solved the original problem. Otherwise, you haven’t.


(Michael C. Grant) #11

You need to stop trying to use CVX in this manner. This is not how convexity works. You cannot expect to find an “equivalent convex form” for your non-convex problem. The methods that utilize the Z=zz^T involve relaxations—they are not equivalent problems, and cannot guarantee to get a solution.

Attempting to use CVX without a proper understanding of convexity is truly a recipe for frustration.