# Quadratic constraint of a matrix is not allowed in cvx?

(Thuy Do) #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?

(Mark L. Stone) #2

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

(Thuy Do) #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,

(Mark L. Stone) #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?

(Thuy Do) #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

(Mark L. Stone) #6

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

(Thuy Do) #7