制約付き最小化問題の解

質問

以下の制約付き最小化問題の解を教えてください

Min： （Y-Xb)’＊（Y－Xｂ）
S.t： Aｂ＞０

Y：ｎ次元の列ベクトル
X：（ｎｘｋ） 行列
ｂ：ｋ次元の列ベクトル
A：（ｒｘｋ） 行列

ｂについて最小化するのですが、、、
Aｂ＞０の制約をどう扱えばいいのか分からず・・・

どなたかご教示お願いします

回答No.1

ramayana

Aｂ＞０の条件では、最小値が存在しないこともあります。制約条件をAｂ≧０に変更することにします。

（制約条件の境界だけを探索すればよいこと）

　　S(b) = （Y-Xb)’＊（Y－Xｂ）
　　Ω：　Aｂ≧０となるbの領域
　　β:　制約なしでS(b)を最小にするb

とします。

　　S(b) = 「bの正定値2次形式」＋定数

ですから、βを通る任意の直線上で、S(b)は、βにおいて唯一の極小値をとる2次関数です。したがって、もしβ∈Ωでなければ、制約条件付でのS(b)の最小値は、必ずΩの境界上で達成されます。

以下、計算方法の一例を示しますが、工夫すれば、もっと効率がよい方法があるかも知れません。

（変数変換により制約条件を単純化）

Aの階数＝rと仮定します。k行k列の適当な正則行列Mにより

　　b → Mb、 X → XM^(-1)

と変数変換することにより、Ωの条件は、一般性を失わずに

　　b1≧0、・・・、br≧0　　

とみなして構いません（b'=(b1, ・・・,bk)とする）。

（帰納的に計算）

　　β'=(β1, ・・・,βk)とします。

もし、β1≧0、・・・、βr≧0なら、βが、制約条件付の解です。
もし、上の条件を満たさないとき、例えば、β1＜0ならば、制約条件付の解は、境界上になければならないので、必ずb1 = 0を満たします。このときは、

　　T = （Y-Zc)’＊（Y－Zc）

を最小にするようなcを、制約条件

　　b2≧0、・・・、br≧0

で求める問題に帰着します。ただし、c' = (b2,・・・,bk) であり、Zは、Xの第2列目以降を抜き出したn行k-1列行列です。

上の手順を繰り返せば、最も運が悪いときでも、最終的に、単純な2次関数の最小値を求める問題に帰着します。