Q matrix is not positive semi-definite when dealing with a cone
AnsweredIn my model, there is an item \(\sum_{i \in \mathcal{I}} \sum_{j \in \mathcal{J}} c_{ij} P_{ij} \) in the objective function (minimize) where \(c_{ij} \) is a parameter and \[ P_{ij} = \frac{u_{ij}x_{ij}}{\sum_{i \in \mathcal{I}} u_{ij}x_{ij}} \quad \forall i \in \mathcal{I}, j \in \mathcal{J} \], x is binary variable, \(u > 0\), \( \sum_{i \in \mathcal{I}} u_{ij}x_{ij} >0 \).
\(P_{ij}\) is hard to solve directly so I introduce a continuous variable to convexify it:
\[\begin{align} w_{ij} & \geq \frac{u_{ij}x_{ij}}{\sum_{i \in \mathcal{I}} u_{ij}x_{ij}} \\ w_{ij} \sum_{i \in \mathcal{I}} u_{ij}x_{ij} & \geq u_{ij}x_{ij} \\ w_{ij} \sum_{i \in \mathcal{I}} u_{ij}x_{ij} & \geq u_{ij}x^2_{ij} \end{align} \]
I use \(w_{ij}\) and the last constraint which is a cone, then the problem is successfully solved. Due to the chracteristics of my model, x can be relaxed to a continuous variable. And I set x as a variable between [0,1], gurobi reports an error "GurobiError: Q matrix is not positive semi-definite (PSD)".
I do not know why. Relaxing x to continuous is very import because too many binaries make the solving process very long. Could you kindly help with this?
-
Official comment
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. -
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 -
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]
EndIf I set x as binary, then it can be solved.
0 -
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.
Comments
4 comments