2016年5月24日火曜日

確率最適化で非線形 SDP を解く

arXiv に SDP 関係の論文として
Faster Projection-free Convex Optimization over the Spectrahedron
http://arxiv.org/abs/1605.06203
が出てきていたので、大まかにチェック。

解きたい問題としては、 spectrahedron $\{ X : X \succeq O, tr(X) = 1\}$ 上で非線形の目的関数 $f(X)$ を最小化する最小化問題。
これについては、projected gradient method が既に提案されているが固有値計算が重たいので、それを回避する計算手法を検討している。

アイデアとしては、$x x^T$ の rank-1 行列を確率的に選んで、その方向での $f(X)$ の勾配を使って計算していく、という確率最適化計算手法になっている。
解析としては、どれくらいの反復が必要かという見積もりが中心。

数値計算結果としては、やはり反復をしても、あまり精度は得られていない様子。高精度な計算よりも、ある程度大雑把に計算結果を知りたいときになど用いるのが良さそう。ただし、projected gradient method との計算比較が載っていなかったりするので、それほど性能が良くない可能性もあり。

確率最適化の論文としては、なかなかに面白いと思う。


2016年5月20日金曜日

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. 5節の最後のあたりに、"the next section investigates to incorporate a sparse learning technique" とありつつ、6節の内容が違う内容になっており、sparse learning とどう関係してくるのか、気になるところ。

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

2016年5月17日火曜日

量的遺伝学の論文読み

最近、空き時間を見つけて量的遺伝学の論文を読んでいる。

ある論文では、凸2次最適化問題を simulated annealing で解いていたりする。

数理最適化の手法を用いれば、こういった分野にも貢献できるのでは、と思って論文を読んでみると、いろいろと面白い。


2016年5月2日月曜日

内点法の探索方向計算に Krylov 空間 の反復解法を利用した論文


Optimization Online のサマリーをチェックしていたところ、内点法の探索方向計算に Krylov 空間の反復解法を利用した論文が出てきていた。

Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning
http://www.optimization-online.org/DB_HTML/2016/04/5421.html

基本的には、「数値計算分野でできた解法を内点法計算に組み込んだ」というあたりがメインのアイデアになっている。

面白いのは、条件数が悪くても解ける、というところ。内点法だと反復が進むと条件数が著しく悪くなるが、この手法だと 10^80 といった条件数でも計算ができている。
また、SDPT3 などとも比較をしている。

もう少し詳しく知りたいところとしては、
  • AA^T の構造をどれだけ上手く活用して反復計算をしているか?(たとえば、AA^T = M-N の分解にどう利用できているのだろう?これが分かると、もっとうまい活用法がわかる?)
  • 数値実験で SDPT3 などを呼ぶ際に CVX を用いているが、これのオーバーヘッドはどれくらいだろう?SDPの場合は、CVX での変換が効率的でない場合があって、CVX で変換した場合と手動で SeDuMi フォーマットに変換した場合では10倍以上の計算時間の差があったりする。ただ、LP の場合は、それほどの大きな差は出てこないことも考えられるので、このあたりを把握できると CVX がどういうときに使い勝手がいいのか、など把握できそう。
といったあたり。