Как решить LCP (линейная проблема дополнительности) в Python?

Question

Есть ли хорошая библиотека для численного решения LCP в python?

Редактировать: Мне нужен пример работающего кода Python, потому что большинство библиотек, кажется, решают только квадратичные задачи, и у меня возникают проблемы с преобразованием LCP в QP.

Answer 1

Для квадратичного программирования на 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.

Answer 2

Взгляните на scikit OpenOpt . У него есть пример выполнения квадратичного программирования , и я считаю, что это выходит за рамки процедур оптимизации SciPy. NumPy требуется для использования OpenOpt. Я считаю, что страница википедии, на которую вы указали нам для LCP, описывает, как решить LCP с помощью QP.

Answer 3

Наилучшим алгоритмом для решения MCP (смешанных нелинейных задач дополнительности, более общих, чем LCP) является решатель PATH: http://pages.cs.wisc.edu/~ferris/path.html

Решатель PATH доступен в Matlab и GAMS. Оба идут с Python API. Я решил использовать GAMS, потому что есть бесплатная версия. Итак, вот пошаговое решение для решения LCP с помощью Python API GAMS. Я использовал Python 3.6:

1. Загрузите и установите GAMS: https://www.gams.com/download/

2. Установите API для Python, как здесь: https://www.gams.com/latest/docs/API_PY_TUTORIAL.html Я использовал conda, изменил каталог, в котором были файлы python 3.6, и ввел

   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)
   

Answer 4

В OpenOpt есть бесплатный решатель LCP, написанный на Python + NumPy, см. http://openopt.org/LCP