シャープレシオ最大化問題 その３

<<前回までのリンク>>
その２， その１

前回は制約を満たす w をカーネル K の元 v を用いて
変数変換を行いましたね～
その結果問題は次のように書き変わったのでした～

\begin{aligned}
\text{maximize} &\quad f(v) = \frac{ \langle s, v \rangle_\varSigma + \frac{\langle s, \varSigma^{-1}\boldsymbol{1} \rangle_\varSigma}{\lVert \varSigma^{-1}\boldsymbol{1} \rVert_\varSigma^2}
 }{  \sqrt{ \lVert v \rVert_\varSigma^2 + \frac{1}{\lVert \varSigma^{-1}\boldsymbol{1} \rVert_\varSigma^2} } } \\
\text{subject to}&\quad v \in K = \{\, x\in\mathbb{R}^N \mid \langle \varSigma^{-1}\boldsymbol{1}, x\rangle_\varSigma = 0\,\}
\end{aligned}

ただし

s = \varSigma^{-1}(\mu - r \boldsymbol{1})

だったことを思い出しておきましょう(*_*;
（その１参照）

今日は第２のステップです！
今日のテクは非常によく使われる常套手段ですよー

一般に，任意のベクトルはある部分空間とその直交補空間の元の和で
一意に表現できることが知られています．
そこで s を K とその直交補空間 K^⊥ の元に分解しましょう～
後々ご利益がわかるとおもいます(^_^;)

さて，分解の仕方は簡単なのですが結果だけ書くことにします：

\begin{aligned}
s &= q +\underbrace{\frac{\langle \varSigma^{-1}\boldsymbol{1}, s\rangle_\varSigma}{\lVert \varSigma^{-1}\boldsymbol{1}\rVert_\varSigma^2}\varSigma^{-1}\boldsymbol{1}}_{\in K^\perp}\\
q &= \biggl( s - \frac{\langle \varSigma^{-1}\boldsymbol{1}, s\rangle_\varSigma}{\lVert \varSigma^{-1}\boldsymbol{1}\rVert_\varSigma^2}\varSigma^{-1}\boldsymbol{1}\biggr) \in K
\end{aligned}

右辺が s であることは自明ですね．．．
また q が K の元であることも簡単に確認できます．

この表現を f の分子第一項に代入して
v が Σ^-11 と直行することに注意すると

f(v) = \frac{ \langle q, v \rangle_\varSigma + \frac{\langle s, \varSigma^{-1}\boldsymbol{1} \rangle_\varSigma}{\lVert \varSigma^{-1}\boldsymbol{1} \rVert_\varSigma^2}
 }{  \sqrt{ \lVert v \rVert_\varSigma^2 + \frac{1}{\lVert \varSigma^{-1}\boldsymbol{1} \rVert_\varSigma^2} } }

になります．
（分子の第一項の s だった部分が q ∈ K に変わりました）

さて，ここまで来たらあと一息です！
v ∈ K を大きさと角度（内積）に分けて考えましょう！
今 v の長さ（ここでは f の分母に現れるノルムのこと）を固定して
方向をいろいろ変えてみましょう～
すると，明らかに f の分子は v が
q と同じ方向を向いている時のほうが大きいですよね！
よって v としてはスカラー α ≥ 0 を用いて v = αq ∈ K
となる v だけ考えればよいことになっちまいます！！

ちょいメモ：
ここで s を K の方向 q とその直交方向に分解したことが生きてます
というのも，もし分解せずに同じ議論を行うと
v = αs が良いってことになっちまいますが
残念ながら s ∈ K でない限り αs ∉ Kです…
これじゃ v ∈ K という制約が満たされませんぜ．．

さて，v = αq を f(v) に代入して α ≥ 0 の関数に書き直すと…

\begin{aligned}
g(\alpha) &= f(\alpha q)\\
 &= \frac{ \alpha\lVert q\rVert_\varSigma^2 + \frac{\langle s, \varSigma^{-1}\boldsymbol{1} \rangle_\varSigma}{\lVert \varSigma^{-1}\boldsymbol{1} \rVert_\varSigma^2}
 }{  \sqrt{ \alpha^2\lVert q \rVert_\varSigma^2 + \frac{1}{\lVert \varSigma^{-1}\boldsymbol{1} \rVert_\varSigma^2} } }
 \end{aligned}

になります！
ここまで来たらあとは α ≥ 0 以外は定数だから
微分でもすりゃー高校生だって解けちゃいます！


疲れましたね…
次回はこいつを微分して決着をつけましょう！

それでは
(@^^)/~~~