scipy.optimize.linprog無法找到解決方案

我試圖檢查數據是否可線性分離。我正在使用這個link中提到的方程式。我在Python中使用Scipy包的linprg函數。是陣列的尺寸如下：scipy.optimize.linprog無法找到解決方案

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次迭代之後，它不能找到解決方案，也沒有說解決方案不存在。那麼，這是否意味着解決方案不存在？或者我應該增加迭代限制，如果是，那麼增加多少？

來源

2017-08-25 V K

在Nocedal和Wright的書「數值優化」中，作者聲稱：「[單純形法]方法一般最多需要2m到3m的迭代，其中m是約束矩陣的行維數」。（這是關於典型行爲的評論，而不是最壞的情況。）您有超過12000個約束，因此需要超過25000次迭代並非意料之外。 –

@WarrenWeckesser還有其他更快的Python庫嗎？ –

我沒有比[google建議]（https://www.google.com/search?q=python+linear+programming&ie=utf-8&oe=utf-8）更好的建議。 scipy的1.0.0版本將實現內部點方法，但尚未發佈。 –

如果您信任解算器（=實施質量），請增加迭代限制，直到出現其他退出狀態。

好的實現將始終在有限的時間內結束，這意味着：退出狀態將在某個迭代大小處發生變化。將有解決方案或一些證書無界限或不可行性。

編輯：以上結果僅限於單純形法（質量實現）的實現！ Interior-point methods表現不同，並且通常沒有一個基礎理論來強有力地提供這些證書（理論一般假設問題是可行的），例外是使用均勻自對偶嵌入（An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm）。一般而言，Simplex算法通常會使用相當多的迭代（至少與內點方法相比，我不會評論你的例子）。

來源

2017-08-25 14:44:06 sascha

scipy.optimize.linprog無法找到解決方案

回答

相關問題