所以我必须找到一个 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中的整数线性最小二乘法?
最佳答案
您可以使用可用于 python 的优化库之一来处理(混合)整数规划。做一个谷歌搜索,你会发现很多。由于您的问题是凸的,cvxpy
可以用作其中许多问题的良好接口(interface)。这是一个使用内置整数规划求解器的玩具示例(对于大规模问题可能效率不高)
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.]]
关于python - 整数线性最小二乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43163682/