Quadratic constraint of a matrix is not allowed in cvx?

Nonconvex
1

Dear all,

I am trying to formulate my problem with cvx, pls take a look at my problem as follow:

variable v(n,n): v is a nxn matrix we are looking for
objective function: minimize (sum (|v_i - v_j|^2)) where |v_i - v_j|^2 = sum (v_ik - v_jk)^2 (euclidian distance between vi and vj); i,j,k in the range of [1…n], and (i,j) in a given set call E
constraints:

  • (1) for every i in the range [1…n] |v_i|^2 == 1
  • (2) for every i<j, sum (|v_i - v_j|^2) >= c where c is a positive real value (c = n/2 for example)
  • (3) for every i,j,k (i ~= j ~=k), |v_i - v_j|^2 + |v_j - v_k|^2 >= |v_i - v_k|^2

The problem is said that it is a SDP problem
I formulated the objective function and it is accepted in cvx

And the constraints are formulated like this:
(1) + (2) :
for every i<j, sum(|v_i - v_j|^2) = sum(|v_i|^2) + sum (|v_j|^2) - 2* sum(v_iv_j = 2n^2 - 2* sum(v_iv_j) >= c.
(3) <=> we form a matrix from v_i, v_j, v_k, called r
we form a matrix
B =[ 0 -1 1
-1 2 -1
1 -1 0 ];
so, (3) <=> sum (sum(B r * r’, 2 ), 1) >= 0 (sum up all the matrix entries; r’ : transpose matrix of r; parameter 1 and 2: sum up in column and row respectively)

I saw cvx does not accept the constraint like " t * t’ < 5 where t is a variable matrix"
Can someone help me point the way of reformulating the constraints that are accepted in cvx?
I highly appreciate your time and your help!

2

Your constraints are not convex.

Have you seen the SDP formulation, as a linear (convex) SDP? Perhaps there is an SDP formulation which is a convex relaxation of the original problem?

It appears that you haven’t read the CVX FAQ Why isn’t CVX accepting my model? READ THIS FIRST! .

3

Thanks so much for you reply
Actually I read the CVX FAQ and I understand the definition of SDP problem.
Yes, It is a SDP relaxation

I am sorry that I took you time.
But I am trying to formulate the problem coming from the paper: http://snap.stanford.edu/class/cs224w-readings/arora04expansion.pdf
(page number = 116 from (4) to (7).
It said that the problem is SDP. It is true if we do some transformations we can see that.
I just confuse that if cvx supports the quadratic constraints in the paper?
Again, Thank you so much,

4

You ought to be able to straightforwardly enter the primal or dual in equations 33 through 36 on p. 136 into CVX. Will that suit your needs?

5

Thanks so much for your help,
Actually the thing I want is a set of points in an n-dimension space. The set is the solution of the problem in page 116 from (4) thru (7). It may not be the same as problem you said. But I will try to reduce to your suggestion!
Thuy

6

I very quickly skimmed through the paper. I will let you figure out the relationships between the various problem formulations.

7

You are so helpful!
I am trying your suggestion. Hope that it will work.
Thank you!
Thuy

8

Unfortunately the problem from (33) thru (36) cannot fit with the problem from (4) to (7). This is because if we have the solution for x in the former, we cannot compute the v of the later.
So I should find other tool instead of cvx for my problem.
If you know some tool suits my need, pls tell me.
Thank you so much for your time and your help!
Thuy