查找载体组合以接近目标载体

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

阅读评论，似乎问题的解释是最小化距离（和（w[i]*v[i]）-目标），对于w[i]在[0,1]。

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

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

前段时间我在这里发布了一个没有约束< code>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.]])

这意味着< code>1 * v1 1 * v2 0 * v3

您可能很难运行10000 x 100问题，但我想说这是可能的。

使用下面的代码，我尝试了400 x 100它运行在1.38秒内，800 x 100运行在9.64秒内

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