如何在Python中解决LCP（线性互补问题）？

9 投票

4 回答

4629 浏览

数据工程师

提问于 2025-04-15 18:42

有没有什么好的库可以在Python中数值求解一个线性互补问题？

补充：我需要一个能运行的Python代码示例，因为大多数库似乎只解决二次问题，而我在把线性互补问题转换成二次问题时遇到了困难。

优化算法数值求解数学建模计算库线性互补问题二次问题

4 个回答

解决混合非线性互补问题（MCPs，包含更一般的线性互补问题LCP）的最佳算法是PATH求解器：http://pages.cs.wisc.edu/~ferris/path.html

PATH求解器可以在matlab和GAMS中使用。这两个工具都有Python的接口。我选择使用GAMS，因为它有免费的版本。下面是使用GAMS的Python接口一步步解决LCP的过程。我使用的是Python 3.6：

下载并安装GAMS：https://www.gams.com/download/
按照这里的说明将API安装到Python中：https://www.gams.com/latest/docs/API_PY_TUTORIAL.html 我使用了conda，切换到Python 3.6的API文件所在目录，然后输入
```
python setup.py install
```

创建一个.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;

你的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)

回答于 2025-04-15 由 Python大师

分享举报

看看这个叫做 scikit 的 OpenOpt。里面有一个关于如何做二次规划的例子，我觉得它的功能比 SciPy 的优化方法更强大。使用 OpenOpt 需要先安装 NumPy。你提到的维基百科页面里，应该也有讲如何通过二次规划来解决 LCP 的方法。

回答于 2025-04-15 由 Python大师

分享举报

在使用Python进行二次规划时，我使用的是来自cvxopt的qp求解器（源代码）。通过这个工具，可以很简单地把线性互补问题（LCP）转换成二次规划问题（QP），具体可以参考维基百科上的内容。下面是一个例子：

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的方式肯定不是最好的解决方案，还有其他更好的方法。

回答于 2025-04-15 由 Python大师

分享举报

如何在Python中解决LCP（线性互补问题）？

4 个回答

撰写回答