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 がどういうときに使い勝手がいいのか、など把握できそう。

といったあたり。

bash on Ubuntu on Windows 10

この夏に Windows 10 で Ubuntu の bash が動くようになるようで、gcc や python なども apt-get でインストールできる様子。

グラフィックス周りは当面は実行できないだろうけど、apt-get でインストールができるようになると数理最適化関連のソフトを Windows にインストールするのも格段に便利になるので、利便性が一気に向上するのでは？と思ったりする。

将来的に X が動くようにもなれば、TeX 関係も非常に簡単にインストールできるので、そのあたりも楽になりそう。
（# apt-get install yatex とすると、emacs も TeX も一度にインストールできる。試したことはないが、TeXworks をインストールすると TeX も一度にインストールできるかもしれない。）

CUTEr/CUTEst の Matlab 用ファイル

問題ライブラリ集である CUTEr/CUTEst は、Matlab 用にデータを変換できるツールがあるので、以下の流れに沿うと Matlab 用に一括変換できる。



実際の手順は以下のサイトに書かれている通りである。
http://ccpforge.cse.rl.ac.uk/gf/project/cutest/wiki/

mkdir ~/cuter
cd ~/cuter
git clone https://github.com/optimizers/archdefs-mirror.git
git clone https://github.com/optimizers/sifdecode-mirror.git
git clone https://github.com/optimizers/cutest-mirror.git
git clone https://github.com/optimizers/mastsif-mirror.git
git clone https://github.com/optimizers/maros-meszaros-mirror.git

export ARCHDEFS=${HOME}/cuter/archdefs-mirror
export SIFDECODE=${HOME}/cuter/sifdecode-mirror
export CUTEST=${HOME}/cuter/cutest-mirror
export MYMATLAB=/usr/local

export ARCHDEFS="${HOME}/cuter/archdefs-mirror"
export SIFDECODE="${HOME}/cuter/sifdecode-mirror"
export CUTEST="${HOME}/cuter/cutest-mirror"
export PATH="${SIFDECODE}/bin:${PATH}"
export PATH="${CUTEST}/bin:${PATH}"
export MANPATH="${SIFDECODE}/man:${MANPATH}"
export MANPATH="${CUTEST}/man:${MANPATH}"

export MYARCH="pc64.lnx.gfo"
export MYMATLABARCH="pc64.lnx.gfo"

export MATLABPATH="${CUTEST}/src/matlab:$MATLABPATH"
export MASTSIF="${HOME}/cuter/mastsif-mirror"

cd ~/cuter/cutest-mirror
./install_cutest
  いろいろとメッセージが出てくるので、それに答える
  自分のところでは、(6) PC with generic 64-bit processor を選択して進めた
  あとは、Matlab を利用できるように設定もした
 
cd ~/cuter/cutest-mirror/src/matlab
以下のシェルスクリプトを行う

#!/bin/sh -x
mkdir mastsif
for SIF_FILE in `ls ${HOME}/cuter/mastsif-mirror/*.SIF`
do
    echo Processing $SIF_FILE
    SIF=`basename $SIF_FILE .SIF`
    cutest2matlab $SIF
    matlab -r "prob = cutest_setup(); save('a.mat','prob'); exit"
    mv a.mat mastsif/$SIF.mat
done

これで mastsif に *.mat が出来上がる。
例えば、LUBRIFC.mat を読み込むと
>> load LUBRIFC.mat

prob というデータが入っていて、この中に問題が格納されている。

実際のデータ構造は、
http://tracsvn.mathappl.polymtl.ca/trac/cuter/wiki/NewMatlabInterface
に詳しく書かれている。