python - Linprog 可以解决 LP 原始问题但不能解决对偶问题？

Question

我能够使用矩阵 A_ub 用 scipy linprog 解决以下最小化问题：

A_ub = [[ 1 10  0  3]
        [ 6  2  3  6]
        [ 3  5  4  2]
        [ 4  9  2  2]]

和

b_ub = [1,1,1,1]

最小化问题是c = [-1,-1,-1,-1]（即范数1的负数）。从 scipy 调用 linprog 会得到以下结果（如预期的那样）：

scipy.optimize.linprog(c, A_ub=A_ub, b_ub=b_ub)

    con: array([], dtype=float64)
     fun: -0.2777777777777778
 message: 'Optimization terminated successfully.'
     nit: 7
   slack: array([0.83333333, 0.        , 0.        , 0.44444444])
  status: 0
 success: True
       x: array([0.        , 0.        , 0.22222222, 0.05555556])

但是，我还需要找到对偶问题的解决方案。

根据我对极小极大定理的理解，上述问题等价于：

scipy.optimize.linprog(-b_ub, A_ub=A_ub.T, b_ub=c)

但是，运行这样的命令会导致错误：

     con: array([], dtype=float64)
     fun: 0.0
 message: "Phase 1 of the simplex method failed to find a feasible solution. The pseudo-objective function evaluates to 4.0e+00 which exceeds the required tolerance of 1e-12 for a solution to be considered 'close enough' to zero to be a basic solution. Consider increasing the tolerance to be greater than 4.0e+00. If this tolerance is unacceptably  large the problem may be infeasible."
     nit: 0
   slack: array([-1., -1., -1., -1.])
  status: 2
 success: False
   x: array([0., 0., 0., 0.])

如果我将容差增加到一个较大的值 (10)，那么它会以一个解决方案终止，但我认为它不正确，因为函数值与原始值不同。我非常感谢有关此问题以及如何找到双重解决方案的任何帮助和提示。

最好的，Hieu。

标签： pythonoptimizationscipy

Answer 1

我在调用 linprog 时犯了一个错误，

问题的双重性应该是：

minimizing b_ub
s.t
-A_transpose *x <= c

因此，如果我使用 linprog 调用将起作用：

linprog(b_ub, -A_transpose, c)