最適化楽屋話#6 ポートフォリオ最適化問題

Numerical Optimizer 開発責任者の田辺隆人でございます。　 　

フィッティングの際の説明変数はできるだけ少なくしたい（L1正規化という手法が、ゆるくこのモチベーションを実現する方法ですね）、とか、ポートフォリオ最適化において、最適ポートフォリオを構成する銘柄を絞りたい、とか、数理最適化を実務に適用しようとすると自然に現れるニーズはいくつもありますが、それらを数理最適化モデルで表現すればいつも簡単に答が求まる、とは限りません。

上に挙げた「答の中の0を増やしたい、0にならないコンポーネントの数を制限したい」というニーズはよく現れるが、厳密に解くのにかなり手間がかかる点でトップランクに属し、複数のアプローチが提案されています。スタンダードなのは0-1整数変数を使って表現する方法でしょうか。例えばポートフォリオ最適化のケースで、例えば5銘柄に絞りたいということであれば

Variable x(index=i);   // 組み入れ比率
IntegerVariable delta(index=i,type=binary); // 銘柄を選ぶかどうかの0-1変数
0 <= x[i] <= delta[i]; // 組み入れ比率 x[i] と delta[i] の関連付け
sum(delta[i],i) <= 5;  // 銘柄数の制約

といった定式化が良く知られていて、我々もサポートでおすすめしたりします（類似の定式化技術はこちらにまとまっていますのでよろしければご参照ください）。0-1整数変数を導入したモデルは、通常分枝限定法というフレームワークを用いて答を求めることが行われますが、大規模、あるいは非線形な問題では大きな計算機リソースを所要するため、手軽に適用できない場合もあります。

つい先日ですが、これを別の方法でモデル化する手法が提案されているのを知りました（論文はこちら）。[0,1] を動く、$y$ という連続変数を使って（$y[i] = 0$ ならば $x[i]$ が正、となるので上の $delta[i]$ とは逆の意味になります）

Variable y(index=i);
0 <= y[i] <= 1; // y は [0,1] の間を動く
x[i]*y[i] == 0; // y[i] の意味付け
sum(y[i],i) >= n - 5; // n は全銘柄数

と一旦書き直し、さらに非線形な制約（$x[i]*y[i]$）をより扱いやすい形に変形してパラメータを調整しながら反復的に解く、というものです。パラメータを調整して到達する点（局所解ではありますが）の理論的な性質が示されているなど実に興味深い内容です。
こんな具合に、数理最適化は同じ意味でも複数の定式化の方法があり、それをうまく活かすのも適用のノウハウの一つです。ポートフォリオ最適化で選ばれる銘柄の数を限るというケースでは、この方法以外にも数理最適化用語集の記事で紹介している別アプローチがあったりもします（二次計画問題の性質を利用して、分枝限定法を使わずに厳密解を効率良く得る）。　
　
どんな大規模問題、あるいは非線形な問題でも、0-1整数変数を入れてモデル化して分枝限定法のフレームワーク（壮大な「場合分け」）を適用すれば、時間がかかるかもしれないけれど厳密な結果を出すことはできます。普通ならばここでおしまいになると思うのですが、そこに飽き足らずに、「厳密でなくてもよいのでより速く結果が欲しい」、といったニーズに導かれてさらに研究がなされるところが、数理最適化の面白いところだったりするなあと思います。こういったコツやノウハウといったものを、今後のセミナーの場などでどしどし発信してゆきたいと考えています。

ポートフォリオと言えば、日程は少々先ですが、2016/11/22に金融工学セミナーを開催することが決定しました。私も講師を務めます。どうかよろしくお願いいたします。