最適化問題について
- 最適化問題において、n×nの正定値対称行列Aとn×1の任意のベクトルxに関数f(x)=t(x)Ax/t(x)xを考えます。
- この問題は、条件||x||=1の下で、関数t(x)Axの最適化問題に帰着されます。
- また、f(x)の極値を取るベクトルxはAの固有値ベクトルであり、その最大値と最小値を求めることができます。
- ベストアンサー
最適化問題について
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の最適化問題に帰着されるのか、というくだりと極値云々というのがどうしてもわかりません。 よろしくお願いします。
- remilia_21
- お礼率80% (4/5)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
c = 1 / ||x|| を代入してみましょう。 f(x) = f(y), y = x / ||x|| となります。 任意の x に対して ||y|| = 1 ですから、 f(x) の最大値・最小値は、 f(y) ただし ||y|| = 1 の最大値・最小値に 一致します。
その他の回答 (1)
- arrysthmia
- ベストアンサー率38% (442/1154)
0 でないスカラー c に対して、f(cx) = f(x) が常に成り立つからです。 f(cx) を、計算してごらんなさい。 分子分母とも、c^2 倍になっています。
補足
えぇっと…f(cx) = f(x) は当然わかるのですが、そのことが||x||=1の条件下で、t(x)Axの最適化問題に帰着されるという部分に 何故繋がるのかがイマイチわかりません。 関数f(x)もf(cx)だろうと結果は変わらないため、||x||=1にして計算を楽にしてる、とかですかね？
関連するQ&A
- ラグランジュを用いた最適化問題
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 が求まる。」 と書いてあって、理解できません。 どなたかよろしくお願いします。
- ベストアンサー
- 数学・算数
- 線形計画法の問題です
Ｐ：最大化ｃ＾Ｔｘ（ｃ＾Ｔはｃの転置） 条件Ａｘ＜＝ｂ ｘ＞＝０ ただし、Ａはｍ＊ｎ行列、ｂはｍ次元ベクトル、ｃはｎ次元ベクトル、ｘはｎ次元 変数ベクトルである。ベクトルはすべて列ベクトルとし、ｃ＾Ｔはｃの転置を表す。 問題Ｐは最適解を持つと仮定し、目的関数の最大値をｆと表す。また、問題Ｐ に関連して、ｍ次元ベクトルｕをパラメータとする次の線形計画問題を考える。 Ｐ（ｕ）：最大化ｃ＾Ｔｘ－ｕ＾Ｔ（Ａｘ－ｂ） 条件ｘ＞＝０ 問題Ｐ（ｕ）の目的関数の最大値ｇ（ｕ）と表す。ただし、問題Ｐ（ｕ）が有界でない 場合はｇ（ｕ）＝無限大と定義する。以下の問いに答えなさい。 １）問題Ｐの双対問題を書きなさい ２）任意のｕ＞＝０に対して、ｇ（ｕ）＞＝ｆが成り立つことを示しなさい ３）ｍｉｎ｛ｇ（ｕ）｜ｕ＞＝０｝＝ｆが成り立つことを示しなさい。ただし、線形計画問題 に対する強双対定理を用いて良い。 以上の問題をお願いします。
- 締切済み
- 数学・算数
- 極を持たない条件
たびたび質問失礼します。 行列Aは4x4対角行列であり、^Tで転置を表すとするとb^T＝(0,1,1,1)とした場合、ベクトルxを引数とする関数ψ(x)=(x^T)Axの極を求める。ただし、拘束条件として、|x|^2=1,(b^T)x=0 という問題なのですが、このとき、x^T=(1,0,0,0)が極値を与える解とならないAの例を挙げよ。また、その例において極値を与えないことを示せ。という問題の解答で、A=diag[0,1,1,-1]という対角成分を持つAとすると、Aが極値を与えないことは自明に明らか、と書かれているだけなのですが、どうして自明に明らかと言えるのでしょうか？ 宜しくお願いします。
- ベストアンサー
- 数学・算数
- ラグランジュの未定乗数法
次のような問題の最適解(目的関数の値とそのそきのxの値)をラグランジュの未定乗数法で求めたいのですが、どうやってやればよいのでしょうか？？？主成分分析で用いる手法とのことですが。。。 問題は以下のような問題です max x^T*Ax ただし、 x:n次列ベクトル s.t. x^T*x=1 A:n*n正定対称行列(固有値が正)
- ベストアンサー
- 数学・算数
- 正定値行列の最大・最小
正定値行列の最大・最小 行列の問題で以下の問題が分からないので、分かる方はヒントをいただければと思います。 一応画像を張っておきますが（張れてないかも・・・）見えにくい（見えない）場合は、下に同じ表現の文章を書いていますので下の文章を見てください。 Ａをp次対称行列,ｂをp次元ベクトルとす。このときfを ｆ(ｘ1,ｘ2,・・・,ｘp) = ｘ^tＡｘ + （ｂ,ｘ） (-∞<ｘi<+∞) と、定義する。 (1)Aが正定値行列であるとき、fの最大値、最小値を求めよ。 (2)Aが非不正定値行列でｂがＭ（Ａ）の元でないとき、ｆの最大・最小を求めよ。ただしＭ（Ａ）は行列Ａの縦ベクトルが張る線形部分空間を表す。 初めのｆの定義でのｘ＾tはｘの転置行列、（ｂ、ｘ）はｂとｘの内積を表しています。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 数学 ラグランジュの乗数を用いた最大最小問題
数学の問題で困っています。 9x^2 +4y^2 =36 のとき、xyの最大値と最小値を求めよ。 この問題をラグランジュの乗数を用いた連立方程式と元の条件式から、 xyの極値の候補が(x,y)＝(√2，3/√2），(√2，-3/√2），(-√2，3/√2)，(-√2，-3/√2) の4つであることが分かったのですが、ここからどうやって最大、最小を説明するのかがわかりません。 すなわち (1)xyの極値の候補が実際に極値であることをどうやって示すのか (2)極値が最大、最小の値にもなるということをどうやって示すのか 以上の2点で困っています。 詳しい解説お願いします。
- ベストアンサー
- 数学・算数
お礼
なるほど、合点がいきました！ ありがとうございました。