arXiv のフォローを外す

今まで arXiv の math.OC カテゴリを RSS でフォローしていたが、このフォローをやめてみることにした。

理由としては、
「面白そうな論文が多すぎて、全部追いかけるのが大変になった」
というところ。
１日に１５本ぐらいずつ登録されているんじゃないか、と思うので１週間に１００本ぐらいになってしまい、情報過多になってしまったので、思い切ってサクッとやめてみることにしてみた。

Google Optimization Tools

RAMP の予稿集を見ていて、あとでチェックしてみようと思ったのが、
Google Optimization Tools
https://developers.google.com/optimization/

どうやら、ざっと見る限り、線形計画問題や整数計画問題のソルバーのインターフェース、およびナップサック問題の解法とネットワーク最適化計算が実装されているようだ。

ずっと以前にネットワーク最適化のソフトウェアを調べたときには、API などがソフトウェアごとにマチマチで、理論的研究成果がソフトウェア実装にどれだけ反映されているのか調べるのが面倒になってしまいギブアップしてしまった。
Google のソフトウェアがデファクトスタンダードになってくれば、理論的研究でも「Google Optimization Tools と比較して何パーセント性能向上」というような数値実験結果が増える方向にいくんじゃないかと思ったりする。



あと、LPやMIPについては既存ソフトウェアへのインターフェースだけ、ってところは気になるところ。既存ソフトウェアで Google が使うには十分なパフォーマンスが得られるのか。あるいは、LP, MIP は Google としては、それほど高性能である必要はないのか。どっちなんだろう。

RAMP１日目雑感

今日は、RAMP１日目、ということで、聞いてきたことの中から、いろいろと思ったことなどを、つらつらと書いておいてみる。


１．Optimality theorems for convex optimization problems
by Gue Myung Lee (以前に、韓国の応用数理学会の会長だったような気がするけど、他人の空似かも）

いろいろな最適性条件を扱っている。
Theorem 4.1 が「constraint qualification が必要ない最適性条件を作っている」ということなので、これがどういうアイデアで実現できているかを把握できれば、他の証明などにも発展できるかもしれない。
また、SOS-convex という概念を扱っている。キーワードとしては面白そうなので、どういった実用例・応用例があるか把握してみたい。

２．Nonsommth semi-infinite multiobjective optimization problem
by Do Sang Kim

無限個の制約がある多目的最適化問題について扱っている。
どうやら efficient と weakly efficient の違いが、最適性条件にも影響しているようだ。
今日の話は最適性条件の理論面が中心だったけど、計算手法としては、
Approximate quasi efficient solutions in multiobjective optimization
http://ssmr.ro/bulletin/pdf/51-2/predamod.pdf
が参考になるようなので、あとでチェックをしてみるといいかと思う。
また、今日の話では、どれだけ高速に計算できるか、などの話はなかったので、そういった視点からみると、何かいいアイデアが浮かんだりするだろうか？

３．From symmetric cone optimization to nonsymmetric cone optimization: Projection onto nonsymmetric cones
by Jein-Shan Chen

対称錐は、self-dual と homogeneous の２条件を満たす錐であって、これらのときに内点法が上手くいくことになっている。
これらの２条件を満たさないような錐のときにどうなるか、ということ。
特に錐への射影を陽に計算する手段を作れるかどうかを、いくつかの錐について議論している。

個人的に思うのは、self-dual と homogeneous のうち、self-dual はいいにしても、homogeneous は物理でいうところの相対性理論と結びつくところだから、こっちを外すのはしんどいかと思う。
homogeneous であって self-dual でないところがどういう構造をしているのか、のあたりが面白そう。

4. Highlight on recent progress for the trust region subproblem and its variants
by Ruey-Lin Sheu

trust-region subproblem は x^T x \le 1 の制約を持つ QCQP だけど、半径１以外の制約にどのような制約が入ってくると、どれだけ難しくなるか、という話。
Iterative reduction procedure という、問題を分割して解く手法を提案している。
あとで細かく論文を確認してみると良さそう。




あと、個人的には、今日の帰り際にRuey-Lin Sheu 先生に挨拶できたのが良かった。
５年前にお世話になっていながら、そのあとに直接お会いできる機会がなかったので、今回挨拶できたのは良かったと思う。

IguanaTeX のバグを回避する

ghostscript のところで set TEMP が効いてなくてバグになっていた現象だが、bat ファイルを挟むことで回避できることが分かった。

まずは、Powerpoint でIguanaTeX タブの「Main Settings」を開く。
ここでは、Absolute が C:\temp とし、gswin32c がC:\Program Files (x86)\gs\gs9.16\bin\gswin32c.exe となっていたとする。

このとき、以下のような bat ファイルを作り C:\Program Files (x86)\gs\gs9.16\bin\gswin32c2.bat とする。

== ここから ==
@echo off
set TEMP=c:\temp
"C:\Program Files (x86)\gs\gs9.16\bin\gswin32c.exe" %*
== ここまで ==
ここの２行目に、上で得た Absolute、３行目に gswin32c.exe の情報を入れる。

こうやってできた
C:\Program Files (x86)\gs\gs9.16\bin\gswin32c2.bat を
「Main Settings」の ghostscript のところに登録する。

こうすると、gswin32c2.bat 経由で set TEMP をはさんで gswin32c.exe を呼び出せるので、バグが回避できる。

IguanaTeX にバグがある

IguanaTeX は、資料作成のときにとても便利である。
というか、IguanaTeX を使い始めてから、beamer の出番はなくなってしまった。

そんな IguanaTeX でもバグがあって、例えば

${\cal P}$

などが入ると platex では、

Error while using Ghostscript to convert from PDF to PNG. Is your path correct?

というエラーメッセージが出る。

ちなみに、${\cal P}$ を外すと普通に platex でコンパイルできるので、パスが違っているわけでもない。

IguanaTeX のデバッグモードで見ると、IguanaTex_tmp_tmp.png を生成するときに失敗している。
このコマンドをコマンドラインから実行すると、

GPL Ghostscript 9.10: **** Could not open temporary file ''
GPL Ghostscript 9.10: Could not open the scratch file .
**** Unable to open the initial device, quitting.

Temp folder の設定が反映されていないようで、コマンドラインからだと set TEMP= を設定すると実行できる。ただ、ppam ファイルを解析していないので、ppam ファイルの中で TEMP をどのようにコントロールしているかが、ちょっとわからない。

まぁ、こんなバグが残ってはいるけど、IguanaTeX は、すごく便利。

もはや、これなしで資料を作るとか大変すぎる。

Uzawa method の実装に挑戦

ICCOPTで勉強してきた Uzawa method をSDPについて実装を行ってみた。
コアとなるアルゴリズムは、Matlab なら 30 行程度で実装できる。

１反復当たりの計算量はADMM よりも小さい（計算量オーダーで違う）ので、各反復は高速だが、やはり収束までの反復回数が相当かかる。

特に、理論的に収束させるためのステップ幅が 1.0e-5 よりも短くなるのが厳しい。
適当にステップ幅を大きくすると、当然ながら点列は収束しないで、どっか明後日の方向に飛んでってしまう。

SDPA にある example1.dat-s なら 100 反復程度なので結構高速だが、SDPLIB にある control1.dat-s を解こうとしたところ 100 万反復（「万」に注意）しても、解に近づけなかった。

ちなみに、「Uzawa method は双対問題への劣勾配法に相当する」、と書いてある論文があった。

やはり参考にしている元論文と同じように特定の状況のみに使うべきか、あるいは、もう少し別のスピードアップを検討するべきか。Uzawa method は、もともと広範囲のアルゴリズムなので、スピードアップについてもいろいろと研究があることだし。

列生成法を勉強するための資料

列生成法を勉強する上で基本的なところを学ぶことができるのが、

"A tutorial on column generation and branch-and-price for vehicle routing problems"
4OR, December 2010, Volume 8, Issue 4, pp 407–424
http://link.springer.com/article/10.1007%2Fs10288-010-0130-z
になっている。


日本語の場合は、
「はじめての列生成法」
http://www.orsj.or.jp/archive2/or57-04/or57_4_198.pdf
が非常によく書けていて参考になる。