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

Nonconvex
1

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

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).

3

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

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! .

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?

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.

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!

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.

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!

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.

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.