Topic
12 replies Latest Post - ‏2013-02-20T23:55:38Z by EdKlotz
SystemAdmin
SystemAdmin
7944 Posts
ACCEPTED ANSWER

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
    7944 Posts
    ACCEPTED ANSWER

    Re: positive semi-definite quadratic constraint problem

    ‏2013-01-03T17:02:21Z  in response to SystemAdmin
    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
      7944 Posts
      ACCEPTED ANSWER

      Re: positive semi-definite quadratic constraint problem

      ‏2013-01-03T20:56:01Z  in response to SystemAdmin
      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
    7944 Posts
    ACCEPTED ANSWER

    Re: positive semi-definite quadratic constraint problem

    ‏2013-02-20T18:34:06Z  in response to SystemAdmin
    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
      214 Posts
      ACCEPTED ANSWER

      Re: positive semi-definite quadratic constraint problem

      ‏2013-02-20T23:55:38Z  in response to SystemAdmin
      > 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