Originally posted by: Moslem Zamani

Consider the following bilinear quadratic program,
  min x1x7+x2x8-x1+x5-x6
   s.t.  x1+x2=1,
        -x3+x5-x6+x7=0,
      -x4+x5-x6+x8=0,
      x1, x2, x3, x4, x5, x6>=0,
     x7, x8>=1.
Its optimal value is -1, consider (1,0,0,0,0,1,1,1). When I model this problem via cplexqp (opt.optimalitytarget=3) on MATLAB, surprisingly, it announces  the problem is unbounded. Of course, the problem is bounded, because objective function can be written as follows (consider multiplication of second and third constraint by x₁ and x₂, respectively)
x1x7+x2x8-x1+x5-x6=-x1+x1x3+x2x4.
 I used global solver cplexqp many times and always provided the best solution compared to the other solvers. I wonder why it cannot handle this problem. My CPLEX version is 12.8.

Consider this solution:

x1 = 1
x2 = 0
x3 = k+1
x4 = k+1
x5 = 0
x6 = k
x7 = 1
x8 = 1

For k>= 0. As far as I can tell, this is feasible and has objective value -k. Since k can be arbitrarily large, the model indeed looks unbounded.

Originally posted by: Moslem Zamani

Thanks for your response. However, your given point is not feasible. (-2k=0!!!)

Yes, sorry, my fault. I mixed up the sign for x6 in the constraints.

There seem to be indeed some problems with this model in CPLEX. We are looking into this.

Originally posted by: JohanLöfberg

Moslem is correct. The globally optimal solution has objective -1 (validated with global solvers in YALMIP), and the proposed unbounded solution above is not feasible.

Originally posted by: PierreBonami

Hi sorry for the long time to answer,

I ran the model in matlab and the status I get is:
statusstring: 'constructed relaxation is unbounded'

which is legitimate in that case.

Most global solver don't have this status. For an indefinite quadratic optimization problem, it may happen that the convex relaxation we construct is unbounded. From that point, one can try to solve the model anyway as is. It may succeed (like in this case aparently with YALMIP) but it may also leads to something that looks a lot like an infinite loop (it is relatively easy to construct examples).

The simplest workaround is to put some reasonnable large bounds (here on the variables x7 and x8).

I have put bounds of 1e4, the solve with CPLEX unfortunately still has difficulties to converge. There are also some issues in reporting: in the log CPLEX reports solution of cost slightly lower than -1 but those are round off errors.

We will try to fix all these in the future.

Originally posted by: Mark L. Stone

Will explicit finite lower and upper bounds on all variables always prevent this bug from manifesting itself, because all convex relaxations will be bounded? Or is this true only if the bounds aren't large enough in magnitude  to cause numerical havoc?

Originally posted by: PierreBonami

Yes putting explicit bounds (unless they are > 1e20) will prevent having this solution status (it is not a bug)

Originally posted by: Moslem Zamani

Hi,
Thanks for your response. In fact, the given optimization problem obtained by setting the parameters of following bilinear problem

                                   min w^' b+v'Dx

                                    s.t.  Ax=b,

                                           w^' A+v'D>=c^'

                                                     x>=0, v>=e,

where x, v, w are decision variables and e is vector of ones. In this model, the set {x: Ax=b, x>=0} is bounded. It is easily seen that the above problem is bounded. However, I put some bounds for v and w. In most cases, CPLEX's performance was not satisfactory (replacing the objective function by w^' Ax+v'Dx made no defference).