线性或二次优化经常会碰到无解情况。一个典型的线性或二次优化问题如下:
$$\begin{array}{rl} \max_w & \alpha w \\ s.t. & \\ & l_w \leq w \leq u_w \\ & l_C \leq Cw \leq u_C \\ & w \in Q \end{array}$$
除了数据精度等问题外, MOSEK 优化器会提示下面几种无解情况:
- PRIME INFEASIBLE
- DUAL INFEASIBLE
当然有时候两个都 INFEASIBLE。其中 PRIME INFEASIBULE 主要是指限制条件互相冲突了,没有可行解。DUAL INFEASIBLE 是指对偶形式的限制条件。
DUAL INFEASIBLE 通常表明在给定限制条件下,目标函数的方向反了,最优值可能是无穷大。这种情况在日常中不太容易出现(一般是max
和min
写反了)。我们最常见需要解决的是 PRIME INFEASIBLE ,也就是找出那些冲突的限制条件。下面以 C++为例( Python 估计更简单):
第一步:在 C++代码里导出问题到文件
model->writeTask("./dump.opf");
如果是在 Python 中:
with Model("your problem") as model:
# your problem, variables and conditions
model.writeTask("./dump.pdf")
第二步:在命令行运行诊断命令
mosek dump.opf --infrepo -d MSK_IPAR_INFEAS_REPORT_AUTO 1 -q mose.log
如果提示找不到 mosek 或无输出,将mosek
的路径写全,
/opt/3rd/mosek/9.2/tools/platform/linux64x86/bin/mosek dump.opf --infrepo -d MSK_IPAR_INFEAS_REPORT_AUTO 1 -q mosek.log
然后在mosek.log
里可以看哪些条件不满足,类似于下面这个:
MOSEK PRIMAL INFEASIBILITY REPORT.
Problem status: The problem is primal infeasible
The following constraints are involved in the primal infeasibility.
Index Name Lower bound Upper bound Dual lower Dual upper
5229 condition[2] unimportant 1.000000e-02 -0.000000e+00 -1.000000e+00
The following bound constraints are involved in the infeasibility.
Index Name Lower bound Upper bound Dual lower Dual upper Dual cone
4 weights[3] -1.728642e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
8 weights[7] -1.561579e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
22 weights[21] -1.350838e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
24 weights[23] -1.430027e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
31 weights[30] -4.973163e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
65 weights[64] 9.658339e-06 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
66 weights[65] 1.240400e-06 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
68 weights[67] 6.213882e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
69 weights[68] -1.487085e-03 unimportant -1.000000e+00 -0.000000e+00 -0.000000e+00
比如上面提到是condition
的第二行无法满足,对应的冲突限制条件也列出来了。dump.opf
里可以查到condition[2]
的表达式,它是那些weights
之和。这里的冲突很简单,就是weights
都给了下界,加起来也会有一个下界,而这个下界超出了condition[2]
约定的的上界,从而引发一个冲突。
Q. E. D.