I tripped over the following while replying to a question on OR Stack Exchange. The starting point is a feasible region consisting of all points where f(x) <= 0, where f(x) = x'Qx + q'x + q0 and Q is positive definite. The question dealt with cases where the feasible region is unbounded (which I'm pretty sure it cannot be). So I coded a few models using CPLEX (Java API) and ran into the following. One model maximizes the L1 norm of any feasible x and a second model maximizes the L-infinity norm. Both of those will frequently claim test problems are unbounded, although there are cases where one says the problem is unbounded and the other says it is bounded.

Now it gets weirder. A third model uses the L-infinity norm, but differs from the second model. In both, I have a nonnegative variable y that captures the inf norm. In the second model, the objective is to maximize y. In the third model, the objective is to minimize 0 and I set progressively larger lower bounds on y until it claims the problem is infeasible. The third model always reaches a (not particularly large) lower bound at which the problem is infeasible (meaning the feasible region is bounded by that value of the inf norm), even when the second model says it is unbounded. The two models are identical other than the lower bound on y and the choice of objective function.

I've documented the problem (including what I think is a proof that the feasible region must be bounded) in a blog post, and supplied details of the models use and a link to the Java code in a second post. I'd be interested to know if there is an explanation for this.

#IBMChampion 

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------