Skip to main content

Q matrix is not positive semi-definite when dealing with a cone

Answered

Comments

4 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Jaromił Najman
    • Gurobi Staff

    Could you please use the write method to write your model to a human-readable LP file and share the output for the particular cone constraint?

    In Python the call to the write method would look similar to

    model.write("myModel.lp")

    You can open the \(\texttt{myModel.lp}\) file with any standard text editor.

    0
  • Abe Stark
    • Gurobi-versary
    • First Comment
    • First Question

    Thank you very much for your response! The content in the .lp is as follows:

    Minimize
      10470 y[0] + 8810 y[1] + 214.3209 w[0,0] + 165.7161 w[0,1]
       + 244.9449 w[0,2] + 198.3543 w[1,0] + 174.5568 w[1,1] + 233.3727 w[1,2]
    Subject To
     power: 10470 y[0] + 8810 y[1] <= 300000
     capacity: 104.7 y[0] + 88.1 y[1] >= 60.71
     consider[0]: x[0,0] + x[1,0] <= 1
     consider[1]: x[0,1] + x[1,1] <= 1
     consider[2]: x[0,2] + x[1,2] <= 1
     qcp[0,0]: [ - 10.47 x[0,0] ^2 + 10.47 x[0,0] * w[0,0]
       + 9.69 x[1,0] * w[0,0] ] >= 0
     qcp[0,1]: [ - 8.81 x[0,1] ^2 + 8.81 x[0,1] * w[0,1] + 9.28 x[1,1] * w[0,1]
       ] >= 0
     qcp[0,2]: [ - 11.43 x[0,2] ^2 + 11.43 x[0,2] * w[0,2]
       + 10.89 x[1,2] * w[0,2] ] >= 0
     qcp[1,0]: [ 10.47 x[0,0] * w[1,0] - 9.69 x[1,0] ^2 + 9.69 x[1,0] * w[1,0]
       ] >= 0
     qcp[1,1]: [ 8.81 x[0,1] * w[1,1] - 9.28 x[1,1] ^2 + 9.28 x[1,1] * w[1,1] ]
       >= 0
     qcp[1,2]: [ 11.43 x[0,2] * w[1,2] - 10.89 x[1,2] ^2
       + 10.89 x[1,2] * w[1,2] ] >= 0
    Bounds
     x[0,0] <= 1
     x[0,1] <= 1
     x[0,2] <= 1
     x[1,0] <= 1
     x[1,1] <= 1
     x[1,2] <= 1
    Binaries
     y[0] y[1]
    End

    If I set x as binary, then it can be solved. 

    0
  • Jaromił Najman
    • Gurobi Staff

    Hi Abe,

    None of the quadratic constraints is convex. The respective \(Q\) matrices of the quadratic inequalities have positive and negative eigenvalues. Let's take \(\texttt{qcp[0,0]}\) as an example. The \(Q\) matrix is a \(3\times 3\) matrix as the constraint has 3 variables \(x_{0,0},x_{1,0},w_{0,0}\)and is given as

    \[\begin{align*}
    \begin{pmatrix} -10.47 & 0 & 5.235 \\ 0 & 0 & 4.845 \\ 5.235 & 4.845 & 0 \end{pmatrix}
    \end{align*}\]

    The eigenvalues of the above matrix are \(\lambda_1 \approx -12.9, \lambda_2 \approx 5.76, \lambda_3 \approx -3.29\). Consequently, constraint \(\texttt{qcp[0,0]}\) is not convex (and not a cone, cf. definition of rotated second order cone).

    Best regards, 
    Jaromił

     

     

    1

Post is closed for comments.