Topic
  • 13 replies
  • Latest Post - ‏2013-01-15T22:47:51Z by SystemAdmin
Herr-Vorragend
Herr-Vorragend
4 Posts

Pinned topic Solve QCP

‏2009-11-30T20:58:16Z |
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 semi-definite.; 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
Updated on 2013-01-15T22:47:51Z at 2013-01-15T22:47:51Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2009-12-01T08: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 non-convex, 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 non-convexity is (I guess) a fundamental property of your problem. Maybe, you can come up with a (potentially larger) formulation that is convex?
  • Herr-Vorragend
    Herr-Vorragend
    4 Posts

    Re: Solve QCP

    ‏2009-12-01T10:33:54Z  
    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 non-convex, 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 non-convexity is (I guess) a fundamental property of your problem. Maybe, you can come up with a (potentially larger) formulation that is convex?
    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!
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2009-12-01T10:34:50Z  
    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!
    There is one Q per constraint, see the user's manual section "Solving Problems with Quadratic Constraints (QCP)". Each of them has to be either positive semi-definite or in the form of a second order cone, which is

    -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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2009-12-01T10:37:58Z  
    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!
    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 + (1-s)*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 non-convex.
  • Herr-Vorragend
    Herr-Vorragend
    4 Posts

    Re: Solve QCP

    ‏2009-12-02T20:19:15Z  
    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 + (1-s)*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 non-convex.
    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!
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2009-12-02T20:26:13Z  
    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!
    I guess the problem is still that CPLEX claims that the Hessian is not positive semi-definite. 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.
  • Herr-Vorragend
    Herr-Vorragend
    4 Posts

    Re: Solve QCP

    ‏2009-12-02T20:58:19Z  
    I guess the problem is still that CPLEX claims that the Hessian is not positive semi-definite. 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.
    You got mail :)
  • MoodyAlam
    MoodyAlam
    1 Post

    Re: Solve QCP

    ‏2010-01-12T15:21:04Z  
    I guess the problem is still that CPLEX claims that the Hessian is not positive semi-definite. 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.
    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 semi-definite 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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2010-01-12T15:49:03Z  
    • MoodyAlam
    • ‏2010-01-12T15: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 semi-definite 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
    For future reference, it would be better to post questions like this as new threads rather than "jumping" someone else's thread.

    > 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 semi-definite 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 non-convex 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)
  • Beca
    Beca
    1 Post

    Re: Solve QCP

    ‏2010-10-07T19:15:01Z  
    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 non-convex, 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 non-convexity is (I guess) a fundamental property of your problem. Maybe, you can come up with a (potentially larger) formulation that is convex?
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2010-10-08T05:33:37Z  
    • Beca
    • ‏2010-10-07T19: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
    With "easy" Tobias means that the Q matrix for each constraint is positive semidefinite or of second order cone form for each constraint.
    "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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2013-01-13T05: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 semi-definite."

    Is there any way to deal with this issue. I mean, if the constraints are not positive semi-definite, 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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Solve QCP

    ‏2013-01-15T22:47:51Z  
    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 semi-definite."

    Is there any way to deal with this issue. I mean, if the constraints are not positive semi-definite, 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.
    If Y is bounded, you can linearize the product of X and Y (at some expense in terms of adding variables and constraints). See, for instance, Binary Variables and Quadratic Terms.

    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)