Python'da bir LCP (doğrusal tamamlayıcılık sorunu) nasıl çözülür?

Question

Python'da LCP sayısal olarak çözmek için iyi bir kütüphane var mı?

Düzenleme: Çalışan bir python kod örneğine ihtiyacım var çünkü çoğu kütüphanede sadece karesel sorunları çözüyor gibi görünüyor ve bir LCP'yi QP'ye dönüştürmede sorun yaşıyorum.

Answer 1

Python ile ikinci dereceden programlama için, cvxopt (source) adresinden -solver kullanıyorum. Bunu kullanarak, LCP problemini bir QP problemine çevirmek basittir (bakınız Wikipedia). Örnek:

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') 

unutmayın:

• kod dikkatlice tamamen denenmemiş kontrol ediniz edilir;
• kesinlikle LCP'yi QP'ye dönüştürmekten daha iyi çözüm teknikleri vardır. http://pages.cs.wisc.edu/~ferris/path.html

  :

Answer 2

Sitakit OpenOpt'a bakın. Bu, quadratic programming yapmanın bir örneğine sahiptir ve bunun SciPy'nin optimizasyon rutinlerinin ötesine geçtiğine inanıyorum. OpenOpt kullanmak için NumPy gereklidir. Bizi LCP için işaret ettiğiniz wikipedia sayfasının QP tarafından nasıl bir LCP'nin çözüleceğini açıkladığına inanıyorum.

Answer 3

OpenOpt YOLU çözücüsü çözücü http://openopt.org/LCP

Answer 4

(LCP daha genel karışık doğrusal olmayan tamamlayıcılık sorunları,) MCPS çözmek için en iyi algoritma bkz Python + numpy yazılmış ücretsiz LCP edilir vardır PATH çözücüsü matlab ve GAMS'de kullanılabilir. Her ikisi de bir python API'si ile geliyor. GAMS'yi kullanmayı seçtim çünkü ücretsiz bir sürüm var. İşte burada bir LCP'yi GAMS'nin python API'si ile çözmek için adım adım bir adımdır. , https://www.gams.com/latest/docs/API_PY_TUTORIAL.html kullandığım Conda piton 3.6 apifiles edildi dizini değişti ve girilen: https://www.gams.com/download/

buradaki gibi python için API yükleyin:

1. indirin ve yükleyin GAMS: Ben piton 3.6 kullanılmış içeren

   python setup.py install 
   

2. bir .gms-dosya (GAMS dosyası) oluşturun 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; 
   

3. Sizin piton kodu şu şekildedir:

   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)