Stochastic optimization の基本的なキーワード

A Tutorial on Stochastic Programming

Alexander Shapiro and Andy Philpott

http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/TutorialSP.pdf

を参考にすると、 Stochastic Optimization 関係のキーワードとしては、

• Two-stage optimization
• 複数のシナリオを発生させてからの最適化
• Sample Average Approximation (SAA)
• chance constraints
• VaR (Value at Risk)
• C-VaR (Conditional Value at Risk)
• Robust Optimization

といったあたりが重要。

Debian では -fPICが非推奨とのことらしい

Linux では、lib???.a ファイルは重要なファイルであるが、Debian ではこの lib???.a を作る際に -fPIC を使うのが非推奨、とのことらしい。
これによって、たとえば apt-get でインストールされる libABC.a というライブラリを使用して libXYZ.so などの shared library の作成ができない、ということが標準のようである。

したがって、たとえば、octave の *.mex を作成するには、*.mex の実態が shared library であることから、libABC.a などの利用に制限がかかるのが標準、ということらしく、apt-get でインストールすのとは別途 libABC.a をソースからコンパイルする必要がある。

素晴らしい対応の Python Extension の Unofficial Windows Binary

Windows での python の状況をチェックしていて、
Unofficial Windows Binary
http://www.lfd.uci.edu/~gohlke/pythonlibs
を利用し始めていたが、今までの CVXOPT バイナリにはバグが残っていて、自分のプログラムではエラーが頻発して使い物にならなかった。

このバグは Netlib の BLAS/LAPACK をリンクしているためであって、MKL とリンクするbinary はバグを取り除けるが CVXOPT のライセンスで配布ができないとのことであった。
そこで、OpenBLAS をリンクすればライセンスの問題は回避できるかも、というメールを送ってみた。

すると、わずか１時間後には CVXOPT が OpenBLAS とリンクされた binary がアップロードされていた。
http://www.lfd.uci.edu/~gohlke/pythonlibs/#cvxopt
しかも、複数の python バージョンで、である。

驚くべき素晴らしい対応すぎて、自分も見習いたいものである。


ちなみに、今回の binary で自分のプログラムは問題なく実行できるようになった。
Conic Programming の研究では、Matlab を使わなくても python で 90% 以上のことができているのでは？と思うが、そうなってきているのも、こうやって binary などをメンテナンスしてくれている方がいるからこそである。

Google の OR-Tools

Google にもオペレーションズリサーチ関係のソフトウェアパッケージがあるらしく、or-tools という名前になっている。

https://code.google.com/p/or-tools/

ページを見てみると、どうやら入っているのは

• 制約プログラミング
• トラック配送問題
• GLPK, Gurobi, SCIP などのインターフェイス
• ナップサック問題
• グラフ問題（最短路計算、最大流問題など）

ということの様子。

インストールについては、現段階ではソースからのビルドのみのようで、まだまだ発展途上の段階のようでもあるが、そのうちに使い道が出てくるかもしれないので、少し注目しておくことにする。

Matlab から python への移行を検討し始める

最近、Matlab の周辺環境がいろいろと使いにくくなりつつあって、市販ソフトウェアとしての限界が出てきつつあるので、python への移行を検討し始めている。

とりあえず検討すべきこととしては、
1. SDPA などの主力ユーザは Windows なので、Windows でどれくらい簡単に利用できるかを把握する（python は Linux 中心で発展してきているので、Linux については特に問題ないかと推測している）
2. Matlab からどれくらい移行が大変かを確認する。文法的な差異はそれほど問題ではないが、BLAS/LAPACK や疎行列へのアクセスがどれくらいできるのか、という点が気になるところ。

永久機関と余弦定理

SIAM News の記事に、永久機関と余弦定理が関係していることが書かれている記事があった。

http://sinews.siam.org/DetailsPage/tabid/607/ArticleID/359/Perpetual-Motion-and-the-Theorem-of-Cosines.aspx

「永久機関が存在しない、ということで式を立てると、そこから余弦定理が導ける」といういもので、意外なところの結びつきが面白い。

Windows 上での Python モジュールのビルド

Windows 上で Python モジュールをどのようにビルドするのか、という内容が、

http://docs.python.jp/2/extending/windows.html

にまとめられている。
Matlab の Mex ファイルも、Python モジュールと同様に実体は DLL ファイルなので、とても参考になる。(Matlab の場合は、拡張子を mexw32, mexw64 としている）

SDPA-M の Windows 版は Linux 上でクロスコンパイルしているが、上記ページの「4.2. Unix と Windows の相違点」が勉強になる。

主双対内点法でまだ解析されていないこと

SDPA や SeDuMi は主双対内点法を実装しているが、これらのソフトウェアを実行していると実際の性能と理論的枠組みには大きなズレがあることもわかる。特に重要な点として、

１．主双対内点法は最適解の近くだと２次収束するが、実際のソフトウェアでは数値誤差の影響もあり、１次収束までの動作しか得られない。わかりやすくいうと、C言語の double で実装した場合、主双対内点法では 10^{-8} 程度の数値誤差が出てしまうが、２次収束を開始するのは 10^{-8} よりも小さいところである。（乱数で問題を生成すると問題の性質がよくなり、もう少し早いところから２次収束する傾向が見られやすい。）

２．ところが１次収束する他のアルゴリズムと比較すると、最初の数反復での収束の速さは速く、その後の１次収束するときの係数も小さい。

などがある。
特に２のところは不思議で、理論的な収束としては１反復で duality gap が $$ 1-\sqrt{n} $$ ぐらいの比でしか小さくならないはずであるが、実際に動かしてみるとは 0.1 ～ 0.5 ぐらい出ているのでは？と思える。