Is there a way to specify an initial condition (value) for a MIDCP? In some cases, it seems that it converges to a local minimum. With an initial condition, this could be avoided.
Thanks
Update: I found the problem! It sounds silly but I forgot to put “subject to” in my optimization problem. I tried it several times and I am sure this is the reason for the strange behavior of CVX. One might think by missing “subject to” you should get an error but CVX tries to solve the problem anyway and comes up with a wrong answer. You might want to address this issue in the next releases. Thanks again for your response and help.
I’m afraid there is no way to specify an initial value, and there likely will not be in the near future.
Under what circumstances do you believe it converges to a local minimum? Since the underlying, relaxed problem is convex, there really is no local minimum per se. Given enough time (and assuming no underling numerical conditioning problems), the MIDCP algorithms in Gurobi and MOSEK should indeed converge to a global solution.
You may wish to consult the documentation of your preferred solver to see if there are some solver parameters that may improve the performance of the integer algorithms in your case.
EDIT: Thanks for the update. This is certainly interesting. If you’ll send us a copy of your model, or at the very least, a copy of the full output of the solver logs, I would genuinely interested to take a look. And I think the CVX community would benefit from knowing what is going on here.
But again—there isn’t really a local minimum here. For standard (non-integer) convex optimization problems, every local optima must also be global. That’s just a fundamental property of convexity.
However, when you add integer constraints to the mix, things do get considerably more complicated—the problem becomes theoretically intractable. MIDCP algorithms simply cannot guarantee that they will reach the global minimum in finite time. So, they will often terminate if they do not see progress in reducing the optimal after a certain number of steps. You’re probably seeing different solutions in each run because it’s starting from different starting points each time, or randomizing the cuts it takes.
If you want to know just how odd integer programming algorithms can behave sometimes, check out this very interesting blog post by Michael Trick about some recent work done by Matteo Fischetti.
Thanks for your comment. I think it converges to a local minimum because if I run the same problem several times, I get totally different answers. This happens more often with MOSEK than with Gurobi. So I though an initial value could help the situation.
There is absolutely no reason why adding “subject to” should change things. Look at the code for “commands/subject.m” and see for yourself: it’s a complete no-op. I provide it ONLY to help people make their code more readable; it is supposed to be optional.