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

Question

是否有一个很好的库可以在python中以数字方式解析LCP？

编辑:我需要一个工作的python代码示例,因为大多数库似乎只解决二次问题,我在将LCP转换为QP时遇到问题.

Answer 1

对于使用 Python 进行二次编程，我使用( sourceqp )中的 -solver 。使用它，可以直接将 LCP 问题转化为 QP 问题（参见维基百科）。例子：cvxopt

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 更好的解决方案技术。