Q matrix is not positive semi-definite when dealing with a cone
回答済みIn 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?
-
-
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 -
-
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 -
サインインしてコメントを残してください。
コメント
3件のコメント