如何解決python中的LCP（線性互補問題）？

Question

有沒有一個好的庫來數值解決python中的LCP？

編輯：我需要一個工作python代碼的例子，因爲大多數庫似乎只解決二次問題，我有轉換LCP成QP問題。

Answer 1

對於Python的二次編程，我使用qp -solver來自cvxopt（source）。利用這一點，將LCP問題轉化爲QP問題很簡單（參見Wikipedia）。例如：

from cvxopt import matrix, spmatrix 
from cvxopt.blas import gemv 
from cvxopt.solvers import qp 

def append_matrix_at_bottom(A, B): 
    l = [] 
    for x in xrange(A.size[1]): 
     for i in xrange(A.size[0]): 
      l.append(A[i+x*A.size[0]]) 
     for i in xrange(B.size[0]): 
      l.append(B[i+x*B.size[0]]) 
    return matrix(l,(A.size[0]+B.size[0],A.size[1])) 

M = matrix([[ 4.0, 6, -4, 1.0 ], 
      [ 6, 1, 1.0 2.0 ], 
      [-4, 1.0, 2.5, -2.0 ], 
      [ 1.0, 2.0, -2.0, 1.0 ]]) 
q = matrix([12, -10, -7.0, 3]) 

I = spmatrix(1.0, range(M.size[0]), range(M.size[1])) 
G = append_matrix_at_bottom(-M, -I) # inequality constraint G z <= h 
h = matrix([x for x in q] + [0.0 for _x in range(M.size[0])]) 

sol = qp(2.0 * M, q, G, h)  # find z, w, so that w = M z + q 
if sol['status'] == 'optimal': 
    z = sol['x'] 
    w = matrix(q) 
    gemv(M, z, w, alpha=1.0, beta=1.0) # w = M z + q 
    print(z) 
    print(w) 
else: 
    print('failed') 

請注意：

• 代碼沒有經過測試的，請仔細檢查;
• 確實有比將LCP轉換成QP更好的解決方法。

Answer 2

看看scikit OpenOpt。它有一個做quadratic programming的例子，我相信它超越了SciPy的優化例程。 NumPy需要使用OpenOpt。我相信您爲LCP指出的維基百科頁面描述瞭如何通過QP解決LCP問題。

Answer 3

OpenOpt有一個免費的LCP求解用Python編寫的+ NumPy的看到http://openopt.org/LCP

Answer 4

解決的MCP（混合非線性互補問題，比LCP更一般的）最好的算法是路徑求解：http://pages.cs.wisc.edu/~ferris/path.html

PATH求解器可在matlab和GAMS中使用。兩者都有一個Python API。我選擇使用GAMS，因爲它有免費版本。所以這裏是一步一步的解決方案，用GAMS的python API來解決LCP問題。我用python的3.6：

1. 下載並安裝GAMS：https://www.gams.com/download/

2. 安裝API到Python喜歡這裏：https://www.gams.com/latest/docs/API_PY_TUTORIAL.html 我用暢達，改變了蟒蛇3.6的apifiles是目錄並進入

   python setup.py install 
   

3. 創建.gms文件（文件GAMS）lcp_for_py.gms含有：

   sets i; 
   
   alias(i,j); 
   
   parameters m(i,i),b(i); 
   
   $gdxin lcp_input 
   $load i m b 
   $gdxin 
   
   positive variables z(i); 
   
   equations Linear(i); 
   
   Linear(i).. sum(j,m(i,j)*z(j)) + b(i) =g= 0; 
   
   model lcp linear complementarity problem/Linear.z/; 
   
   options mcp = path; 
   
   solve lcp using mcp; 
   
   display z.L; 
   

4. Python代碼是這樣的：

   import gams 
   
   #Set working directory, GamsWorkspace and the Database 
   worDir = "<THE PATH WHERE YOU STORED YOUR .GMS-FILE>" #"C:\documents\gams\" 
   ws=gams.GamsWorkspace(working_directory=worDir) 
   db=ws.add_database(database_name="lcp_input") 
   
   #Set the matrix and the vector of the LCP as lists 
   matrix = [[1,1],[2,1]] 
   vector = [0,-2] 
   
   #Create the Gams Set 
   index = [] 
   for k in range(0,len(matrix)): 
   index.append("i"+str(k+1)) 
   
   i = db.add_set("i",1,"number of decision variables") 
   for k in index: 
       i.add_record(k) 
   
   #Create a Gams Parameter named m and add records 
   m = db.add_parameter_dc("m", [i,i], "matrix of the lcp") 
   for k in range(0,len(matrix)): 
       for l in range(0,len(matrix[0])): 
        m.add_record([index[k],index[l]]).value = matrix[k][l] 
   
   #Create a Gams Parameter named b and add records 
   b = db.add_parameter_dc("b",[i],"bias of quadratics") 
   for k in range(0, len(vector)): 
       b.add_record(index[k]).value = vector[k] 
   
   #run the GamsJob using the Gams File and the database 
   lcp = ws.add_job_from_file("lcp_for_py.gms") 
   lcp.run(databases = db) 
   
   #Save the solution as a list an print it 
   z = [] 
   for rec in lcp.out_db["z"]: 
       z.append(rec.level) 
   
   print(z)