整数線形最小2乗

Question

したがって最小になるxを見つけなければならないnorm(A.dot(x) - y, 2) Aは行列であり、yはベクトルです。

これはscipy.optimize.lsq_linearまたはnumpy.linalg.lstsqで簡単に実行できますが、xは整数でなければなりません。一般に、「整数プログラミング」はNP完全である。 私はRoutines for solving the standard integer least squares problemを見つけましたが、私はmatlabから変換する前に尋ねると思いました。

Pythonの整数線形最小二乗を解くことができる確立されたライブラリはありますか？

Answer 1

Pythonで使用できる最適化ライブラリの1つを、（混在した）整数プログラミングよりも使用できます。ゴーグル検索を行い、多くを見つけるでしょう。あなたの問題は凸であるので、cvxpyはそれらの多くの素晴らしいインターフェースとして使用できます。 |ここで私は、関連するソリューション解決合計と思いついたの（大規模な問題のために、非常に効率的ではないかもしれない）内蔵の整数計画ソルバー

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.]] 

Answer 2

を（使用したおもちゃの例です。 Ax-y |）は、線形整数計画問題に変換し、PuLPを使って解くことができます。

基本的な考え方は、制約（ERR（i））を被験者目的関数の和を最小化することである： - Y（I）< = ERR（i）およびアックス（I）

アックス（I） - y（i）> = -err（i）となる。

これは線形ソルバと互換性があります。