最適化問題について

質問

Max and Min 　x^2-2xy+2y^2
suject to 　x^2+y^2=1　(-∞＜x,y＜∞）

という問題なのですが、固有値問題で解けるような気がするのですが、進め方が分からず困っています。

どなたかよろしくお願いいたします。

回答No.2

echoes_x86

こんばんは．
ベクタ z = [x y]^T とし(^Tは転置記号)，対称行列Aを以下で定義します．
[ 1 -1]
[-1 2]
すると，目的関数は以下の二次形式で書けます．
z^T*A*z = x^2 - 2xy + 2y^2
さらに制約は次の二次形式です．
z^T*z = 1
これをラグランジュの未定乗数法を用いて解くことを考えます．
未定乗数λを導入した目的関数は以下です．
z^T*A*z + λ*(z^T*z - 1)
この式をベクタzで微分して零と置いたものを解けば所望の解が得られます
(ベクタによる二次形式の微分については自分で調べてください)．
すると以下の式を得ます．
A*z -λ*z = 0
これは対称行列Aの固有値問題に他なりません．
Aの最小固有値に対応する単位固有ベクタをz_1，固有値をλ_1とすると，
目的関数の値は
z_1^T*A*z_1 = z_1^T*(λ_1*z) = λ_1 * z_1^T*z_1 = λ_1
最大固有値に関しても同様です．
前の時はAの定義を間違えましたが，今回はあっているはずです．
http://oshiete1.goo.ne.jp/qa4599984.html

ところで，上記の問題は目的関数 z^T*A*z を制約 z^T*z = 1で解くわけですが，
目的関数と制約関数の比を新たな目的関数と考えることで解いても良いです(前の回答の方法)．
これは目的関数 z^T*A*z/N を制約 z^T*z = Nで解くのと同じ問題だからです．
新たな目的関数(Rayleigh商)を
R(z) = z^T*A*z/z^T*z
と考えて微分して零とすると
A*z/z^T*z - {R(z)/(z^T*z)^2}*z = 0
両辺をz^T*z倍すると以下を得ます．
A*z = R(z)*z
R(z)は未知数zの関数ですからこれを新たな変数λと見ると，
上の式はやはりAの固有値問題です．

回答No.1

Tacosan

なんかちょっと前にも同じ問題を見た気がするなぁ.
目的関数を 2次形式で書く.