Is the quadratic mixed integer problem solvable in cvx?

MIDCP
1

Hi all,

I want to solve this problem using Mixed integer optimizer in mosek:

cvx_begin
variable P1(19,19) binary
variable P2(19,19) binary
variable P3(19,19) binary
minimize(norm([P1,P2,P3]A[P1,P2,P3]’,‘fro’))

sum(P1,1)== 1
sum(P1,2)== 1
sum(P2,1)== 1
sum(P2,2)== 1
sum(P3,1)== 1
sum(P3,2)== 1
cvx_end

Here A is a pre-defined 57x57 matrix.
But MATLAB throws an error " Only scalar quadratic forms can be specified in CVX". Can cvx solve the optimization problem? Thank you!

3

This formulation violates CVX’s rules.norm, or the alternative,sun_square, both require their argument to be affine, which yours is not.

I don’t know whether there is a reformulation compliant with CVX’s rules, but I am not optimistic. Note that, in general, there is no matrix X such that A*X = P*A*P for a permutation matrix P, which appears to close off a possible angle of attack.

I offer a free virtual beer, to anyone of legal virtual drinking age, who comes up with a CVX solution. The problem can be accepted by various global MINLP solvers (not available in CVX), but whether they can produce a solution within memory and run-time constraints is another matter.