如何解决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)