ラグランジュの未定乗数法

質問

次のような問題の最適解(目的関数の値とそのそきのxの値)をラグランジュの未定乗数法で求めたいのですが、どうやってやればよいのでしょうか？？？主成分分析で用いる手法とのことですが。。。

問題は以下のような問題です

max　x^T*Ax 　　　　ただし、　x:n次列ベクトル
s.t. 　x^T*x=1 　 A:n*n正定対称行列(固有値が正)

回答No.2

tomtak · ベストアンサー

f(x)=x^T*Ax、
g(x)=x^T*x-1
と置きます。

ラグランジュ未定乗数法から、
g(x)=0の条件の下でf(x)が極値をとるのは、

F(x,λ)=f(x)-λg(x)

と置き、

∇F(x,λ)=0　かつ　g(x)=0

を満たすときです。
ここで∇は、xのそれぞれの成分についての偏微分を表します。
成分で書くと、

∂F(x,λ)/∂x_i
=∂{ΣΣx_k・A_kj・x_j-λ(Σx_j^2-1)}/∂x_i
=2(ΣA_ij・x_j-λx_i)

です。すなわち、

∇F(x,λ)=2(A-λ)x

です。これが0より、

Ａx=λx　

よって、ｘがＡの固有ベクトル、λが固有値のときf(x)が極値をとります。
g(x)=0より、ｘは規格化されている必要があります。

また、このとき、f(x)=λx^T*x=λ
となります。

よって、f(x)が最大になるのは、λが最大の固有値の時です。

お礼

詳しい回答をありがとうございます
よく理解することができました
今後ともよろしくお願いいたします

補足

少し疑問に思ったところがありましたので
補足して質問させてください

２行目のg(x)=x^T*x-1　なのですが
T*(x-1)ではなく(T*x)-1　ということでよろしいのでしょうか？

回答No.3

tomtak

＞２行目のg(x)=x^T*x-1　なのですが
＞T*(x-1)ではなく(T*x)-1　ということでよろしいのでしょうか？

そうです。
x^T*x=1　という条件を、
(x^T*x)-1=0　という形(g(x)=0)に書き直しただけです。

お礼

親切な回答をありがとうございました
大変勉強になりました
今後ともよろしくお願いいたします

回答No.1

kony0

下記URLは参考になりませんか？（googleで「未定乗数法」と入力して1番目にヒットしたもの）

これに忠実に作業すれば、「(A+A^T)の固有ベクトル」が答えとして有力そうです。（計算は自身なしです）

参考URL：

http://www.neuro.sfc.keio.ac.jp/~masato/study/SVM/lagrange.htm

お礼

適切なサイトを教えていただきましてありがとうございます
今後ともよろしくお願いいたします