math - 求解线性组合的算法？

Question

我遇到了以下问题，我需要在我正在处理的项目中解决：

给定一些向量 v_i（在数学意义上）和一个目标向量 H，计算与目标向量 H 最匹配的向量 v_i 的线性组合，约束条件是系数必须在 [0, 1] .

我不太了解应该使用哪种算法/数学来解决这样的问题。任何在正确的大方向上的刺激都将不胜感激！

Answer 1

It's a constrained least square problem. Basically you want to solve the optimization problem:

  argmin ||Ax-H||
    x
  s.t.  0<=x_j<=1

where x=(x_1, ..., x_j, ..., x_n) consists the coefficients you are seeking, and a column of A corresponds to a vector v_i.

Answer 2

假设您想以最小二乘的方式求解，那么您有一个二次规划问题。例如，假设您的向量集是

x1 = 1 2 3]'    x2 = [3 2 1]'

你的目标向量是

H = [1 -1 1]'

然后您可以创建其列是您的向量的矩阵：

A = [1 3;
     2 2;
     3 1]

你试图最小化的事情是

norm(A*x - H) = (A*x - H)' * (A*x - H) = x' * (A'*A) * x - (2*H'*A) * x + const

如果你定义

B = A' * A
C = -2 * H' * A

那么你有一个问题可以通过我的 Matlabquadprog函数得到最佳解决

quadprog(B,C,[],[],[],[],0,1)
ans = 
    0.16667
    0.16667

所以这种情况下的最优解是

1/6 * x1 + 1/6 * x2 = [2/3, 2/3, 2/3]

Answer 3

这是一个组合优化问题。这类问题是 NP 难的。但我猜对于二进制，应该有多项式算法可以解决，或者可能有一些放松来得到一个近似的解决方案。一些关于“整数编程”的谷歌搜索可能会有所帮助。