python - 如何解决python中的LCP(线性互补问题)？

Question

是否有一个很好的库来对 LCP 进行数值求解在 python 中？

编辑:我需要一个有效的 Python 代码示例，因为大多数库似乎只解决二次问题，而我在将 LCP 转换为 QP 时遇到问题。

Answer 1

对于使用 Python 的二次规划，我使用 qp - 来自 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 更好的解决方案。