CVX reports unbounded status but with viable solution

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) = q
q’;
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

Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status
--------±--------------------------------±--------
3/ 3 | 8.000e+00 3.613e+00 2.209e-07 | Solved
3/ 3 | 1.470e+00 1.390e-01 0.000e+00 | Solved
3/ 3 | 6.935e-02 3.010e-04 0.000e+00 | Solved
0/ 0 | 0.000e+00 0.000e+00 0.000e+00 | Solved

Status: Unbounded
Optimal value (cvx_optval): +Inf

mu_B =

19.2114

X(:,:,1) =

Columns 1 through 7

 1     1     1     1     0     1     1
 1     1     1     1     0     1     1
 1     1     1     1     0     1     1
 1     1     1     1     0     1     1
 0     0     0     0     0     0     0
 1     1     1     1     0     1     1
 1     1     1     1     0     1     1
 0     0     0     0     0     0     0
 1     1     1     1     0     1     1
 1     1     1     1     0     1     1
 1     1     1     1     0     1     1
 1     1     1     1     0     1     1

Columns 8 through 12

 0     1     1     1     1
 0     1     1     1     1
 0     1     1     1     1
 0     1     1     1     1
 0     0     0     0     0
 0     1     1     1     1
 0     1     1     1     1
 0     0     0     0     0
 0     1     1     1     1
 0     1     1     1     1
 0     1     1     1     1
 0     1     1     1     1

X(:,:,2) =

Columns 1 through 7

 0     0     0     0     0     0     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     0     0     0     0     0     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0
 0     1     1     1     1     1     0

Columns 8 through 12

 0     0     0     0     0
 1     1     1     1     1
 1     1     1     1     1
 1     1     1     1     1
 1     1     1     1     1
 1     1     1     1     1
 0     0     0     0     0
 1     1     1     1     1
 1     1     1     1     1
 1     1     1     1     1
 1     1     1     1     1
 1     1     1     1     1

X(:,:,3) =

Columns 1 through 7

 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 0     0     0     0     0     0     0
 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 1     1     1     1     1     1     0
 0     0     0     0     0     0     0
 1     1     1     1     1     1     0

Columns 8 through 12

 1     1     1     0     1
 1     1     1     0     1
 1     1     1     0     1
 1     1     1     0     1
 1     1     1     0     1
 1     1     1     0     1
 0     0     0     0     0
 1     1     1     0     1
 1     1     1     0     1
 1     1     1     0     1
 0     0     0     0     0
 1     1     1     0     1

Thank you for looking at it.

Using MATLAB R2014A and CVX 2.1, I got

Error: ()-indexing must appear last in an index expression.

when I entered the first constraint

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))))

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?

Dear Mark,

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.

1 Like

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.

I agree with Mark.

Moreover, MOSEK cannot deal with the log directly. So CVX does an iterative process i.e.

Successive approximation method to be employed.

Maybe that process has issues.

Dear Erling, thank you for looking at my problem too. So should I report for this issue somewhere else? What would you suggest me to do?

I think you need to wait for @mcg to look at this.

But in the meantime you could do the extra runs I suggested and report the results.

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.

I’m awaiting for @mcg answer. Problem is still actual. Thank you!

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.

I just discovered this thread from the annals of history Optimization problems containing binary variable .

@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].

You should be able to do this using the MIDCP capability of CVX. You will need to declare binary variables. You ought to be able to use an approach as shown at https://cs.stackexchange.com/questions/12102/express-boolean-logic-operations-in-zero-one-integer-linear-programming-ilp for xor, but adjusted to handle xnor.

Thanks for your reply, I am trying it