Dear Mark, in your case problem is really unbounded and solution x = -1 is definitely wrong. But in my case objective is max_{x} sum_log(wx) - vx s.t x \in {0,1} which is obviously not ‘unbounded’. I use cvx for around two years only, I’m not sure, maybe it is a bug?
I will probably repeat, but I am curious not about what values cvx returns when problem is unbounded but rather why it reports unboundness whether it is obvious for us that it is not unbounded?
Please provide complete reproducible code (including the values of all MATLAB variables) and your results, including MOSEK output, in order to enable people to evaluate your claims.
Dear Mark, below I attach code that reports me unbounded status, but still provides solutions, which are feasible, but I want to know is it optimal or suboptimal as well as why problem is reported to be unbounded. Thank you very much for your support!
clc;
for i = 1:3
q = randn(12,1) + 1irandn(12,1);
Q(:,:,i) = qq’;
H(:,:,i) = randn(12,12) + 1irandn(12,12);
end
cvx_solver Mosek
cvx_begin
variable X(12,12,3) binary
variable mu_B
maximize mu_B
subject to
mu_B <= log(real(trace(H(:,:,1)(Q(:,:,1).*X(:,:,1))H(:,:,1)’)))+ …
log(real(trace(H(:,:,2)(Q(:,:,2).X(:,:,2))H(:,:,2)’)))+ …
log(real(trace(H(:,:,3)(Q(:,:,3).X(:,:,3))H(:,:,3)’)))-…
0.1(diag(squeeze(X(:,:,1))))-…
0.1(diag(squeeze(X(:,:,2))))-…
0.1(diag(squeeze(X(:,:,3))))
for k = 1:3
for i=1:12
for j=1:12
X(i,j,k) <= X(i,i,k);
X(i,j,k) <= X(j,j,k);
X(i,j,k) >= X(i,i,k)+X(j,j,k)-1;
end
end
end
cvx_end
display(mu_B); display(X);
Result is below:
Successive approximation method to be employed.
Mosek will be called several times to refine the solution.
Original size: 1678 variables, 1242 equality constraints
3 exponentials add 24 variables, 15 equality constraints
I don’t have MOSEK available to actually solve the problem, although other forum members do, but I haven’t even succeeded in getting it entered. Plus it seems somewhat more complicated than how you described it, so I am not even mentally understanding what your problem specification is.
Why do you believe that your problem is not unbounded?
I think my problem is bounded because objective is basically function of X and X is bounded since it’s finite and countable and no one binary combination of X cannot make log(f(X)) go to +Inf.
Unfortunately, only Mosek solver is able to solve this class of problems, so to run that instance of code you should have it. Btw, I use Matlab 2015a. Don’t really understand why do you get that error.
Indeed log function is unbounded from the top(as we are interested in maximization). How do you think, may it be an issue?
The error I was getting was due to missing instances of * in that constraint, which apparently was lost in the forum formatting process, even when I tired to edit it by clicking on preformatted text.
I inserted the missing * 's , removed the binary designation, and added its continuous relaxation 0 <= X <= 1. then solved it with sedumi. I did runs with several random instantiations of q and H, and on each occasion, sedumi/CVX claimed to have solved the problem, producing cvx_optval in the range of 20 to 23. For each random instantiation, I also solved the problem using SDPT3, and got the same cvx_optval as with sedumi. So of course, if that is really correct, and X were really constrained to be binary, the problem should not be unbounded.
I will have to defer to the CVX and MOSEK gurus to further diagnose. I have no idea whether the use of CVX"s successive approximation method to deal with log is playing a role in the matter.
While awaiting additional assistance, it might be a good idea for you to reproduce what I did, namely, remove binary from the declaration of X, and impose the constraint 0 <= X <= 1 . It would be interesting to see what happens when you run that with MOSEK as solver. Of course, when comparing different formulations and solvers, run all the variations with the same input data, i.e., without generating new random instantiations of q and H.
Right, I forgot to write. I’ve tried continuous relaxation and indeed Mosek and SDPT3 are able to solve the problem. The rang of the solution is from 19 to 23, so I guess it is the same as your results.
Just out of curiosity, have you tried binary declaration together with 0 <= X <= 1? Of course, that should be redundant, but I have no idea what it will do.
I’m sorry I haven’t been able to look at this, but I don’t have an answer for you. Unfortunately, I haven’t attempted to solve problems that combine the successive approximation approach with binary variables. So I don’t think we can support this.
@Mark_L_Stone, thank you! unfortunately in that topic @mcg said: “In a future update of CVX I am going to have to detect and reject this particular combination of constraints.” So I guess this topic can be closed now. Thanks everyone for help!
I think this problem should be solvable now using MOSEK as solver with CVXQUAD’s Pade approximation for the exponential cone, which avoids use of CVX’s successive approximation method. I am not aware of anyone having verified correct behavior when using the CVXQUAD algorithm with binary variables, but I see no reason (famous last words) why it should not work.
This requires installing CVXQUAD https://github.com/hfawzi/cvxquad , including replacing the exponential.m function in the CVX sets directory with CVXQUAD"s version. This will also require reformulating the log constraints using the explicit exponential cone formulation . I.e.,. use the constraint { x, y, z } == exponential(1)
to model y*exp(x/y) <= z
This is necessary because the CVXQUAD Pade approximation gets invoked for entr, rel_entr , and explicit exponential cone constraint, but not for log or exp by themselves.
At such time as MOSEK 9.0, which will have native exponential cone support (allowing use of mixed integer for exponential cone), comes out, and a version of CVX which utilizes that exponential cone support is available, then none of these workarounds should be necessary.
Hi Mark, I want to use XNOR logic between two binary variables, is it possible to use in CVX? or how can I solve the problem. e.g I have A=[1 0 0 1] and B=[0 1 0 1], and the result I want [0 0 1 1].