Skip to main content
 首页 » 编程设计

python之整数线性最小二乘法

2025年02月15日8duanxz

所以我必须找到一个 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.]]