Gurobi报错Objective Q非PSD(负对角元) 优化模型求解求助

错误含义 #

Gurobi 10.0.1: Error: Objective Q not PSD (negative diagonal entry) 表示Gurobi检测到目标函数中的二次项构成的Q矩阵不满足半正定（PSD）条件，且存在负对角元素。半正定矩阵要求所有特征值非负，负对角元素直接违反这一要求，导致求解器无法处理该二次结构。

问题定位 #

你的模型中存在三次非线性项（整数变量q[i,j]与二元变量x[k,j]、w[k,l]的乘积，例如q[i,j] * x[k,j] * w[k,l] * t_lav_mo[l,i,k,j]），Gurobi会尝试自动将高次项转化为二次项，但这种自动转化可能生成包含负对角元素的Q矩阵，进而触发报错。

你尝试设置nonconvex=2无效的原因是：该参数仅支持处理非凸二次规划（QP）或混合整数二次规划（MIQP），对三次及以上的非线性项无法生效，自动转化后的结构超出了非凸QP的处理范围。

解决方法 #

1. 显式线性化高次乘积项 #

将所有三次项拆解为线性约束下的低次项替换，这是最稳妥的方案：

• 步骤1：线性化二元变量乘积x[k,j] * w[k,l]
  引入新的二元变量z[k,j,l]，添加约束：

  var z {K,J,L} binary;
  subject to z_upper1 {k in K,j in J,l in L}: z[k,j,l] <= x[k,j];
  subject to z_upper2 {k in K,j in J,l in L}: z[k,j,l] <= w[k,l];
  subject to z_lower {k in K,j in J,l in L}: z[k,j,l] >= x[k,j] + w[k,l] - 1;
  

  替换原模型中所有x[k,j] * w[k,l]为z[k,j,l]。

• 步骤2：线性化整数-二元变量乘积q[i,j] * z[k,j,l]
  引入新的整数变量y[i,j,k,l]，并为q[i,j]设置上界U[i,j]（可取V[i]，因为sum{j in J} q[i,j] = V[i]），添加约束：

  var y {I,J,K,L} integer >=0;
  param U {I} = V[I];  # q[i,j]的上界
  subject to y_upper {i in I,j in J,k in K,l in L}: y[i,j,k,l] <= U[i] * z[k,j,l];
  subject to y_lower1 {i in I,j in J,k in K,l in L}: y[i,j,k,l] >= 0 * z[k,j,l];
  subject to y_lower2 {i in I,j in J,k in K,l in L}: y[i,j,k,l] <= q[i,j];
  subject to y_lower3 {i in I,j in J,k in K,l in L}: y[i,j,k,l] >= q[i,j] - U[i] * (1 - z[k,j,l]);
  

  替换原模型中所有q[i,j] * z[k,j,l]为y[i,j,k,l]。

  线性化后，模型所有项均为线性，Gurobi可直接处理，不会再触发Q矩阵相关报错。

2. 若保留非线性项的替代方案 #

如果不进行线性化，需确保模型仅包含二次项（无三次及以上项），并正确设置Gurobi参数：

• 确认所有非线性项均为二次项（变量的两两乘积）
• 在AMPL中设置参数：

  option gurobi_options 'nonconvex=2 Method=2';
  

  Method=2指定使用分支定界算法处理非凸MIQP问题，但此方案仅适用于纯二次结构的模型，对三次项无效。

原模型代码 #

set J:= 1..n; 

param m;
set K:= 1..m; 

param p;
set I:= 1..p; 

param f;
set L:= 1..f;  

var x {K, J} binary; 
var w {K, L} binary; 
var q {I, J} integer >=0; 

param V {I} >=0;  
param D {J} >=0;  
param M {J} >=0;  
param a {I, L} binary;  
param b {J, L} binary;   
param g {K, L} binary;  
param t_lav_ord {L, I, J} >=0; 
param t_op {I, J} >=0;  
param t_lav_mo {L, I, K, J} >=0; 
param t_setup {K, J} >=0; 
param Cu {I, J, L} >=0; 
param C {K} >=0; 
param Cu_mod {I, J, K, L} >=0; 

#funzioni obiettivo
minimize time: (sum{j in J, l in L, k in K, i in I} q[i, j] * (t_op[i, j] + a[i, l] * x[k, j] * w[k, l]     * t_lav_mo[l, i, k, j] + (1- x[k, j]) * a[i, l] * t_lav_ord[l, i, j])) + (sum{k in K, j in J} x[k, j] * t_setup[k, j]) ;
minimize cost: (sum {j in J, k in K} x[k, j] * C[k]) + (sum { j in J, k in K, i in I, l in L} q[i, j] *   a[i,l] * (x[k, j] * w[k, l] * Cu_mod[i, j, k, l] + (1 - x[k, j]) * Cu[i, j, l])) ;

#vincoli
subject to volume {i in I, l in L}: sum{j in J} q[i, j] = V[i] ;
subject to Nmax_mod {j in J}: sum{k in K} x[k, j]<= M[j] ;
subject to lav_modulo {k in K, l in L}: w[k, l]<= g[k, l] ;
subject to ass_lav_macchina_modulo {i in I, l in L}: sum{j in J} (b[j, l] + sum{k in K} w[k, l] * x[k, j]) >= a[i,l] ;
subject to ass_disp {j in J}: sum {l in L, k in K, i in I} (q[i, j] * (t_op[i, j] + a[i, l] * x[k, j] *  w[k, l] * t_lav_mo[l, i, k, j] + (1- x[k, j]) * a[i, l] * t_lav_ord[l, i, j])) + (sum{k in K} x[k, j] *  t_setup[k, j]) <= D[j] ;

内容的提问来源于stack exchange，提问作者sara menegato