きっかけ
いつものようにボケーっとしながらツイッター見てたら面白そうなものを見つけた。
これ急に見て三角関数やんとはならないやろ
【画像】
画像の内容は、とある参考書を写したものである。
「$x^2+y^2=4$のときの$2x^2+3xy-y^2$の最大値・最小値を求めよ」という問題に対して、$x=2\cos{\theta},y=2\sin{\theta}$という変数変換をして解いているというような解法が書かれいた。
逆張りオタクをこじらせてしまったので、三角関数を使わない解法を考えてみることにした。ついでに一般化もしてみる。
考察
$n\in\mathbb{N}$として、$x=(x_1,\ldots,x_n)^\top \in\mathbb{R}^n$と書く。
とりあえず、$\parallel x\parallel =1$のときの$x^\top Ax$の最大値と最小値を求めよという問題を解くことにする。
ここで、$\parallel x\parallel:=\sqrt{x_1^2+\cdots+x_n^2}=\sqrt{x^\top x}$である。
また、$A$は$n$次元正方行列だが、
$$x^\top A x=\sum_{i,j}a_{i,j}x_i x_j$$
となっているが、
$$a_{i,j},a_{j,i}\to \dfrac{a_{i,j}+a_{j,i}}{2},\dfrac{a_{i,j}+a_{j,i}}{2}$$
という変換をしても式としては同じであるため、$A$は対称行列であるとしてもよい。
対称行列だと何が良いかというと、直交対角化ができる。
つまり、$A=P\Lambda P^{-1}$であり、
このとき$P$は直交行列、$\Lambda$は対角行列である。
直交行列なので、逆行列と転置が等しくなる。つまり、$P^\top=P^{-1}$となる。
また、対角行列$\Lambda$を成分表示すると以下のようになる。
$$\Lambda =\begin{pmatrix}\lambda_1&\cdots &0\\\vdots&\ddots&\vdots\\0&\cdots&\lambda_n\\\end{pmatrix}$$
ここで、$\lambda_1\geq \cdots\geq \lambda_n$としてもよい。（対称行列なので、固有値は全て実数であることが保証される。）
このとき、$y=P^{-1}x$と変数変換すると、
$1=x^{\top}x=x^{\top}PP^{\top}x=y^{\top}y$
である。よってこの問題は
$\parallel y\parallel =1$のときの$y^{\top}\Lambda y=\sum_{i=1}^{n}\lambda_i y_i^2$の最大値・最小値を求めれば良いことになる。
これは、
$$\lambda_n=\sum_{i=1}^{n}\lambda_n y_i^2\leq \sum_{i=1}^{n}\lambda_i y_i^2\leq \sum_{i=1}^{n}\lambda_1 y_i^2=\lambda_1$$
である。ここで、一個目の不等式は$y=(0,\ldots,0,1)^\top$のとき、二個目の不等式は$y=(1,0,\ldots,0)^\top$のときに等号が成立するので、実際に$\lambda_1,\lambda_n$がそれぞれ最大・最小となる。
ここで、$e_i$を$i$番目の基本ベクトルとする。$y=e_1$のときに最大となって$y=e_n$のときに最小となることに注意。このとき、$\Lambda e_i=\lambda_i e_i$なので、$\lambda_i, e_i$は$\Lambda $の固有値と固有ベクトルの組となる。
ここで、$x^\top Ax$が最大・最小となるような$x$はそれぞれ$Pe_1,Pe_n$である。
ここで、
$$APe_i=PP^{-1}APe_i=P\Lambda e_i=\lambda_i Pe_i$$
なので、$\lambda_i,Pe_i$は$A$の固有値と固有ベクトルの組となる。
つまり、$x^\top Ax$が実際に最大・最小となるような$x$は最大値・最小値（これらは$A$の固有値となる）に対応する固有ベクトルとなる。
これで終わりかと思いきや、件のツイートをよく見てみるとなんと、$x\geq 0,y\geq 0$という条件が課されているのである。
ここら辺の条件をなんとかするとしたら三角関数が一番手っ取り早いのかもしれないと思ったが、なんとかして逆張りを完遂したいので頑張る。
$n-1$次元球面上のある領域$D$について$\overline{D}:=D\cup \partial D$とする。
$x\in\overline{D}$における$x^\top Ax$の最大値・最小値を求めることにする。
ここで、$\overline{D}$はコンパクトなので、最大値・最小値を達成するような点は必ず存在する。最大値・最小値は無いというようなことは考えなくてもOK。
ここで、$\overline{D}$内に、$Pe_1$というベクトルが含まれているならば最大値は$\lambda_1$としても問題ないはずである。最小値も同じ
一方、含まれてない場合はどうすればいいかというと、これは見た感じ領域の境界点に最大最小を達成する点がありそうなので、これを示す。
ここで、今までは$x^\top Ax$の最大最小を考えていたが、以降では
$$f(x):=\dfrac{x^\top Ax}{x^\top x}$$
について考える。このとき、斉次化されているので$x$を定数倍しても値は変わらなくなっている。
（$f(rx)=f(x),r\in(0,\infty) $）
よって、この場合、$D'=\{x\in\mathbb{R}^n\setminus \{0\}: \dfrac{x}{\parallel x\parallel}\in D\}$という領域内で考えてもいいことになっている。
ここで、
$\overline{D'}=\{x\in\mathbb{R}^n\setminus \{0\}: \dfrac{x}{\parallel x\parallel}\in \overline{D}\}$である。
ここで、この式を$x_i$番目の変数で偏微分すると
$$\dfrac{\partial}{\partial x_i}\dfrac{x^\top Ax}{x^\top x}=\dfrac{1}{(x^\top x)^2}\left( (x^\top x)\cdot \dfrac{\partial }{\partial x_i}(x^\top Ax)-(x^\top A x)\cdot \dfrac{\partial }{\partial x_i}(x^\top x)\right)$$
ここで、
$$\dfrac{\partial}{\partial x_i}(x^\top x)=2x_i$$
$$\dfrac{\partial}{\partial x_i}(x^\top A x)=\dfrac{\partial }{\partial x_i}(-a_ix_i^2+2\sum_{j=1}^{n}a_{i,j}x_ix_j)=2\sum_{j=1}^{n}a_{i,j}x_j=2(Ax)_i$$
となっているので、
$$\dfrac{\partial}{\partial x_i}f(x)=\dfrac{2}{(x^\top x)^2}\left( (x^\top x)\cdot (Ax)_i -(x^\top A x)\cdot x_i\right)$$
つまり、
$$\nabla f(x)=\dfrac{2(x^\top x)Ax-2(x^\top Ax)x}{(x^\top x)^2}$$
である。ここで、$y$が微小なベクトルであると仮定したとき、
$$f(x+y)\simeq f(x)+y^\top \nabla f(x)$$
である。ここで、$\nabla f(x)$が0ベクトルでないならば、ある微小なベクトル$y$を取れば$y^\top \nabla f(x)\gt 0$であり、$(-y)^\top \nabla f(x)\lt 0$となる。
このような状況において、$f(x-y)\lt f(x)\lt f(x+y)$となる。
もし$x\in D'$ならば、ある$\varepsilon\gt 0$が存在して$B(x,\varepsilon)\subset D'$なので、$x$は$f$を最適化しなくなる。つまり、ある微小なベクトル$y$が存在して、$f(x-y)\lt f(x)\lt f(x+y)$かつ、$x+y\in D',x-y\in D'$となるため、少なくとも$x$よりも大きく/小さくなる点が存在する。
では、$\nabla f(x)=0$となるのはどのような場合か？
それは、
$$(x^\top x)Ax=(x^\top Ax)x$$
であるようなときである。
これをよく見てみると、$Ax$と$x$が平行なベクトルであることが要求される。
つまり、$x$は$A$の固有ベクトルでなくてはいけない。
逆に$x$が固有ベクトルなら、固有値を$\lambda $とすると計算すれば$\nabla f(x)=0$が求まる。
結局、内部の点で最大値・最小値となるならば、それは固有ベクトルである。
$x$が固有ベクトルの場合
最大値・最小値を達成するような点が固有ベクトルであることがわかったが、それが最大固有値・最小固有値に対応する固有ベクトルかどうかはまだ言い切れない。
ここで、$x$は$A$の固有ベクトルとなるが、$x$に対応する固有値を$\lambda$とおく。ここで、$\lambda\neq \lambda_1,\lambda \neq \lambda_n$とする
このとき、
$$f(x+y)\simeq f(x)+y^\top H_f(x)y$$
となる。ここで、$H_f(x)$はヘッセ行列であり、$(i,j)$成分は$\dfrac{\partial}{\partial x_i}\dfrac{\partial}{\partial x_j}f(x)$である。
$$H_f(x)_{i,j}=\dfrac{\partial}{\partial x_j}\dfrac{\partial}{\partial x_i}\dfrac{x^\top Ax}{x^\top x}=\dfrac{\partial}{\partial x_j}\dfrac{1}{(x^\top x)^2}\left( 2(x^\top x)(Ax)_i-(x^\top A x)2x_i\right)$$
これを頑張って計算すると
$$=\dfrac{2}{(x^\top x)^3}\left(-2(x^\top x)((Ax)_i x_j+(Ax)_j x_i)+(x^\top x)^2 a_{i,j}+4(x^\top Ax)x_ix_j-(x^\top x)(x^\top Ax)\delta_{i,j}\right)$$
ここで、$\delta_{i,j}$はクロネッカーのデルタである（$i=j$ならば$\delta_{i,j}=1$,$i\neq j$ならば$\delta_{i,j}=0$）
よって、ヘッセ行列は（注：$I_n$は単位行列）
$$H_f(x)=\dfrac{2}{(x^\top x)^3}\left(-2(x^\top x)((Ax)x^\top +x(Ax)^\top)+(x^\top x)^2 A+4(x^\top Ax)xx^\top -(x^\top x)(x^\top Ax) I_n\right)$$
ここで、$Ax=\lambda x$であることから、
$$H_f(x)=\dfrac{2}{(x^\top x)}\left( A -\lambda I_n\right)$$
この行列の固有値は$\dfrac{2}{x^\top x}(\lambda_1-\lambda),\ldots,\dfrac{2}{x^\top x}(\lambda_n-\lambda)$である。
仮定より$\lambda_1-\lambda \gt 0,\lambda_n-\lambda\lt 0$
なので、$Pe_1$の方向に進めば、$f$の値はより大きくなり、$Pe_n$の方向に進めば、$f$の値はより小さくなる。よって、この場合は$x$において$f$は最大でも最小でもない。
よって、最大でない固有値に対応する固有ベクトルが最大値を達成することはない。最小についても同様。
結局、領域内部において最大値/最小値を達成するような点は最大固有値/最小固有値に対応する固有ベクトルであることがわかった。
で、もしそのような固有ベクトルが領域にない場合、その他の内部の点が最大値/最小値を達成することはない。よって、消去法により境界において最大・最小を達成することになる。
以上を踏まえると、最大/最小固有値に対応する固有ベクトルが領域内に存在しないならば、領域内における最大値/最小値については、境界の部分だけ探索すれば良いことになる。
結論
長々と書いたが、以下の結論が従う。
$x\in\mathbb{R}^n$として、$A$を$n$次対称行列として、$D\subset S^{n-1}$を領域とする。ここで、$S^{n-1}=\{x\in\mathbb{R}^n:\parallel x\parallel=1\}$である。
位相は$S^{n-1}$における部分位相を考えている。この位相において$D$は開集合であると仮定している。
このとき、$x\in \overline{D}$という範囲内での$x^\top Ax$の最大値・最小値について、以下が従う。（$\overline{D}$はコンパクトなので最大値・最小値が必ず存在する。）
$A$の固有値は全て実数であることが保証されるが、その中で最大なものを$\lambda_1$とする。
もし、$\lambda_1$に対応する固有ベクトル$v_1$であって、$x\in\overline{D}$であるようなものが存在するならば、$v_1$において$x^\top Ax$は最大となる。
もしそのような固有ベクトルが存在しないならば、最大を達成するような$x$は領域の境界上のどれかである。
最小値についてもほぼ同じである。
$A$の固有値は全て実数であることが保証されるが、その中で最小なものを$\lambda_n$とする。
もし、$\lambda_n$に対応する固有ベクトル$v_n$であって、$x\in\overline{D}$であるようなものが存在するならば、$v_n$において$x^\top Ax$は最小となる。
もしそのような固有ベクトルが存在しないならば、最小を達成するような$x$は領域の境界上のどれかである。
解答
以上を踏まえて問題を解く
$$A=\begin{pmatrix}2&3/2\\3/2&-1\end{pmatrix}$$
として、
まずは$x^2+y^2=1$における最大・最小を求める。
これの固有方程式は$(2-t)(-1-t)-(3/2)^2=\dfrac{1}{4}(4t^2-4t-17)$なので、
これを解くことで$t=\dfrac{1\pm 3\sqrt{2}}{2}$が固有値であると分かる。
で、最大の固有値は$\dfrac{1+3\sqrt{2}}{2}$であり、最小の固有値は$\dfrac{1-3\sqrt{2}}{2}$である。
よって、$x\geq 0,y\geq 0$という条件を無視するならば、
$(x,y)=\pm \dfrac{1}{\sqrt{4+2\sqrt{2}}}(1+\sqrt{2},1)$のときに最大値$\dfrac{1+3\sqrt{2}}{2}$
$(x,y)=\pm \dfrac{1}{\sqrt{4+2\sqrt{2}}}(-1,1+\sqrt{2})$のときに最小値$\dfrac{1-3\sqrt{2}}{2}$
を達成するはずである。
ここで、$x\geq 0,y\geq 0$の条件を付け加えるとどうなるだろうか。
$(x,y)=\dfrac{1}{\sqrt{4+2\sqrt{2}}}(1+\sqrt{2},1)$とすると$x\geq 0,y\geq 0$を満たすので、このときに実際に最大値を達成する。よって最大値は$\dfrac{1+3\sqrt{2}}{2}$で問題ない。
しかし、最小値を達成するベクトルは$x\geq 0,y\geq 0$の範囲内に無い。
つまり、$x\geq 0,y\geq 0$という条件を追加した場合の最小値は領域の境界にあることになる。
ここで、境界は$(x,y)=(1,0),(0,1)$からなる2点集合となるので、それぞれについて計算すると、
$(x,y)=(1,0)$のとき$2$
$(x,y)=(0,1)$のとき$-1$
なので、最小値は$-1$である。（$(x,y)=(0,1)$のときに最小値を達成する。）
以上が$x^2+y^2=1$のときの答えである。
ツイートにおける問題文は$x^2+y^2=4$となっている。これについては$(x,y)\to(2x,2y)$と変換すると$x^2+y^2=1$の場合と$x^2+y^2=4$の場合が一対一対応する。
よって$x^2+y^2=4$の場合を求めるには、$x^2+y^2=1$としたときの答えを単純に4倍すればよい。
よって、最大値は$2+6\sqrt{2}$であり、最小値は$-4$である。
$$f(t,x)=x^\top Ax-t x^\top x$$
というものを考える
$A$の$(i,j)$成分を$a_{i,j}$として、$A^\top=A$を仮定
ここで、
$$\dfrac{\partial}{\partial x_i}f(t,x)=\dfrac{\partial}{\partial x_i}\left(-a_{i,i}x_i^2+2\sum_{j=1}^{n}a_{i,j}x_ix_j -2tx_i^2\right)+(x_iに依存しない部分)$$
なので、
$$\dfrac{\partial }{\partial x_i}f(t,x)=2\sum_{j=1}^{n}a_{i,j}x_j-2tx_i$$
なので、
$$\nabla f(t,x)=2Ax-2tx=2(A-t I_n)x$$
となる。$\parallel x\parallel =1$で$\nabla f(t,x)=0$となるためには、
少なくとも$A-tI_n$が非正則行列でならなくてはいけない。このとき$t$は$A$の固有値となり、極値となるようなベクトル$x$は$A$の固有値$t$に対する固有ベクトルとなる。つまり、最大・最小を達成するようなベクトルも固有ベクトルとなる。あとは同じ
あとがき
ツイートの問題を解くだけなら、極座標変換したほうが一番手っ取り早い気がした。
でも、多次元だと極座標変換したら面倒くさくなるし対称性も崩れるのでこの記事でやったように線形代数で殴ったほうが良いのかもしれない。
余談
行列のノルムの定義（のうちの1つ）は以下の通りである。
$$\parallel A\parallel :=\sup_{\parallel x\parallel=1}\parallel Ax\parallel$$
ここで、
$$\parallel Ax\parallel=\sqrt{x^\top A^\top Ax}$$
このとき、$A^\top A$は対称行列であることに注意
つまり、$\parallel x\parallel =1$の場合の$x^\top A^\top Ax$の最大値を求めればよいことになる。
よって、行列のノルムは$A^\top A$の最大の固有値のルートを取ったものとなる。
ここで、任意の$x\in\mathbb{R}^n$について$x^\top A^\top Ax=\parallel Ax\parallel ^2\geq 0$であるため、$A^\top A$は半正定値行列となる。よって全ての固有値が非負であることが保証されるので安心してルートを取ることができる。
