Je dois donc trouver un x qui minimise norm(A.dot(x) - y, 2) A est une matrice et y est un vecteur.

Cela pourrait être facilement accompli avec scipy.optimize.lsq_linear ou numpy.linalg.lstsq mais j'ai besoin que x soit des entiers. En général, la «programmation entière» est NP-complète. J'ai trouvé des Routines pour résoudre le problème des moindres carrés d'entiers standard mais j'ai pensé Je demanderais avant de le convertir de matlab.

Existe-t-il une bibliothèque établie qui peut résoudre les moindres carrés linéaires entiers en python?

2
Jacob 2 avril 2017 à 04:19

2 réponses

Meilleure réponse

Vous pouvez utiliser l'une des bibliothèques d'optimisation disponibles pour python qui peut gérer la programmation d'entiers (mixtes). Faites une recherche sur Google et vous en trouverez plusieurs. Puisque votre problème est convexe, cvxpy peut être utilisé comme une interface agréable pour beaucoup d'entre eux. Voici un exemple de jouet utilisant un solveur de programmation d'entiers intégré (qui peut ne pas être très efficace pour les problèmes à grande échelle)

import numpy as np
import cvxpy

np.random.seed(123) # for reproducability

# generate A and y
m, n = 10, 10
A = np.random.randn(m,n)
y = np.random.randn(m)

# declare the integer-valued optimization variable
x = cvxpy.Int(n)

# set up the L2-norm minimization problem
obj = cvxpy.Minimize(cvxpy.norm(A * x - y, 2))
prob = cvxpy.Problem(obj)

# solve the problem using an appropriate solver
sol = prob.solve(solver = 'ECOS_BB')

# the optimal value of x is 
print(x.value)
[[-13.]
 [ -3.]
 [  3.]
 [  6.]
 [  1.]
 [ -5.]
 [ -1.]
 [ -3.]
 [ -2.]
 [ -6.]]
1
recnac 5 mai 2019 à 12:08

J'ai proposé une solution connexe résolvant la somme (| Ax-y |) que vous pouvez convertir en un problème de programmation d'entiers linéaires et résoudre à l'aide de PuLP.

L'idée de base est de minimiser la somme de la fonction objectif (err (i)) soumise aux contraintes:

Ax (i) - y (i) <= err (i) et Ax (i) - y (i)> = -err (i).

Qui est compatible avec les solveurs linéaires.

0
Eric Aya 20 oct. 2017 à 09:41