How can I solve this SDP problem with CVX?

Nonconvex
1

I wish to solve the following SDP problem:
link to SDP image

We can assume that D = \{0,1\}^n and s = (1,1,... } .
So far I have tried to convert the right side expression in a stright forward way but I got stuck at the vector inner products (at matlab dot(A,B) function) with “not a square” error.

m = 4; n = 4; s =16; cols = n*s;
F0 = [0,1,2,4,5,8,9,10];
F1 = [3,6,7,11,12,13,14,15];
cvx_begin
    variable X(m,cols)
    expression w(n)
    expression z
    for i = 1:s
        w(i) = 0;
        for j=1:n
            w(i) = w(i)+sum_square_abs(X(:,(i-1)*n+j));
        end
    end
    
    minimize( max(w) )
    subject to
    for i0 = 1:8
        for i1 = 1:8
            z=0;
            for j=1:n
                if bitget(F0(i0),j)~=bitget(F1(i1),j)
                   z = z + dot(X(:,F0(i0)*n+j),X(:,F1(i1)*n+j));  
                end;
            end
            z == 1;
        end
    end
cvx_end

Any ideas how to make it work? The motivation behind this problem is that the solution to it is an optimal quantum query algorithm for a given Boolean function.

2

I haven’t tried to look at your problem in detail, but the constraint in question looks non-convex and therefore will not be accepted by CVX (see Why isn’t CVX accepting my model? READ THIS FIRST! ). Do you have reason to believe that your constraints are (could be reformulated as) convex? Has anyone ever stated that this is a convex problem?

As a side note, maybe quantum computers will be better able to deal with non-convex constraints than deterministic computers by being inside and outside the constraints at the same time? :smile:

3

My problem comes from this paper https://cs.uwaterloo.ca/~breic/papers/sdponly.pdf equation 5.2 which is related to equation 4.5 (which can be solved with CVX). I would like to solve 5.2 because it gives vectors I need as a solution.

4

It would take me a lot longer than I am prepared to spend to understand the definitions, conventions, and notation in that paper. Nevertheless, I don’t see any claim by the author that 5.2 is an SDP, or the constraints convex. As to how to solve 5.2, I will leave that to you, but perhaps some nonlinear solver which accepts non-convex formulations?