implies problem with sdpvar as input condition and binvar as resulting constraint

[Yan]

Hi All,

I am solving an optimization problem with implies. Although I only the following a few lines, it could not give me the correct result, as double(X)= [0 0 0 0]; double(XF)=[0.5 0.5 0.5 0.5]; etc. I guess the problem that leads to the infeasible solution may rely on the parts with bold fonts below. But still I have no idea about the correct command.

X=sdpvar(1,NodeNum,'full');Y=sdpvar(NodeNum,NodeNum,'full');XF=binvar(1,NodeNum,'full');

Z=binvar(NodeNum,NodeNum,'full'); V=[1 0.4 1 1];

for p=1:NodeNum

  F=[F, sum(Y(p,:))==X(p) X(p)<=V(p) implies(X(p),XF(p))];%If X(p)>0, XF=1, otherwise, XF(p)=0

  F=[F, sum(Y(:,p))<=V(p) X(p)*(sum(Y(:,p))-Y(p,p))==0];%Y(p,p)means node p itself can join the computation,

  for q=1:NodeNum

      F=[F; implies(Y(p,q),Z(p,q))]; % if Y(p,q) >0, then Z(p,q)=1

  end

end

C=sum(sum(Y));

options=sdpsettings('solver','bnb','verbose',0,'debug',1);

opt=optimize(F,C,options); %get maximal C

double(C)

x=double(X)

xf=double(XF)

y=double(Y)

z=double(Z)

Thanks a lot!

[Johan Löfberg]

You are multiplying variables generating bilinear nonconvex constraints, so using bnb is not sensible. bmibnb is applicable, but fails as the search-space is unbounded

[Johan Löfberg]

and this

F=[F; implies(Y(p,q),Z(p,q))]; % if Y(p,q) >0, then Z(p,q)=1

is numerically ill-conditioned

[Yalmipfan]

I modify it to F=[F;  implies(X(p)>=1e-2,XF(p)==1)  implies(X(p)<1e-2,XF(p)==0); by introducing a threshold 1e-2 and also the same way to Z(p,q), now it can give me a feasible solution by bmibnb,.

But I have another question. In my optimization, besides the above constraints on X, Y, XF, and Z, there are also additional constraints imposed by some other unknown variables, e.g., Va, cc, which are both highly nonlinear and more complex. If I take all these (including X, Y, XF, Z, Va, cc) as unknown variables to be optimized, neither bnb or bmibnb could give a feasible solution. But if I manually give X, Y, XF and Z, the optimization always yields an optimal solution for Va and cc (Of course, the given X, Y ,XF and Z satisfy the constraints on my first post). Since this overall solution with Va and cc, together with the given X, Y, XF and Z actually composite a complete solution (although it is not overall optimal since the X and Y are manually given), therefore, we can infer that the formulation for this optimization is reasonable, right? But what maybe the fundamental problem? 

Thanks a bunch!

[Johan Löfberg]

Don't use strict inequality. YALMIP will complain. Only non-strict inequalities are allowed.

First, bnb is never guaranteed to work on problems with nonconvexity in continuous space, which you have.

If bmibnb fails, but you know there exists a solution, and you let it run without terminating after default 100 iterations, the problem(formulation) is simply to complicated.

[Yalmipfan]

Thanks for your reply! I am only aware of setting the max iterations using 'bmibnb.maxiter', but how to let it run without terminating? Do I just simply set the maxiter to be pretty large like 1000?

[Johan Löfberg]

yes. but if you are unlucky it needs 10^10 iterations