0-1 変数に Sum of Squares を使ってみると

$x \in \{0,1\}$ という制約条件は、普通に連続緩和をすると $ 0 \le x \le 1$ になる。

これを、$-x^2(x-1)^2 \ge 0$ として、Sum of Squares の緩和をするとどうなるか。

得られる緩和は $ 0 \le x \le 1$ となって、連続緩和と強さが変わらない。

なるほど、なるほど。なかなかに面白い結果だ。

Julia のエディタは Atom より Emacs のほうが快適

この前調べていた Julia のエディタだが、Atom よりも Emacs のほうが快適に使えることに気がついた。

基本的には、julia-mode.el をダウンロードして、
https://github.com/JuliaLang/julia-emacs/blob/master/julia-mode.el
説明に書いてあるように以下の内容を適宜修正してから .emacs/init.el に追加する。

(add-to-list 'load-path "path-to-julia-mode")
(require 'julia-mode)


ちなみに、julia-mode.el だと、M-x run-julia で Julia の REPL が Emacs 内で実行できるけど、これだとセミコロンでのシェルモードへの切り替えが上手くいかないようなので、REPL は別のターミナルで起動していた方が使いやすい。

あと、非常に便利なところとしては、ギリシャ文字などの入力にも対応しているところで、
\alpha[Tab]
と TeX の記号で Tab を押すとαに自動変換してくれる。「あるふぁ」と入力しなくても大丈夫。

もう一つ便利な点としては、インデントを自動調節してくれる点。Atom でも追加されている機能だが、Emacs で入力するほうがインデントの自動調節が素早く行われる。
（このあたりのスピードの差がどこから来るのかは、まだ良く調べてないけど。）

Julia を Atom のエディターで試してみる

Julia の統合開発環境っぽかった Juno が Atom ベースになっていたので、どんな様子かを試してみた。
とりあえず、現状で感じたところのメモ書き。

• Atom のインストール自体は普通にできる。
• Atom に Julia の設定を導入するのも、uber-juno のパッケージのインストールだけなので、簡単にできる。https://github.com/JunoLab/uber-juno/blob/master/setup.md の通り。
• メッセージが出る通り、Atom でJulia の設定を導入すると、Atom を起動しなおしたときに Julia のパッケージの設定が入って、これが結構時間がかかる（３０分ぐらい？）。
• テーマが暗くて文字が読みづらいが Light にテーマを変更したら読みやすくなった。
• カッコを書いたときに自動的に閉じカッコが入ると入力の邪魔になるので、ATOMで開き括弧を入力した時に、閉じ括弧を自動で入力するのをやめる を参考にする
• ギリシャ文字などは自動で候補が出てくるので、これは便利。例えば \alpha で alpha を UTF-8 で入力できる。
• Autocompletion が出てくるのが速すぎるので、autocomplete-plus パッケージにある Delay Before Suggestions Are Shown を 2 秒にしてみる
• Console がどのペインなのか覚えていないので、ペインの位置を変えても毎回設定しなおす必要がある
• Run File のボタンを押してから、実行が始まるまでにだいぶ時間がかかる (Julia のコンパイルも時間がかかるが、それだけではない様子。）
• Run File で実行して、そのあとでファイルを修正保存して再度 Run File を実行しても、以前のファイルの内容で実行される
• エラーメッセージはポップアウトで表示されてかっこいいが、ここをクリックしてもエラーの行に自動的に行ってくれるわけではない

たぶん、現状では Matlab の統合開発環境よりも遅い感じ。
Atom がモッサリという印象があって、そこに Julia を乗っけているのでだいぶ大変か。
Atom は様々なことができるようになっているが、現状ではスピードが遅くて、Emacs よりも遅い印象になっている。
数理最適化のプログラムを組んでいくには、現状では大変な感じだ。

でも、面白い機能も多いので、スピードが改善されてメモリ消費量が抑えられたら、こっちに移るのもありだと思う。

確率最適化で非線形 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 との計算比較が載っていなかったりするので、それほど性能が良くない可能性もあり。

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

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 とどう関係してくるのか、気になるところ。

などが、気がついた点。

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

量的遺伝学の論文読み

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

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

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

内点法の探索方向計算に 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 がどういうときに使い勝手がいいのか、など把握できそう。

といったあたり。