Optimization beyond Prediction: Prescriptive Price Optimization

Binary Quadratic Problem を SDP 緩和で解く、という内容が arXiv に新しく出てきていたので、内容をチェックしてみた。

URL としては、https://arxiv.org/abs/1605.05422

以下に気付いた点をメモ代わりに書いておくことにする。

1. binary 変数の設定の仕方が面白い。自分が行っているところにも、この手法を利用してみようと思う。
2. SDP 緩和の評価が比較的わかりやすいところが載っているが、このあたりはもっと詳しく解析する方法が載っている論文もあるので、使えるかもしれない
3. 目的関数が convex の最大化なので、整数制約だけでなく凸性がない点も難しさがあるところ。ただ、数値実験結果は良好なので、目的関数に現れる行列（共分散行列）の性質がいいのだと思われる。
4. 定式化されている SDP は内点がないので、主双対内点法だと数値的不安定性が現れやすいと予測できる。数値実験では M = 250, K = 5 で行列のサイズが 1250x1250 と小規模なところになっているが、おそらく 5000x5000 あたりの中規模問題から数値的不安定性がシリアスになってくる。 データにも依存するけど、SDPA なら epsilonBar を若干大きくして (1.0e-4 など)、数値的不安定性を回避したほうがいいかもしれない。
5. 数値実験を 72 core のマシンでありながら 1 core でしか行っていないので、SDPA を 72 core で実行したらどうなるか、気になるところ。
6. ５節の最後のあたりに、"the next section investigates to incorporate a sparse learning technique" とありつつ、６節の内容が違う内容になっており、sparse learning とどう関係してくるのか、気になるところ。

などが、気がついた点。

内容としては面白かったし、１番の点については、あとで自分の研究にも実装してみようと思う。