10

mosek 优化器里处理优化问题的无解情况

 3 years ago
source link: https://zhiqiang.org/math/mosek-handle-infeasible-solution.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

mosek 优化器里处理优化问题的无解情况

作者: 张志强

, 发表于 2020-09-29

, 共 2425 字 , 共阅读 242 次

线性或二次优化经常会碰到无解情况。一个典型的线性或二次优化问题如下：

maxwαws.t.lw≤w≤uwlC≤Cw≤uCw∈Q(1)(1)maxwαws.t.lw≤w≤uwlC≤Cw≤uCw∈Q

除了数据精度等问题外， MOSEK 优化器会提示下面几种无解情况：

  • PRIME INFEASIBLE
  • DUAL INFEASIBLE

当然有时候两个都 INFEASIBLE。其中 PRIME INFEASIBULE 主要是指限制条件互相冲突了，没有可行解。DUAL INFEASIBLE 是指对偶形式的限制条件。

DUAL INFEASIBLE 通常表明在给定限制条件下，目标函数的方向反了，最优值可能是无穷大。这种情况在日常中不太容易出现（一般是max和min写反了）。我们最常见需要解决的是 PRIME INFEASIBLE ，也就是找出那些冲突的限制条件。下面以 C++为例（ Python 估计更简单）：

第一步：在代码里导出问题到文件

model->writeTask("./dump.opf");

第二步：在命令行运行诊断命令

mosek dump.opf --infrepo -d MSK_IPAR_INFEAS_REPORT_AUTO 1 -q mose.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.

avatar-0.jpg
avatar-4.jpg
无名1418
2021-02-09

支持，希望能继续写下去


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK