• ベストアンサー

ラグランジュを用いた最適化問題

xはn次元ベクトル、AとBはn×nの行列です。 Aは半正定値で階数はたかだか(n-1)であるとします。 xの転置をx'と表しています。 max　　x'Ax s.t.　 　x'Bx - 1 = 0 という問題についてなんですが、ここでラグランジュを考えると L(x) = x'Ax - λ( x'Bx - 1 ) となって、xについて偏微分して0とおくと、 Ax = λBx となり、Bに逆行列B^(-1)が存在するならば (B^(-1)A - λI)x = 0　(Iは単位行列) となりますよね。ここまではわかるのですが、次に 「B^(-1)Aの最大固有値をλ1とすると max{L(x)} = λ1 が求まる。」 と書いてあって、理解できません。 どなたかよろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.1

Ax = λBx　を満たす x が最大値（正確には極値)を 与えるわけです。 これを使ってもとのL(x)において Ax を消去すると、 L(x) = λ　になりますよね？ 許されるλは (B^(-1)A - λI)x = 0 によって決まるわけなので、B^-1 A の固有値です。 すなわち、固有値のうちで最大のものが max L(x) に なるわけです。

coldplay
質問者

お礼

L(x)=λ になるんですね！ 完全に盲点でした。 ありがとうございました。

その他の回答 (1)

  • yaksa
  • ベストアンサー率42% (84/197)
回答No.2

たんに、 (B^(-1)A - λI)x = 0 B^(-1)Ax = λx の解をL(x)の式に代入しただけかと。 Ax = λBx 両辺に左からx'をかけて x'Ax = λx'Bx したがって、 L(x) = x'Ax - λ( x'Bx - 1 ) 　　 = λ

coldplay
質問者

お礼

タッチの差でしたね（笑） ありがとうございました。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

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

    次のような問題の最適解(目的関数の値とそのそきのxの値)をラグランジュの未定乗数法で求めたいのですが、どうやってやればよいのでしょうか？？？主成分分析で用いる手法とのことですが。。。 問題は以下のような問題です max　x^T*Ax 　　　　ただし、　x:n次列ベクトル s.t. 　x^T*x=1 　 A:n*n正定対称行列(固有値が正)

  • 行列の問題です。

    行列の問題です。 A^tはAの転置行列 R^nの2つのベクトル x^t=(x_1,..,x_n) y^t=(y_1,..,y_n) に対して内積<x,y>を Σ_{i=1～n}x_iy_i で定義する。 Aをn×n実交代行列とする。 Bをすべての固有値が正となる実対称n×n行列とする。 (1)任意のベクトルx∈R^nに対して <Ax,x>=0を示せ。 (2)任意のベクトルx∈R^nに対して <Bx,x>≧0であり、 統合はx=0のときに限ることを示せ。 (3)A+Bは正則行列となることを示せ。 よろしくお願いします。

  • 整式の除法に関する問題です。

    整式の除法に関する問題です。 「ax^n+bx^(n-1)+1が(x-1)^2で割り切れるとき、a、bをnで表せ」という問題です。 私は 　ax^n+bx^(n-1)+1=f(x)(x-1)^2と表せることから、両辺のxに1を代入して、 　a+b+1=0 を得ましたが、これで良いのでしょうか？ a、bをnで表せていません。どなたかアドバイスの程宜しくお願い致します。

  • ラグランジュ関数の偏微分

    ラグランジュ関数 L(x,λ)=f(x)+Σ(i=1～m)λi・gi(x) をλで偏微分すると ▽L(x,λ)=(g1(x),g2(x),…,gm(x))t(←tは転置の意味) になるとあるのですが、何故、転置が出てくるのかがよくわかりません。 どなたか詳しい方お答え願えますでしょうか？よろしくお願いします。

  • 最適化問題について

    n×nの正定値対称行列であるAと、n×1の任意のベクトルxに対して 関数f(x)=t(x)Ax/t(x)x　　　t()は転置 の最適化問題が、||x||=1の条件下で、t(x)Axの最適化問題に帰着されることを説明した上で f(x)の極値を取るベクトルxがAの固有値ベクトルであることを示し、かつf(x)の最大値、最小値を求めよ。 という問題なのですが、最大値、最少値を示す問題は観て未定乗数法で制約条件を||x||=1にして求めるのかなぁ、と何となくわかるのですが、 どうして||x||=1の条件下で、t(x)Axの最適化問題に帰着されるのか、というくだりと極値云々というのがどうしてもわかりません。 よろしくお願いします。

  • 最適化の問題に詳しい方

    お世話になっております。 Let x0 and x1 be solution of min tcx+c0 s.t. Ax≦a, Bx=b, x≧0 Show that all points on the line with end points x0 and x1 are solutions. (A:m×n matrix, a,b,c∈R^n, B:k×n matrix) 訳せば 「x0とx1を min tcx+c0 s.t. Ax≦a, Bx=b, x≧0 の解とする時、終点をx0とx1とする線上の全ての点が解を示せ」 これはどうやって示せばいいのでしょうか? tは転置行列の意味だと思います。 x_0とx_1がAx≦a,Bx=b,x≧0を満たしていて、tcx0=tcx1ならば点λx0+(1-λ)x1も Ax≦a,Bx=b,x≧0を満たしていて、同じ最適値(?)を持つ事をいいのかと思いますが この手の問題になれてらっしゃる方,お教え下さい。

  • AはC上のn次正方行列のとき。

    『AはC上のn次正方行列.E_nはn次単位行列,b∈Cとするとき、 1：bはAの固有値である。 2：det(bE_n-A)=0 の二つが同値を示せ』 という問題で、 i）1→2のとき Aの固有ベクトルをxと置く、 Ax＝bx E_nはn次単位行列だから AE_n＝A AE_nx＝Ax＝bx Ax＝bE_nx A＝bE_n このとき次数も等しいから det(bE_n-A)=0. ii）行列(bE_n-A)の次数は0より bE_n-A=0 bE_n=A E_nはn次単位行列 Aはn次正方行列 だから bはAの固有値. この２つから題意は示せますか？

  • 行列の問題です。

    行列の問題です。 A:n×n行列 x:1×n行列 任意のxに対して、 内積<Ax,x>≧0 (等号はx=0のときのみ) が成立するとき Aは正則ですか？ A=(c_i) c_i:1×n行列,1≦i≦n として考えていたのですが、うまくいきません…。 よろしくお願いします。

  • 線形写像のノルムに関する関する問題です

    線形写像A∈L(R^n,R^m) (=R^nからR^mへの線形写像全体） に対して||A||を||A||≡sup{||Ax|| : x , ||x||≦１｝で定めます。 ||A||がm×ｎ個の変数{a}ij (i=1・・・m , j=1・・・ｎ)の連続関数となることを示す問題です。 以前にいくつかのヒントをいただいて自力で頑張ってみたのですがいまだに理解できません。どなたか証明の仕方をお願いします。 必要な場合、以下の性質が使えます。 （i） ||A||＝sup{||Ax||＼||x|| : x≠0 ,x∈R^n} ＝sup{||Ax|| : x=1 ,x∈R^n} (ii) A∈L(R^n,R^m), B∈L(R^m,R^l)　であるとき||BA||≦||B||||A|| (iii) A∈L(R^n,R^m),の標準基底に関する表現行列を(a_ij) (i↓1,・・・,m ; j→1,・・・,n)とするとき 　　maxΣa^2_ij≦||A||^2≦ΣΣa^2_ij (i=1,・・・,m ; j=1,・・・,n)

  • 逆行列が存在しない連立一次方程式

    Ax = b　　　　　Aはm×n行列　m≠n xはn×1　bはm×1 という式があるとき、 x = (At・A)^-1・b　　　　　　At： Aの転置 と変形すると一般化逆行列を求めなくてもxが求められるように思うのですが、この式変形は間違ってますか？

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する