整数线性最小二乘问题

Question

所以我需要找到一个x，使得norm(A.dot(x) - y, 2)最小。其中A是一个矩阵，y是一个向量。

虽然可以使用scipy.optimize.lsq_linear或numpy.linalg.lstsq轻松实现，但我需要x为整数。一般来说，“整数规划”是NP完全问题。 我确实发现了解决标准整数最小二乘问题的例程，但在转换成Python之前，我想先询问。

是否有已建立的库可以在Python中解决整数线性最小二乘？

- Jacob

---

@ruakh，谢谢，忘记了。哈哈。 - Jacob

这是你要找的吗？https://docs.scipy.org/doc/numpy-1.10.0/reference/generated/numpy.linalg.lstsq.html - lightsong

@sinewaver，lstsq返回浮点数。我希望找到最佳整数解决方案。 - Jacob

请点击此处查看：https://wiki.python.org/moin/NumericAndScientific/Libraries。 - litepresence

你有没有开始在Python中实现MILES包？ - hydronium

我没有这样做，我使用了答案中的其他建议。 - Jacob

Answer 1

您可以使用Python中可处理（混合）整数规划的优化库之一。进行谷歌搜索，您会发现很多。由于您的问题是凸的，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.]]

- Stelios

Answer 2

我想到了一个相关的解决方案，可以通过将其转换为线性整数规划问题并使用PuLP进行求解来解决sum（| Ax-y |）。

基本思路是最小化目标函数sum(err(i))，并满足以下约束条件：

Ax(i) - y(i) <= err(i) 和 Ax(i) - y(i) >= -err(i)。

这与线性求解器兼容。

- user3833171