scipy.optimize.linprog 找不到解决方案

Question

我正在尝试检查数据是否线性可分。为此，我正在使用 link 中提到的等式。我在 python 中使用 Scipy 包的 linprg 函数。数组大小如下：

A = [12137810,11]
A1 = [12137,11]
b = 12137
c = 11

这是我使用的代码：

try:
        import os
        import random
        import traceback
        import numpy as np
        import scipy.io as sio
        from scipy.optimize import linprog
        os.system('cls')
        dicA  = sio.loadmat('A.mat')
        A = dicA.get('A')
        lengthA = int(len(A)/1000)
        aRange = range(0,lengthA)
        selectedIndexes = random.sample(aRange,lengthA)
        A1 = A[selectedIndexes]
        print('a = [',len(A),',',len(A[0]),']')
        print('a1 = [',len(A1),',',len(A1[0]),']')
        del A
        b = -1*np.ones(len(A1),np.int64)
        c = np.zeros(11,np.int64)
        print('c = ',len(c))
        print('b =',len(b))
        del dicA
        res = linprog(c, A_ub=A1, b_ub=b, bounds=(None,None),options={"disp": True,"maxiter": 25000})
        print(res)
except:
        print('exception')
        tb = traceback.format_exc()
        print(tb)
finally:

        print('reached finally')

这是我得到的输出：

Iteration limit reached.
fun: -0.0  message: 'Iteration limit reached.'
nit: 25000   status: 1  success: False
x: nan reached finally

所以，2500次迭代后，还是找不到解，也没有说没有解exist.So，那是不是解不存在呢？或者我应该增加迭代限制，如果是，那么增加多少？

Answer 1

如果您信任求解器（=实施质量），请增加迭代限制，直到出现其他退出状态。

一个好的实现总是在有限的时间内结束，这意味着：退出状态将在某个迭代大小 上改变。对于无界性或不可行性，将会有一个解决方案或一些证明。

编辑： 以上后果仅限于单纯形法的实施（质量实施）！ Interior-point methods behave differently and do not have an underlying theory in general to provide these certificates robustly (theory in general assumes that the problem is feasible), the exception beeing the ones using a homogeneous self-dual embedding (An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm).

众所周知，单纯形算法一般会使用相当多的迭代（至少与内点方法相比；我不会评判你的例子）。

scipy.optimize.linprog 找不到解决方案

scipy.optimize.linprog not able to find solution

python

scipy

linear-programming