Why can't CVX solve my problem and the status is overdetermined?

1

Here is my optimization code：
beta=[3.7 4.2 7.8 0.4;6.4 2.4 9.6 1.7;0.4 3.8 8.5 4.6;5.6 7.6 8.4 3.5;6.4 1.6 3.2 5.9;6.3 2.7 0.5 6.4];
cvx_solver mosek
cvx_begin
% cvx_quiet(true);
variable nu1(6,4) binary;
variable nu2(6,4) binary;
variable nu3(6,4) binary;
variable nu4(6,4) binary;
minimize sum(sum(nu1.*beta+nu2.*beta+nu3.*beta+nu4.*beta));

subject to
nu1(:,1)==0;
nu2(:,2)==0;
nu3(:,3)==0;
nu4(:,4)==0;
for i=2:6
nu1(i,:)==nu1(1,:);
nu2(i,:)==nu2(1,:);
nu3(i,:)==nu3(1,:);
nu4(i,:)==nu4(1,:);
end

nu1(1,2)==nu2(1,1);
nu1(1,3)==nu3(1,1);
nu1(1,4)==nu4(1,1);
cvx_end
nu1
nu2
nu3
nu4

The results of optimization variables nu1,nu2,nu3 and nu4 are all NaN,and the following prompt message appears:
Redundant equality constraints detected.
** CVX cannot solve this problem; but it is likely infeasible.**
Status: Overdetermined
Optimal value (cvx_optval): NaN

nu1 =

NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN

nu2 =

NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN

nu3 =

NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN

nu4 =

NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN
NaN NaN NaN NaN

2

I don’t know why CVX refuses to send the problem to the solver.

However, if the binary declarations are removed and constraints 0<= nu1 <= 1 ,0<= nu2 <= 1 0<= nu3 <= 1 0<= nu4 <= 1 inserted, then CVX does submit the problem to Mosek, which reports the correct optimal solution of all variables being all zeros. This is also the optimal solution to the original binary-restricted problem.

3

I add the following constraints so that the optimal solution nu1,nu2,nu3,nu4 are no longer all zeros.
0<=sum(nu1(1,:))<=3;
0<=sum(nu1(1,:))<=3;
0<=sum(nu1(1,:))<=3;
0<=sum(nu1(1,:))<=3;

4<=sum(nu1(1,:))+sum(nu1(1,:))+sum(nu1(1,:))+sum(nu1(1,:))<=12;
The results of optimization variables nu1,nu2,nu3 and nu4 are still all NaN,and the following prompt message appears again:
Redundant equality constraints detected.
** CVX cannot solve this problem; but it is likely infeasible.**
Status: Overdetermined
Optimal value (cvx_optval): NaN

4

I again relaxed the binary constraints to [0,1] and Mosek solved the problem to optimality. The solution elements consist only of ones or zeros, within solver tolerance, and therefore is optimal for the original (unrelaxed) binary problem.

I tired it both ways with nu1, nu2, nu3, nu4 for your new constraints, as well as all with nu1 as you posted, The solution changed, but was still all zeros and ones.

5

Here is a minimal example. Funny behavior from cvx. Probably a bug.

cvx_begin
cvx_solver Mosek

variable n binary;
variable m binary;
minimize n+m

subject to
n==0;
m==0;
n==m;

cvx_end
6

Not sure whether this is a bug or a feature.

7

Indeed, thank you for your answer!

8

Thank you for your example.The values of M and N are both NaN.It’s so frustrating.

9

I suggest you create a bug report and submit it to the cvx maintainer. You may have to wait quite bit of time for a fix though.

In the meantime you can try the MATLAB interface to Mosek. If a bug appears we will fix it quickly :-).