Quantum annealing for you 03

ポートフォリオ最適化

株価データの読み込み

import pandas_datareader.stooq as stooq

株価データとその計算結果の送受信

D-Waveに計算を送るのは時間がかかる…実はAmazonウェブサービスでOregon regionを選択、そこから計算を送ると如実に高速化できます。

共分散行列

\[\frac{1}{N} \sum_t (w_{it} - \bar{w}_i)(w_{jt}-\bar{w}_j)\]

平均からどれくらいズレるかを出したのち、それらを違う要素について掛け合わせます。これにより、違う銘柄が同じ傾向にあるのか、違う傾向にあるのかを見ることができます。

ポートフォリオ最適化の未定乗数

未定乗数が大きすぎる(wが小さすぎる)ため、最適解が出ない。
量子アニーリングでは\(2^N\)の中から1つの状態を選ぶことが得意…罰金法を使うと精度が下がる(無駄なところを探してしまう)ため、罰金法は量子アニーリングと相性が悪いです。制約条件が多いならば、アニーリングにやらせてはいけません(既存の数理最適化ツールを使うことをお勧めします)。

選択からグループ分けする問題

2=(0, 1, 0, 0), 3=(0, 0, 1, 0)のようなベクトルに変換をします。このようなOne-hot encodingは効率が悪い(ただし、人間にはわかりやすい)です。器用な古典コンピュータでビット数を削減し、量子アニーリングに入れるというのが良い戦法でしょう。
最初は罰金法を使って定式化、最後にはそれを無くす手法を考えます。
\(\sum_{i=1}^N \sum_{k=1}^N \sum_{\ell=1}^N x_{ik} x_{i\ell}\)のような場合には、\(x_{ik}\)を\(i = (1, 2, \dots, N), (N+1, N+2, \dots N+N), (2N+1, 2N+2, \dots, 2N+N)\)のようにして1次元ベクトルに変換します。
精度を高められるというのはCPUで長い時間使うというのは良いこと。QPUで出した解を参考にCPUで良い解を出す、というのがHybridの解き方です。
grobi optimizerという最適化ソルバーがあります。速い。2次形式になるとD-Waveに勝てないものもあります。
量子アニーリングに解かせやすい定式化、grobiに解かせやすい定式化などがあります。

量子アニーリングが使えるところ

もうすでに最適化されているようなところはやらない方が良いでしょう(すでに高速化・成熟しているため)。今まで最適化・デジタル化されていないようなところを攻めるのが良いでしょう。
罰金法は使わない方が良いでしょう。
離散最適化なので、凸ではありません。その時点で難しいです。制約条件(線形和がいくつになる)も加味されるとより難しくなります。grobiなどでは悪い解はすぐ捨てるなどの処理ができるので利点はあります。そこまで制約条件が厳しくないようなものではアニーリングでも高速に解けるでしょう。
離散最適化問題の場合、勾配がないため一度連続に緩和します。そこから勾配を使って連続最適化問題を解いた後で、離散最適化に持っていきます。