找到向量的组合以接近目标向量

Question

我有大约10000个大约100个元素的向量(浮点(和1个也有100个元素。我的目标是通过使用这10000个向量的组合来接近这个目标向量。然而，我只能使用每个向量一次，并且元素可以是正的或负的。有人对此有什么想法吗？是否有可能进行优化？

一个小例子是：

v1 = [1.5, 3.0, -1.5]
v2 = [-0.5, -1.0, 3.0]
v3 = [1.0, 0.0, 0.0]
target = [0.5, 2.0, 1.0]
# the best combination here would be v1 and v2

PS。我使用的是Julia，但python、c(++(或对某些算法的想法也非常欢迎

Answer 1

阅读评论，似乎对问题的解释是minimize distance(sum(w[i] * v[i]) - target), for w[i] in [0, 1]。

如果我们使用标准欧几里得，这甚至不是MILP(混合整数线性规划(问题，它是一个混合整数二次规划问题。由于您没有定义距离，我将使用norm1作为距离的度量。

正如评论中提到的，你基本上有2**10,100的可能性。但幸运的是，MILP可以使用边界来修剪搜索(例如分支和边界(，并且在典型情况下的复杂性会小得多。

不久前，我在这里发布了一个没有约束w[i] in [0, 1]的问题的解决方案。这可以很容易地针对我们正在讨论的问题进行修改。

def place_there_ilp(X, target):
# some linear algebra arrangements
target = np.array(target).reshape((1, -1))
ncols = target.shape[1]
X = np.array(X).reshape((-1, ncols))
N_vectors = X.shape[0]
# variable of the problem
w = cvxpy.Variable((1, X.shape[0]), integer=True)
# solve the problem with the objective of minimize the norm of w * X - T (@ is the matrix product)
P = cvxpy.Problem(cvxpy.Minimize(cvxpy.atoms.norm1((w @ X) / N_vectors - target)), [w >= 0, w <=1])

# here it is solved
return w.value

尝试使用您提供的问题实例

v1 = [1.5, 3.0, -1.5]
v2 = [-0.5, -1.0, 3.0]
v3 = [1.0, 0.0, 0.0]
target = [0.5, 2.0, 1.0]
place_there_ilp([v1, v2, v3], target)

给出

array([[1., 1., 0.]])

这意味着1 * v1 + 1 * v2 + 0 * v3

运行10000 x 100问题可能会很困难，但我认为这是可能的。

使用下面的代码，我尝试了一个400 x 100，它在1.38s中运行，800 x 100在9.64s 中运行

X = np.random.randn(801, 100) # 800 x 100 problem
place_there_ilp(X[1:, :], X[0, :])