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

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

前回は制約を満たす 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 以外は定数だから
微分でもすりゃー高校生だって解けちゃいます！


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

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

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

前回のつづきです

前回は Σ を間に挟んだ内積を定義して
特殊なケースでの最大値を求めましたね～
今日はそうでない場合を考えましょう！
（実はこのアプローチなら前回の場合を含む形で解けます）

さて，問題が解く最初のステップは，
制約 1^Tw = 1 を満たす wを扱いやすい形で表現することです．
このために，次の集合を導入しましょう：

K = \{ \, v \in \mathbb{R}^N \mid 
\langle \varSigma^{-1} \boldsymbol{1},
v \rangle_\varSigma = 0 \, \}

これは Σ^-11で張られる線形部分空間の直交補空間です．
（内積 ⟨•,•⟩_Σ を持つヒルベルト空間の意味でです）

集合 K を導入するメリットは，もしある w が
制約 1^Tw = ⟨ Σ^-11, w⟩_Σ = 1 を満たすとすると
任意のv ∈ K に対して w + v もまた制約を満たすということです．
従って制約を満たす代表の w を一つ見つけたら
あとは w + v, v ∈ K の形で制約を満たすすべてのwを表現できます

そこで制約を満たす代表の w を見つけましょう！
これは超簡単で， Σ^-11 のスカラー倍で制約を満たすよう調整します．
つまり次のベクトルを代表に選びましょう：

\frac{\varSigma^{-1}\boldsymbol{1}}
{\lVert \varSigma^{-1}\boldsymbol{1} 
\rVert_\varSigma^2}

以後 v ∈ K をパラメータとして

w = \frac{\varSigma^{-1}\boldsymbol{1}}
{\lVert \varSigma^{-1}\boldsymbol{1} 
\rVert_\varSigma^2} + v, \quad v \in K

の w を考えていきましょう．

上の形の w を θ に代入して問題を パラメータv
の問題に書き換えると次のようになります：

\begin{aligned}
\text{maximize} &\quad f(v) = \theta\biggl(
\frac{\varSigma^{-1}\boldsymbol{1}}
{\lVert \varSigma^{-1}\boldsymbol{1} 
\rVert_\varSigma^2} + v \biggr) \\
&\quad\quad\quad=
 \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
\end{aligned}

f の分母を導出する際に，v と Σ^-11が直交することを用いたことに注意してください．


関数は複雑になりましたが，少し進展したんですよ(-_-;)
とりあえず今日はこの w から v への変数変換を行ったとこまでにします．

それではまた～