How to write diag(x*x') in cvx?

1

Hello everyone,

I want to know how to write a constraint that diag(x*x’), which means x in {-1;1}^n. Thank you so much!
Here is my code:

A=[1 0 2; 0 -1 0; 2 0 3];
b=[1; 0; 1];
n=3;
cvx_begin sdp
variable x(n);
variable X(n,n) symmetric;
maximize (trace(X’*A)+b’x )
subject to
diag(X)==1;
diag(xx’)==1;
[1 x’; x X] == semidefinite(n+1);
cvx_end

Warning: A non-empty cvx problem already exists in this scope.
It is being overwritten.

In cvxprob (line 28)
In cvx_begin (line 41)
Error using * (line 126)
Disciplined convex programming error:
Only scalar quadratic forms can be specified in CVX

2

As written, it is a non-convex constraint. But it is MIDCP representable by using binary variables.

xb(n) binary
x = 2*xb - 1; % don't declare x as variable

CVX will accept, but not solve, the problem. No solver under CVX is capable of solving it (Mosek handles Mixed-Integer for all cone type combinations except semidefinite).

Your options under MATLAB are to

  1. Use brute force enumeration (separate CVX problems) for each of the 2^n possibilities, which is reasonable for n = 3, but not for very large n
    or
  2. Use YALMIP
    a) bnb as solver combined with Mosek or other semidefinite solver as uppersolver
    or
    b) cutsdp as solver
    or
  3. Use SCIP MISDP capability, if you can figure out how to use its MATLAB interface
2 Likes
3

Dear,
Thank you so much!