Как решить LCP (линейная проблема взаимозависимости) в Python?
Существует ли хорошая библиотека к numericly, решают LCP в Python?
Править: Мне нужен рабочий пример кода Python, потому что большинство библиотек, кажется, только решает квадратичные проблемы, и у меня есть проблемы при преобразовании LCP в QP.
2 ответа
Для квадратичного программирования на Python я использую qp -сольвер из cvxopt ( источник ). Используя это, легко перевести проблему 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.
Взгляните на scikit OpenOpt . В нем есть пример выполнения квадратичного программирования , и я считаю, что он выходит за рамки процедур оптимизации SciPy. NumPy требуется для использования OpenOpt. Я считаю, что страница википедии, на которую вы указали нам для LCP, описывает, как решить LCP с помощью QP.