Critical-Line Algorithm for Portfolio Optimization:共分散行列の展開　

An Open-Source Implementation of the Critical-Line Algorithm for Portfolio Optimization

https://www.researchgate.net/publication/226987510_Applying_Markowitz%27s_Critical_Line_Algorithm

共分散行列の逆行列

　領域の中を自由に動けるセット$${{\bf F}}$$から、上限値か下限値に固定されるセット$${{\bf B}}$$に移るCase$${{\rm i}}$$と、$${{\bf B}}$$から$${{\bf F}}$$に入るCase$${{\rm ii}}$$のアルゴリズム上の大きな違いは、
Case$${{\rm ii}}$$では、
$${\lambda_{out}=\max_{i\in {\bf B}}\{\lambda^{(i)}| \lambda^{(i)} < \lambda_c\}}$$
において、$${{\bf B}}$$内の資産全てについての$${\lambda^{(i)}}$$計算が必須なことである。この$${\lambda^{(i)}}$$の計算には、$${{\bf V_F}^{-1}}$$が伴う。一般に逆行列の計算は計算負荷が大きく、アルゴリズム性能に悪い影響を与える。
　この逆行列の計算は、Case$${{\rm i}}$$とCase$${{\rm ii}}$$のどちらにも、次の転換値を求めるために要求される。
　しかし、転換点から一つの資産が出ていく/入ってくるだけであるから、$${{\bf V_F}}$$を展開し、新しい逆行列の計算を軽くすることができる。
　$${{\bf A}}$$を$${k \times k}$$の対称行列とし、成分$${k}$$のベクトルを$${{\bf a}}$$、スカラーを$${\alpha}$$とする。
　$${{\bf F}}$$に新たに資産が入ってきた時の$${{\bf V_F}}$$の逆行列は、
$${\displaystyle{\begin{pmatrix}{\bf A} & {\bf a} \\{\bf a}^T & \alpha \\\end{pmatrix}^{-1} = \begin{pmatrix}{\bf A}^{-1} + \beta{{\bf c c}^T}& -\beta {\bf c} \\ -\beta{\bf c}^T & \beta \\\end{pmatrix}}}$$、ここで、
$${\displaystyle{{\bf c}={\bf A}^{-1}{\bf a}, \ \ \beta=\frac{1}{\alpha-{\bf c}^T{\bf a}}}}$$、と与えられる。
　$${{\bf A}^{-1}}$$は資産が入ってくる前の$${{\bf V_F}^{-1}}$$で既知である。よって、必要になる計算は$${{\bf A}^{-1}{\bf a}}$$と、$${\alpha-{\bf c}^T{\bf a}}}$$で、計算オーダーは$${O(k^2)}$$となる。
　同様に、資産が一つ出ていく時の$${{\bf V_F}^{-1}}$$の計算も、逆行列をストレートに計算しなくて良い。
$${\displaystyle{\begin{pmatrix}{\bf A} & {\bf a} \\{\bf a}^T & \alpha \\\end{pmatrix}^{-1}=\begin{pmatrix}{\bf B} & {\bf b} \\{\bf b}^T & \beta \\\end{pmatrix}}}$$
より、この場合、右辺が既知の$${(k+1) \times (k+1)}$$の共分散行列であるから、
$${\displaystyle{{\bf A}^{-1}={\bf B}-\frac{{\bf b b}^T}{\beta}}}$$と与えられる。

上記の方法を使えば、$${\lambda^{(i)}, i \in {\bf B}}$$の$${{\bf V_F}^{-1}_i}$$を、既知の$${{\bf V_F}}$$に置き換えて計算負荷を軽くすることができる。
$${\displaystyle{{\bf V_F}_i = \begin{pmatrix}{\bf V_F} & {\bf a} \\{\bf a}^T & \alpha \\\end{pmatrix}, \ \ {\bf \mu_F}_i =\begin{pmatrix}{\bf \mu_F} \\ \mu_i \\\end{pmatrix}}}$$とかけば、
$${D_i =(1-{\bf a}^T{\bf V_F}^{-1}{\bf 1_F})({\bf 1_F}^{T}{\bf V_F}^{-1}{\bf \mu_F})-(\mu_i - {\bf a}^{T}{\bf V_F}^{-1}{\bf \mu_F})({\bf 1_F}^{T}{\bf V_F}^{-1}{\bf 1_F})}$$
$${\lambda^{(i)}=\displaystyle{\frac{1}{D_i}[ (1-{\bf 1_B}^T{\bf \omega_B} + {\bf 1_F}^T{\bf V_F}^{-1}{\bf V_{FB} \omega_B})(1-{\bf a}^T{\bf V_F}^{-1}{\bf 1_F})}}$$
$${ \displaystyle{ +{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}\left({\bf a}^T{\bf V_F} ^{-1} {\bf V_{FB}\omega_B } -{\bf V_{FB}\omega_B} \right)] }}$$