Topic
  • 12 replies
  • Latest Post - ‏2013-02-20T23:55:38Z by EdKlotz
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic positive semi-definite quadratic constraint problem

‏2013-01-03T16:15:22Z |
Hi,

I am trying to solve a quadratic programing problem with quadratic constraints. My problem is with the constraints. Ordinarily quadratic constraints should take the form of:

b x + x T Q x < r

However, for my problem, the constraints instead take the form of:

b x - x T Q x < r

Q is positive semi-definite. However, if I try to redefine a new matrix K = - Q to form a new equation:

b x + x T K x < r

the problem cannot be solved, because K is not positive semi-definite.

Any thoughts on how to solve this problem??
Thanks
Updated on 2013-02-20T23:55:38Z at 2013-02-20T23:55:38Z by EdKlotz
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-03T17:02:21Z  
    Aren't you not making a convex function concave by changing the sign? If so, changing the <= r to >= r should make it PSD.

    Regards,
    Vivek.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-03T20:56:01Z  
    Aren't you not making a convex function concave by changing the sign? If so, changing the <= r to >= r should make it PSD.

    Regards,
    Vivek.
    Hi Vivek,

    Do you know if there is an option in CPLEX to handle quadratic constraints which are > (the basic documentation defines the constraints as < ). If so, do you know what the syntax for that option is?

    Thanks for the answer.

    Marshall
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-03T21:11:31Z  
    Hi Vivek,

    Do you know if there is an option in CPLEX to handle quadratic constraints which are > (the basic documentation defines the constraints as < ). If so, do you know what the syntax for that option is?

    Thanks for the answer.

    Marshall
    There's no easy fix. b x - x^T^ Q x < r with Q psd causes the feasible region not to be convex. CPLEX (as well as all LP/MIP/QP solvers and most but not all NLP solvers) requires the feasible region (after relaxing any integrality restrictions) to be convex.

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

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-04T03:38:22Z  
    There's no easy fix. b x - x^T^ Q x < r with Q psd causes the feasible region not to be convex. CPLEX (as well as all LP/MIP/QP solvers and most but not all NLP solvers) requires the feasible region (after relaxing any integrality restrictions) to be convex.

    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)
    Hi Paul,

    Are there any NLP solvers that you would recommend to deal with this problem?

    Thanks,

    Marshall
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-04T05:40:09Z  
    Hi Vivek,

    Do you know if there is an option in CPLEX to handle quadratic constraints which are > (the basic documentation defines the constraints as < ). If so, do you know what the syntax for that option is?

    Thanks for the answer.

    Marshall
    Hi Marshall,

    The CPXaddqconstr() in C Callable API has support for adding both <= (L) and >= (G) type QCP constraints.

    Pls refer: http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.html

    Regards,
    Vivek.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-04T05:46:13Z  
    Hi Marshall,

    The CPXaddqconstr() in C Callable API has support for adding both <= (L) and >= (G) type QCP constraints.

    Pls refer: http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.html

    Regards,
    Vivek.
    Hello, you can refer to this link instead:

    http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r4/index.jsp?topic=%2Filog.odms.cplex.help%2Frefcallablelibrary%2Fhtml%2Ffunctions%2FCPXaddqconstr.html

    Regards,
    Vivek.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-04T13:39:22Z  
    Thanks Vivek! I'll check it out.

    Marshall
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-04T21:17:18Z  
    Hi Paul,

    Are there any NLP solvers that you would recommend to deal with this problem?

    Thanks,

    Marshall
    I have no first-hand experience with nonconvex problems, but you might be interested in https://groups.google.com/forum/?fromgroups=#!topic/knitro/xRZA5kDNaQ8.

    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)
  • Erwin_Kalvelagen
    Erwin_Kalvelagen
    2 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-04T21:44:07Z  
    I have no first-hand experience with nonconvex problems, but you might be interested in https://groups.google.com/forum/?fromgroups=#!topic/knitro/xRZA5kDNaQ8.

    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)
    GloMIQO by Floudas e.a. (http://helios.princeton.edu/GloMIQO/) may be another candidate for this type of problem.

    Erwin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-05T13:57:25Z  
    GloMIQO by Floudas e.a. (http://helios.princeton.edu/GloMIQO/) may be another candidate for this type of problem.

    Erwin
    Thanks!
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-02-20T18:34:06Z  
    Hi,

    I did try to simply change the sign of the inequality in CPXaddqconstr. As a number of you suggested, this did not resolve the problem (the constraint was still not positive semi-definite). I will try some of the other solvers that were suggested.

    Thanks very much for all the help!

    Marshall
  • EdKlotz
    EdKlotz
    244 Posts

    Re: positive semi-definite quadratic constraint problem

    ‏2013-02-20T23:55:38Z  
    Hi,

    I did try to simply change the sign of the inequality in CPXaddqconstr. As a number of you suggested, this did not resolve the problem (the constraint was still not positive semi-definite). I will try some of the other solvers that were suggested.

    Thanks very much for all the help!

    Marshall
    > YPT9_Marshall_Sussman wrote:
    > Hi,
    >
    > I did try to simply change the sign of the inequality in CPXaddqconstr. As a number of you suggested, this did not resolve the problem (the constraint was still not positive semi-definite). I will try some of the other solvers that were suggested.
    >
    > Thanks very much for all the help!
    >
    > Marshall
    Regarding more general nonlinear solvers, I have found the solvers section of the GAMS web site to contain quite a bit of useful information on a variety of solvers. The descriptions there may help you assess which solver would work well on your particular type of problem. The URL is http://www.gams.com/solvers/index.htm.

    Regarding CPLEX, there are a couple of things you could try.

    1) Given that Q is positive semi definite, you know that Q can be represented as
    L'L (i.e. Q has a Cholesky factorization. You could then add the linear constraints
    y - Lx = 0 and replace x'Qx with y'y in your quadratic constraint. You now have a
    separable quadratic expression that you can approximate with piecewise linear functions. CPLEX supports that. However, this reformulation increases the problem
    size significantly, adding the y - Lx = 0 constraints and introducing variables for
    piecewise linear term for each element of the y vector of variables. So, this may
    run slower than just using a good nonlinear solver.

    2) Your problem is not convex, but it involves a special type of nonconvexity that
    you might be able to address via some fairly simple discrete constraints. Let's
    have a look at the simplest case, namely a single variable, and Q is the identity
    matrix:

    bx - x^2 <= r
    x^2 - bx >= -r // multiply by -1
    (x - b/2)^2 >= (b^2)/4 - r // complete the square

    How, we have two data dependent cases to consider:

    a) if (b^2)/4 - r <= 0, the constraint

    (x - b/2)^2 >= (b^2)/4 - r

    always holds. Hence, your equivalent original constraint bx - x^2 <= r
    also always holds. In that case, you can just remove this constraint and solve
    the rest of your quadratic program.

    b) if (b^2)/4 - r > 0, the constraint

    (x - b/2)^2 >= (b^2)/4 - r

    holds if

    x - b/2 >= sqrt ((b^2)/4 - r) or
    x - b/2 <= -sqrt ((b^2)/4 - r)

    CPLEX supports modeling of this type of disjunctive constraint, so in this
    case you can replace your quadratic constraint and solve the model as a MIQP
    instead of a nonconvex QCP.

    Now, that handles the simplest case, but I believe this extends to a
    Q matrix of arbitrary dimension. Specifically, I have found the attached
    pdf by R Clark Robinson of Northwestern very useful regarding positive definiteness
    in general, and it also discusses completing the square for Q matrices of arbitrary
    size. So, you could probably complete the square for x'Qx - b'x, then formulate
    similar linear disjunctive constraints, and solve the resulting MIQP. I'm not
    sure this would work better than a well chosen nonlinear solver, but it might
    be interesting to compare.

    Attachments