Originally posted by: Farouk HAMMAMI

Hello,

I am trying to solve a quadratic problem using CPLEX.

Observe that $w_b$ is binary and $p_b$ is a positive continuous, hence i started by linearizing the product $p_b w_b$ by adding a new variable $y_b$ however when i try to solve my problem with the following quadratic constraint, i got CPLEX error 5002: 'q1' is not convex.

Moreover $z_{kb}$ is binary and as for the other terms ($\sigma$, $\overline{p_k}$), they are known parameters.

Is there a way to solve my problem????

I want also to mention that when i change inequality sign, the problem gets solved.

Originally posted by: Laci Ladanyi

Well, you get 5002 because your constraint does not describe a convex region. Just think about it in one dimension. The x values feasible for x^2 >= 5 are [-inf,-5] and [5,inf]. And if you change the inequality sign the feasible region becomes convex, [-5,5]. By default, for such instances CPLEX returns the error indicating that you have a non-convex constraint.

However, as of version 12.6.3 CPLEX *can* solve instances with non-convex quadratic constraints. For details see the release notes for that version: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.studio.help/CPLEX/ReleaseNotes/topics/releasenotes126/newNonconvexMIQP.html

--Laci

Originally posted by: Farouk HAMMAMI

I tried adding

cplex.setParam(IloCplex.Param.OptimalityTarget, IloCplex.OptimalityTarget.OptimalConvex);

then 

cplex.setParam(IloCplex.Param.OptimalityTarget, IloCplex.OptimalityTarget.FirstOrder);

and

cplex.setParam(IloCplex.Param.OptimalityTarget,IloCplex.OptimalityTarget.OptimalGlobal);

and i still get errors.

Originally posted by: Mark L. Stone

Aren't non-convex quadratics still only allowed in the objective function, and not in the constraints?

Originally posted by: EdKlotz

Yes, Mark is right that CPLEX currently supports non-convex quadratics in the objective function, not is the constraints.   And that explains the problems Farouk reported when trying to adjust the optimality target parameter.   However, there may be some ways to address this.

1. If you can express the constraint via penalties in the objective function, that will work.  In other words, if you have x^2 - 25 >= 0, replace it with p*(25 - x^2) in the objective.   Now you have moved the nonconvexity into the quadratic objective, and the optimality target parameter should get this to work.   The question is whether you can come up with a suitable value of p that is large enough relative to your actual objective to ensure that the constraint is satisfied, but not so large that it introduces numerical problems.
2. You may be able to replace the nonconvex quadratic constraint with a disjunctive formulation.   For example, with x^2 - 25 >= 0, it is equivalent to (x +5) (x -5 )>= 0, which is equivalent to x >= 5 or x <= -5.   You can express this condition directly in most of CPLEX's APIs, particularly in the Java or C++ API you appear to use.    So if your quadratic expression can be expressed as a disjunctive condition like this as well (which seems likely based on the description), then this should work.   And don't be concerned about the discrete branching conditions you introduce here; CPLEX also branches on nonconvex quadratic objectives (and will most likely do so for quadratic constraints if and when support is added for that).
3. If neither of the first two approaches work, you can always try piecewise linear approximations to the nonconvex constraints.

Originally posted by: Laci Ladanyi

Yes, of course, you are correct. What you can do with non-convex constraints is what Ed has described.