math - 線形結合を解くためのアルゴリズム?

Question

私が取り組んでいるプロジェクトで解決する必要がある次の問題に遭遇しました。

いくつかのベクトル v_i (数学的な意味で) とターゲット ベクトル H を指定して、ターゲット ベクトル H に最もよく一致するベクトル v_i の線形結合を計算します。係数は [0, 1] でなければならないという制約があります。 .

そのような問題にアプローチするためにどのようなアルゴリズム/数学を使用する必要があるかについて、私はあまり知りません。正しい一般的な方向へのプロドは大歓迎です!

Answer 1

制約付き最小二乗問題です。基本的に、最適化問題を解決したい：

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

wherex=(x_1, ..., x_j, ..., x_n)は求める係数で構成され、の列はAベクトル 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

quadprog次に、Matlabの関数を最適に解決できる問題があります

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 困難です。しかし、バイナリの場合は、解決できる多項式アルゴリズムがあるはずです。または、近似解を取得するための緩和があるかもしれません。「整数計画法」に関するグーグル検索が役立つ場合があります。