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

作者: , 共 2865 字 , 共阅读 0

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

$$\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 通常表明在给定限制条件下,目标函数的方向反了,最优值可能是无穷大。这种情况在日常中不太容易出现(一般是maxmin写反了)。我们最常见需要解决的是 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.

类似文章:
C++对一个有序序列[first, last)firstlast都是iterator,可简单理解为位置指针),以及指定值v,标准库直接提供二分查找的函数std::lower_boundstd::upper_bould
最近看了几个风险管理和组合管理系统,有几个系统里附带了组合优化模块,也了解到这一方面工业界的最新成果。最新的组合优化模块被称为第二代最优化模型,主要成果就是二阶锥优化算法的应用,其中一个重要的改进为对 alpha 估计的不准确性考虑在内。
箭扣最精华的一段,从涧口,途径天梯、鹰飞倒仰、北京结,到西大墙西山。全程接近 9 公里,爬升 550 米。路程和爬升都不大,但路极其艰险。
编程 » popen, C++
我们在 C++里可以这么查看popen是否正常执行: