Critical-Line Algorithm for Portfolio Optimization:アルゴリズム
二つのサブセットの集合$${{\bf F}}$$と$${{\bf B}}$$からの資産の入れ替えは、転換点で起こる。よって、それぞれの転換点において$${{\bf F}}$$の資産構成は違い、
$${{\bf V_F \omega_F} + {\bf V_{FB}\omega_B} - \lambda {\bf \mu_F} =\gamma {\bf 1_F}}$$
は異なる$${{\bf F}}$$で成立している。
転換点を通過する時に、$${{\bf F}}$$から一つの資産要素を削除、または追加が行われる。
アルゴリズムでは、高い期待リターンを持つ転換点の$${\lambda_t}$$から、次に低い期待値リターンの転換点$${\lambda_{t+1}}$$へ移り、それ以上に低い期待リターンの転換点が見つからなかった場合に終了する。
初期解
初期解は制約のある最少分散フロンティア上の階で、最も高い期待リターンを持つことから、$${\mu}$$を高い順に並べ、全資産の重みを下限に設定する$${\omega_i=l_i}$$。これから、期待リターンの最も高い資産の重みを増やしていく。これが上限に達し、$${{\bf \omega}^T{\bf 1} < 1}$$であれば、次の資産を増やしていく。これを$${{\bf \omega}^T{\bf 1} = 1}$$になるまで繰り返す。
よって、初期階の構造は、最初の資産重みが上限で最後の資産重みが下限である。その中間にある一つの資産重みが$${l_i < \omega_i < u_i }$$を満たし、$${{\bf F}}の要素となる。
Iteration
ある転換点から次の転換点に移る場合、Case $${{\rm i}}$$)$${{\bf F}}$$から$${{\bf B}}$$へひとつの資産が移る、Case $${{\rm ii}}$$）$${{\bf B}}$$から$${{\bf F}}$$へひとつの資産が移る、この二つのシナリオが考えられる。
Case $${{\rm i}}$$: $${{\bf F}}$$から$${{\bf B}}$$へひとつの資産が移る。
時点$${t}$$での転換点での$${\lambda}$$を、$${\lambda_{c}}$$と表す。ここで、$${\lambda_c\equiv \lambda_t >\lambda > \lambda_{t+1} }$$である。そして、$${{\bf F}}$$をこの転換点よりも微小に小さい転換点で制限内にある資産とする（以下、自由資産と呼ぶ）。
この$${{\bf F}}$$要素の$${k}$$資産は、
$${{\bf \omega_F} = - {\bf V_F} ^{-1} {\bf V_{FB}\omega_B } + \lambda{\bf V_F}^{-1} {\bf \mu_F} +\gamma {\bf V_F}^{-1}{\bf 1_F}}$$
を満たしてる。
$${\gamma=\displaystyle{-\lambda \frac{{\bf 1_F}^T{\bf V_F}^{-1}{\bf \mu_F}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}} + \frac{1-{\bf 1_B}^T{\omega_B} + {\bf 1_F}^T{\bf V_F}^{-1}{\bf V_B \omega_B}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}}}}$$を代入して、$${\lambda}$$の関数として表すと、
$${{\bf \omega_F} =\displaystyle{ - {\bf V_F} ^{-1} {\bf V_{FB}\omega_B } - \frac{1-{\bf 1_B}^T{\omega_B} + {\bf 1_F}^T{\bf V_F}^{-1}{\bf V_B \omega_B}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}}{\bf V_F}^{-1}{\bf 1_F} }}$$ $${\displaystyle{ -\lambda \frac{{\bf 1_F}^T{\bf V_F}^{-1}{\bf \mu_F}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}} {\bf V_F}^{-1}{\bf 1_F} + \lambda{\bf V_F}^{-1} {\bf \mu_F}}}$$
よって、$${{\bf F}}$$の各資産の重みは、$${\displaystyle{\frac{\partial \omega_{{\bf F}_i}}{\partial \lambda} > 0}}$$であれば、$${\omega_{{\bf F}_i}}$$は$${\lambda}$$が減少すれば減り、下限に達した時に$${{\bf F}}$$から出て$${{\bf B}}$$に入る。同様に、$${\displaystyle{\frac{\partial \omega_{{\bf F}_i}}{\partial \lambda} < 0}}$$の時は、$${\lambda}$$の減少で増加し、上限に達した時に$${{\bf F}}$$から出て$${{\bf B}}$$に入る。
資産$${i}$$が$${{\bf F}}$$から出て$${{\bf B}}$$に入り、$${u_i}$$もしくは$${l_i}$$の値$${b_i}$$を取る$${\lambda}$$の値を$${\lambda_i}$$と書くと、
$${b_i=\displaystyle{ -( {\bf V_F} ^{-1} {\bf V_{FB}\omega_B })_i - \frac{1-{\bf 1_B}^T{\omega_B} + {\bf 1_F}^T{\bf V_F}^{-1}{\bf V_B \omega_B}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}}({\bf V_F}^{-1}{\bf 1_F})_i }}$$ $${\displaystyle{ -\lambda_i \frac{{\bf 1_F}^T{\bf V_F}^{-1}{\bf \mu_F}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}} ({\bf V_F}^{-1}{\bf 1_F})_i + \lambda_i({\bf V_F}^{-1} {\bf \mu_F})_i}}$$
これから、
$${C_i ={\bf 1_F}^T{\bf V_F}^{-1}{\bf \mu_F} ({\bf V_F}^{-1}{\bf 1_F})_i - {\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}({\bf V_F}^{-1} {\bf \mu_F})_i }$$として、
$${\lambda^{(i)}=\displaystyle{\frac{1}{C_i}[ (1-{\bf 1_B}^T{\bf \omega_B} + {\bf 1_F}^T{\bf V_F}^{-1}{\bf V_{FB} \omega_B})({\bf V_F}^{-1}{\bf 1_F})_i }}$$
$${ \displaystyle{ -{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}\left(b_i +({\bf V_F} ^{-1} {\bf V_{FB}\omega_B } \right)_i )] }}$$
また、
$${\displaystyle{\frac{\partial {\bf \omega_F}}{\partial \lambda}= {\bf V_F}^{-1}{\bf \mu_F} - \frac{{\bf 1_F}^T{\bf V_F}^{-1}{\bf \mu_F}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}} {\bf V_F}^{-1}{\bf 1_F}}}$$
より、
$${\displaystyle{\frac{\partial \omega_{{\bf F}_i}}{\partial \lambda}=( {\bf V_F}^{-1}{\bf \mu_F})_i - \frac{{\bf 1_F}^T{\bf V_F}^{-1}{\bf \mu_F}}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}}( {\bf V_F}^{-1}{\bf 1_F})_i=\frac{C_i}{{\bf 1_F}^T{\bf V_F}^{-1}{\bf 1_F}} }}$$
と書けることから、$${C_i > 0}$$であれば、$${b_i=u_i}$$で、$${C_i < 0}$$であれば、$${b_i=l_i}$$になる。
ここで、$${{\bf F}}$$の要素数$${k=1}$$の時は、明らかに$${C_i=0}$$となるため、資産の出入りは起こらない。同様に、全ての資産の期待リターンが同じな場合も$${C_i=0}$$である。
次に資産が$${{\bf F}}$$を抜ける次の転換点の$${\lambda, \ \lambda < \lambda_c}$$は、
$${\lambda_{in}=\max_{i \in F}\{\lambda^{(i)}\}}$$で、$${k=1}$$の時は$${\lambda_{in}}$$は存在しない。
$${\lambda_{in}}$$が存在し、かつ$${\lambda_c > \lambda > \lambda_{in}}$$で、$${{\bf B}}$$に移る資産がないとき、ある資産が$${{\bf F}}$$に入ってくるケース（Case $${{\rm ii}}$$）となる。
Case $${{\rm ii}}$$: $${{\bf B}}$$から$${{\bf F}}$$へひとつの資産が移る。
$${{\bf \mu}^T{\bf \omega}}$$が減少しているとき、$${{\bf B}}$$にあった資産が$${{\bf F}}$$に入ってくる状況が出てくる。この時のポートフォリオは、上記のCase$${{\rm i}}$$と同じく、$${{\bf F}}$$と$${{\bf F}}$$が再定義される転換点である。
この時、移動する資産を$${i}$$、新しい$${{\bf F}}$$と$${{\bf B}}$$を以下のように定義する。
$${{\bf F}_i={\bf F} \cup \{i\}}$$
$${{\bf B}_i={\bf B} \setminus \{i\}}$$
と書く。
Case$${{\rm i}}$$と同様に、$${{\bf B}}$$にあった資産が$${{\bf F}}$$に入ってくる時の$${\lambda^{(i)}}$$は$${{{\bf F}_i}$$と$${{{\bf B}_i}$$を使って計算される。
$${\lambda^{(i)}=\displaystyle{\frac{1}{C_i}[ (1-{\bf 1_B}_i^T{\bf \omega_B}_i+ {\bf 1_F}_i^T{\bf V_F}_i^{-1}{\bf V_B}_i{\bf \omega_B}_i)({\bf V_F}^{-1}{\bf 1_F})_i }}$$
$${ \displaystyle{ -{\bf 1_F}_i^T{\bf V_F}_i^{-1}{\bf 1_F}_i\left(b_i +({\bf V_F}_i ^{-1} {\bf V_{F_iB_i}\omega_B }_i \right)_i )] }}$$
ここで、$${b_i = ({\bf \omega_F}_i)_i=\omega_i}$$とし、上限から$${{\bf F}}$$に移る場合は$${b_i=u_i}$$で、下限から$${{\bf F}}$$に移る場合は$${b_i=d_i}$$である。
$${\lambda_c}$$より小さい中での最大の$${\lambda^{(i)}}$$を見つけるためには、$${{\bf B}}$$にいる全ての資産の$${\lambda^{(i)}}$$を計算し、
$${\lambda_{out}=\max_{i\in {\bf B}}\{\lambda^{(i)}| \lambda^{(i)} < \lambda_c\}}$$
とする。
もしも$${\lambda^{(i)} < \lambda_c}$$なる資産$${i}$$が見つからなかったら、$${\lambda_{out}}$$は存在しない。
次の転換点を見つける
Case$${{\rm i}}$$とCase$${{\rm ii}}$$のどちらかが起こるかは、$${\lambda_{in}}$$と$${\lambda_{out}}$$を比べ、大きい方を取る。すなわち、$${\lambda_{in} > \lambda_{out}}$$であれば、Case$${{\rm i}}$$が起こり、$${{\bf F}}$$から資産$${i}$$が$${{\bf B}}$$に移る。
どちらかの解しか見つからなかった場合は、見つけられた方を転換点とし、$${{\bf F}}$$を、$${{\bf F}\setminus\{i\}}$$か$${{\bf F}_i}$$に、$${{\bf B}}$$を、$${{\bf B}\cup\{i\}}$$か$${{\bf B}_i}$$に置き換え、$${\lambda_c=\lambda_{new}}$$にする。
どちらの解も見つけられなかった時に、アルゴリズムは終了する。
結果が正しければ、最後に得られた重みは初期解と逆になっており、期待リターンの大きさで並べ替えると、最初の重みは下限で、最後の重みから上限の重みとなり、残りの成分は$${l_i < w_i < u_i}$$になっている。