CVX reports unbounded status but with viable solution


(Mykola Servetnyk) #1

I use latest version of Mosek under cvx for solving mixed integer problem. The only variable inside my problem is binary vector, call it x. The objective is max \mu s.t \mu<=sum_log(wx) - vx(so it is a hypograph). w and v are vectors containing some weights, not a variable. There are some constraints on x and all of them are linear w.r.t. x. When I run it under cvx, Mosek outputs status “Unbounded”, but gives me a solution that is feasible and seems like correct. But I am still aware of the status. Did anyone encounter that problem before? Should I trust solution?

One idea that I have is that when Mosek starts its internal algorithm it chooses some initial point which is probably x = 0, so that objective becomes -Inf, so it reports “Unbounded” status. But this is only my guess.

Thanks.


(Mark L. Stone) #2

cvx_begin
variable x
minimize(x)
cvx_end

Calling SeDuMi 1.34: 1 variables, 0 equality constraints

SeDuMi 1.34 (beta) by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Split 2 free variables
eqs m = 1, order n = 6, dim = 6, blocks = 1
nnz(A) = 2 + 0, nnz(ADA) = 1, nnz(L) = 1
it : by gap delta rate t/tP t/tD* feas cg cg prec
0 : 2.67E+00 0.000
1 : -2.31E-01 6.05E-01 0.000 0.2267 0.9000 0.9000 0.23 1 1 1.9E+00
2 : -1.23E+00 1.29E-02 0.000 0.0214 0.9900 0.9900 -0.84 1 1 4.0E+00
3 : -1.27E+00 8.55E-08 0.011 0.0000 1.0000 1.0000 -0.99 1 1
Dual infeasible, primal improving direction found.
iter seconds |Ax| [Ay]_+ |x| |y|
3 0.2 0.0e+00 0.0e+00 2.4e+00 0.0e+00

Detailed timing (sec)
Pre IPM Post
3.780E-01 6.470E-01 2.200E-02
Max-norms: ||b||=1, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.

Status: Unbounded
Optimal value (cvx_optval): -Inf

disp(x)
-1.0000

This is an unbounded problem, reported as such. CVX returned a feasible solution. But it is not “optimal”.


(Mykola Servetnyk) #3

Thank you for that example. So can I know, why is the problem like this appearing? Is there any way to circumvent it? And is the solution suboptimal or cvx just picks any feasible solution? Btw, my problem size 36 binary variables and cvx spends around 30 seconds to give me the answer, so what is it spending time for?
Thank you very much for quick respond! Sorry for asking so many questions.


(Mark L. Stone) #4

Aside from whatever time CVX takes to process your model and call the solver (MOSEK in your case), the solver takes some time before declaring the problem to be unbounded. An integer problem could potentially take quite a while to solve, perhaps even until the solver realizes it is unbounded.

I will have to defer to someone else for an unequivocal statement on what value of the CVX variables is returned when the solver declares the problem to be unbounded. Interestingly, when I invoked SDPT3 on my example problem above, the value of x provided by CVX was also -1, but SDPT3 took 8 iterations before declaring unboundednss.


(Mykola Servetnyk) #5

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?


(Mark L. Stone) #6

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.


(Mykola Servetnyk) #7

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.


(Mark L. Stone) #8

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?


(Mykola Servetnyk) #9

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?


(Mark L. Stone) #10

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.


(Mark L. Stone) #11

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.


(Erling D.Andersen) #12

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.


(Mykola Servetnyk) #13

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?


(Mark L. Stone) #14

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.


(Mykola Servetnyk) #15

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.


(Mykola Servetnyk) #16

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


(Mark L. Stone) #17

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.


(Michael C. Grant) #18

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

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


(Mykola Servetnyk) #20

@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!