python - 整数线性最小二乘法

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 的优化库之一来处理(混合)整数规划。做一个谷歌搜索，你会发现很多。由于您的问题是凸的，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.]]