Hi,
I'm trying to use CPLEX 10.2.0 and AMPL to solve a program, which has a linear objective function and several constraints, which are sums of products of two variables.
The first question is: Is this a QCP? If not, how is it called?
When I try to solve the problem CPLEX doesn't start and says "CPLEX 10.2.0: QP Hessian is not positive semidefinite.; no basis.". I wonder, why it interprets the program as a quadratic program since i have quadratic constraints.
I also read something about QCP in the manual and it says that CPLEX will solve those problems with the Barrier algorithm. So I used the directive "option cplex_options 'baropt';" to force the use of this algorithm, but CPLEX stops with error #1031.
It would be great if someone could tell me how to solve my problem.
Thanks in advance and greetings
Topic

Re: Solve QCP
20091201T08:40:39ZThis is the accepted answer. This is the accepted answer.Your problem is a QCP (quadratically constrained problem). But CPLEX cannot solve all QCPs, it can only solve those where the Q matrix is positive semidefinite. With such a matrix, the problem is convex and it is solvable in polynomial time. If the matrix is nonconvex, then the problem is much harder and has to be solved in a completely different way. As I said, at the moment CPLEX only supports the "easy" positive semidefinite variant.
Unfortunately, there is no "fix" to your problem, since the nonconvexity is (I guess) a fundamental property of your problem. Maybe, you can come up with a (potentially larger) formulation that is convex? 
Re: Solve QCP
20091201T10:33:54ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20091201T08:40:39Z
Your problem is a QCP (quadratically constrained problem). But CPLEX cannot solve all QCPs, it can only solve those where the Q matrix is positive semidefinite. With such a matrix, the problem is convex and it is solvable in polynomial time. If the matrix is nonconvex, then the problem is much harder and has to be solved in a completely different way. As I said, at the moment CPLEX only supports the "easy" positive semidefinite variant.
Unfortunately, there is no "fix" to your problem, since the nonconvexity is (I guess) a fundamental property of your problem. Maybe, you can come up with a (potentially larger) formulation that is convex?
Can you tell me what which matrix you call Q ? I found many different definitions, sometimes there was one matrix H, sometimes many matrices P_i for each constraint.
I'll then try to make my problem bigger, maybe I'm lucky.
Thanks! 
Re: Solve QCP
20091201T10:34:50ZThis is the accepted answer. This is the accepted answer. HerrVorragend
 20091201T10:33:54Z
Thank you very much for your answer.
Can you tell me what which matrix you call Q ? I found many different definitions, sometimes there was one matrix H, sometimes many matrices P_i for each constraint.
I'll then try to make my problem bigger, maybe I'm lucky.
Thanks!
a_0 x_0^2 + sum a_j x_j^2 <= 0
with a_j >= 0, i.e., a sum of squares smaller or equal than a square. 
Re: Solve QCP
20091201T10:37:58ZThis is the accepted answer. This is the accepted answer. HerrVorragend
 20091201T10:33:54Z
Thank you very much for your answer.
Can you tell me what which matrix you call Q ? I found many different definitions, sometimes there was one matrix H, sometimes many matrices P_i for each constraint.
I'll then try to make my problem bigger, maybe I'm lucky.
Thanks!
In order to check convexity, the main question you have to ask yourself is the following: if you have two feasible solutions x and y to your problem, is every convex combination z = s*x + (1s)*y with 0 <= s <= 1 also a feasible solution? If this is the case, your problem is convex. If it is not the case, your problem is nonconvex. 
Re: Solve QCP
20091202T20:19:15ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20091201T10:37:58Z
By the way: "I'll then try to make my problem bigger, maybe I'm lucky." does not seem to be a good approach. You need to analyze mathematically whether your problem is convex or not. Fiddling around and just hoping for the best will not be successful.
In order to check convexity, the main question you have to ask yourself is the following: if you have two feasible solutions x and y to your problem, is every convex combination z = s*x + (1s)*y with 0 <= s <= 1 also a feasible solution? If this is the case, your problem is convex. If it is not the case, your problem is nonconvex.
i tried to check my program for convexity and i think it is convex. That's good news, isn't it? :)
So what now? What should I do now?
Thank you! 
Re: Solve QCP
20091202T20:26:13ZThis is the accepted answer. This is the accepted answer. HerrVorragend
 20091202T20:19:15Z
Hi,
i tried to check my program for convexity and i think it is convex. That's good news, isn't it? :)
So what now? What should I do now?
Thank you!
Having the model at hand, I can probably find out where the issue is. 
Re: Solve QCP
20091202T20:58:19ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20091202T20:26:13Z
I guess the problem is still that CPLEX claims that the Hessian is not positive semidefinite. If you like, you can send me your model (as *.lp, *.mps, or *.sav file; I hope that AMPL provides such an output). If it is not too large after compression, you can send it to me as email: achterberg "at" de "dot" ibm "dot" com. If it is big, we can find other means.
Having the model at hand, I can probably find out where the issue is. 
Re: Solve QCP
20100112T15:21:04ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20091202T20:26:13Z
I guess the problem is still that CPLEX claims that the Hessian is not positive semidefinite. If you like, you can send me your model (as *.lp, *.mps, or *.sav file; I hope that AMPL provides such an output). If it is not too large after compression, you can send it to me as email: achterberg "at" de "dot" ibm "dot" com. If it is big, we can find other means.
Having the model at hand, I can probably find out where the issue is.
I am trying to solve a fairly simple problem (x^2) with linear constraints. As far as I know its a convex problem. However, I get the same CPLEX Error 5002: Q in %s is not positive semidefinite error which is making me insane now. Any hints what I've missed?
IloCplex cplex = new IloCplex();
IloNumVar x = cplex.numVar(0,5);
IloNumExpr obj= cplex.square(x);
cplex.addMaximize(obj);
if(cplex.solve())
System.out.println(cplex.getValue(x));
Would be very thankful for any help,
Moody 
Re: Solve QCP
20100112T15:49:03ZThis is the accepted answer. This is the accepted answer. MoodyAlam
 20100112T15:21:04Z
Hi Tobias,
I am trying to solve a fairly simple problem (x^2) with linear constraints. As far as I know its a convex problem. However, I get the same CPLEX Error 5002: Q in %s is not positive semidefinite error which is making me insane now. Any hints what I've missed?
IloCplex cplex = new IloCplex();
IloNumVar x = cplex.numVar(0,5);
IloNumExpr obj= cplex.square(x);
cplex.addMaximize(obj);
if(cplex.solve())
System.out.println(cplex.getValue(x));
Would be very thankful for any help,
Moody
> MoodyAlam wrote:
> I am trying to solve a fairly simple problem (x^2) with linear constraints. As far as I know its a convex problem. However, I get the same CPLEX Error 5002: Q in %s is not positive semidefinite error which is making me insane now. Any hints what I've missed?
>
> IloCplex cplex = new IloCplex();
> IloNumVar x = cplex.numVar(0,5);
> IloNumExpr obj= cplex.square(x);
>
> cplex.addMaximize(obj);
>
> if(cplex.solve())
> System.out.println(cplex.getValue(x));
>
The problem is that you are attempting to maximize a convex function, which is a nonconvex problem. For the problem to be convex, you should be minimizing a convex function or maximizing a concave one. I'm pretty sure the source of the message is that CPLEX converts your objective to minimization of x^2 and then (correctly) decides that x^2 is not at least weakly convex (since it is strictly concave).
/Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe) 
Re: Solve QCP
20101007T19:15:01ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20091201T08:40:39Z
Your problem is a QCP (quadratically constrained problem). But CPLEX cannot solve all QCPs, it can only solve those where the Q matrix is positive semidefinite. With such a matrix, the problem is convex and it is solvable in polynomial time. If the matrix is nonconvex, then the problem is much harder and has to be solved in a completely different way. As I said, at the moment CPLEX only supports the "easy" positive semidefinite variant.
Unfortunately, there is no "fix" to your problem, since the nonconvexity is (I guess) a fundamental property of your problem. Maybe, you can come up with a (potentially larger) formulation that is convex?
Thank you 
Re: Solve QCP
20101008T05:33:37ZThis is the accepted answer. This is the accepted answer. Beca
 20101007T19:15:01Z
At this moment CPLEX, what are the "easy" variant of positive semidefinite, could you please tell me where can i found some examples.
Thank you
"easy" does not refer to some special kind of being positive semidefinite.
CPLEX ships one example for qcps you may want to look at. Depending on which API you want to use this example is in one of
 qcpex1.c for the C API
 iloqcpex1.cpp for the C++ API
 QCPex1.java for the Java API
 QCPex1.cs for C#
 qcpex1.m for matlab
 qcpex1.py for python
 qcpex1.xls for Excel

Re: Solve QCP
20130113T05:33:50ZThis is the accepted answer. This is the accepted answer.Dear All,
I really need your help regarding a MIQCP in CPLEX. I formulated the problem and then tried to solve it in CPLEX but I am getting the following error:
"CPLEX Error 5002: Q in 'id182' is not positive semidefinite."
Is there any way to deal with this issue. I mean, if the constraints are not positive semidefinite, can we still solve the problem in CPLEX?
I really appreciate your help. If you want me to send the code, I will send it. Here are some of the constraints:
sum (t in Periods) X[t] Y[t]== sum (t in Periods) N[t];* where X[t] is a binary decision variable and Y[t] is an integer decision variable. 
Re: Solve QCP
20130115T22:47:51ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130113T05:33:50Z
Dear All,
I really need your help regarding a MIQCP in CPLEX. I formulated the problem and then tried to solve it in CPLEX but I am getting the following error:
"CPLEX Error 5002: Q in 'id182' is not positive semidefinite."
Is there any way to deal with this issue. I mean, if the constraints are not positive semidefinite, can we still solve the problem in CPLEX?
I really appreciate your help. If you want me to send the code, I will send it. Here are some of the constraints:
sum (t in Periods) X[t] Y[t]== sum (t in Periods) N[t];* where X[t] is a binary decision variable and Y[t] is an integer decision variable.
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)