投稿
Optimization Online に最近掲載された
http://www.optimization-online.org/DB_FILE/2016/11/5713.pdf
をざっと眺めてみると、SOCP に対する多項式時間アルゴリズムが載っていて、内点法とも近いような、それでいてそうでもないような感じで面白いと思う。
標準形を特定の形式に変形することでアルゴリズムを作るってところは Karmarkar の内点法に似たような感じもあるし、途中で体積の計算をしたりしているところは楕円体法を思い出したりもする。
気になるのは、
（１）実際にプログラムを組んでみたら、どれくらいの性能が出るのか？
（２）内点法よりも数値誤差に強いだろうか？
特に（２）のところは、実行可能内点がない問題がとけるようになれば、ぜひ使ってみたいところ。でも、これはやっぱり難しい？
2016年12月6日火曜日
2016年12月1日木曜日
NASA との共同研究での 3D パッキング問題
INFORMS Annual Meeting で聞いた発表のひとつに、NASA との共同研究で 3D パッキング問題を解いている、というものがあった。
ふつうの問題とは若干違っていて、ひょっとしたら数学的性質がかなり違うのかもしれない。
発表の中では、「厳密解を求めるために、今は整数計画問題として解いている」ということで、定式化されている整数計画問題は比較的オーソドックスに定式化されていた。
これは、なかなかに面白いネタだと思う。
例えば、
１）定式化を工夫して、冗長な情報を除去したり、CPLEX などで高速に解けるようにする
２） Bender's decomposition などが使えるか検討する
３） Lagraingian 緩和, SDP 緩和などの緩和手法で近似値を低コストで得る
などなど、いろんな発展があるんじゃないかと思う。
発表のパワーポイント資料を発表者から頂くことができたので、定式化については検討してみようと思う。
ふつうの問題とは若干違っていて、ひょっとしたら数学的性質がかなり違うのかもしれない。
発表の中では、「厳密解を求めるために、今は整数計画問題として解いている」ということで、定式化されている整数計画問題は比較的オーソドックスに定式化されていた。
これは、なかなかに面白いネタだと思う。
例えば、
１）定式化を工夫して、冗長な情報を除去したり、CPLEX などで高速に解けるようにする
２） Bender's decomposition などが使えるか検討する
３） Lagraingian 緩和, SDP 緩和などの緩和手法で近似値を低コストで得る
などなど、いろんな発展があるんじゃないかと思う。
発表のパワーポイント資料を発表者から頂くことができたので、定式化については検討してみようと思う。
2016年11月9日水曜日
PDF の日本語目次を pdftk で修正する
PDF を結合したりするときに使う pdftk だが、目次を入れ替えることもできる。
このときに、utf8 を使えば日本語でも大丈夫になる。
例えば、a.pdf の目次情報を取り出すなら、
$ pdftk a.pdf dump_data_utf8 output mokuji.txt
として mokuji.txt に取り出せる。
これをutf8 の文字コードのまま編集してセーブしたら
$ pdftk a.pdf update_info_utf8 mokuji.txt output a2.pdf
とすれば、他の内容を引き継ぎつつ、目次情報だけを更新できる。
あるいは、目次情報などが全くない PDF に対しても、
https://www.pdflabs.com/blog/export-and-import-pdf-bookmarks/
を参考にしつつ、以下のような mokuji.txt をutf8で作ればOKである。
BookmarkBegin
BookmarkTitle: 日本語目次
BookmarkLevel: 1
BookmarkPageNumber: 1
BookmarkBegin
BookmarkTitle: 目次ページ
BookmarkLevel: 2
BookmarkPageNumber: 3
このときに、utf8 を使えば日本語でも大丈夫になる。
例えば、a.pdf の目次情報を取り出すなら、
$ pdftk a.pdf dump_data_utf8 output mokuji.txt
として mokuji.txt に取り出せる。
これをutf8 の文字コードのまま編集してセーブしたら
$ pdftk a.pdf update_info_utf8 mokuji.txt output a2.pdf
とすれば、他の内容を引き継ぎつつ、目次情報だけを更新できる。
あるいは、目次情報などが全くない PDF に対しても、
https://www.pdflabs.com/blog/export-and-import-pdf-bookmarks/
を参考にしつつ、以下のような mokuji.txt をutf8で作ればOKである。
BookmarkBegin
BookmarkTitle: 日本語目次
BookmarkLevel: 1
BookmarkPageNumber: 1
BookmarkBegin
BookmarkTitle: 目次ページ
BookmarkLevel: 2
BookmarkPageNumber: 3
2016年11月4日金曜日
Bixby がなぜ CPLEX を止めたか
Bixby がなぜ CPLEX を止めたのか、その理由が今回の OPTIMA (OPTIMA 101) に掲載されているインタビュー記事の途中に書いてあった。
このインタビューは、いろいろと書いてあるので、非常に面白い。
まだインターネットには掲載されていないけど、そのうちに
http://www.mathopt.org/Optima-Issues/optima101.pdf
にアップロードされるのだと思う。
このインタビューは、いろいろと書いてあるので、非常に面白い。
まだインターネットには掲載されていないけど、そのうちに
http://www.mathopt.org/Optima-Issues/optima101.pdf
にアップロードされるのだと思う。
2016年11月2日水曜日
Julia のエディタとして Visual Studio Code を試してみる
Julia を使うためのエディタとして Visual Studio Code を試してみた。
まず、Visual Studio Code は、
https://code.visualstudio.com/docs/?dv=winzip
から Windows 版の zip ファイルをダウンロードして、zip ファイルを展開して使ってみた。
次に Visual Studio Code を実行して、「表示」-「拡張機能」で検索できる状態にして、「julia」として検索。これで Julia のサポートが入る。
また、linter の設定として、settings.json に
"julia.validate.executablePath":"C:\\Users\\ユーザー名\\AppData\\Local\\Julia-0.4.5\\bin\\julia.exe"
を追加する。
ちなみに、パスの区切りはバックスラッシュが２個になるところに注意。
settings.json の構文を間違えると、Visual Studio Code のウィンドウの一番左下にある x マークの数字が増えるので、xマークのところをチェックすると理由を教えてくれる。
これで一通り設定は終了。
使ってみると、エディタとして、構文サポートをしてくれる。
なお、エディタとターミナルは連携しておらず、「デバッグ」-「統合ターミナル」と開いても、julia.exe が起動するわけでもないし、julia.exe のディレクトリに移動するわけでもない。
したがって、普通のエディタとコマンドプロンプトを起動して、それらのウィンドウを上下に並ぶように配置したぐらいの効果が得られる。
まず、Visual Studio Code は、
https://code.visualstudio.com/docs/?dv=winzip
から Windows 版の zip ファイルをダウンロードして、zip ファイルを展開して使ってみた。
次に Visual Studio Code を実行して、「表示」-「拡張機能」で検索できる状態にして、「julia」として検索。これで Julia のサポートが入る。
また、linter の設定として、settings.json に
"julia.validate.executablePath":"C:\\Users\\ユーザー名\\AppData\\Local\\Julia-0.4.5\\bin\\julia.exe"
を追加する。
ちなみに、パスの区切りはバックスラッシュが２個になるところに注意。
settings.json の構文を間違えると、Visual Studio Code のウィンドウの一番左下にある x マークの数字が増えるので、xマークのところをチェックすると理由を教えてくれる。
これで一通り設定は終了。
使ってみると、エディタとして、構文サポートをしてくれる。
なお、エディタとターミナルは連携しておらず、「デバッグ」-「統合ターミナル」と開いても、julia.exe が起動するわけでもないし、julia.exe のディレクトリに移動するわけでもない。
したがって、普通のエディタとコマンドプロンプトを起動して、それらのウィンドウを上下に並ぶように配置したぐらいの効果が得られる。
2016年10月31日月曜日
救急車配置問題を python で解いているサイトがあった
救急車配置問題を python で解こうとしているサイトがあった。
以下のような方向で発展できるかもしれない。
- p-median は LP に定式化できるので、今どきの LP solver なら、まず解ける。これを初期解として改良する、というのはありかもしれない。分枝限定法とも組み合わせられるのではないだろうか？
- いま思ったが、p-median に定式化するのと似たような感じで、最も時間がかかるところを最小化するのも LP になる。これも、今どきの LP solver なら、まず解けるだろう。つまり、1,2 のイイトコどりをするような解を構成できるはず。
2016年10月26日水曜日
カミフルについて
新潟に行ったときにカミフルのあたりも見てきたので、思ったことを少し書き留めておいてみる。
（やはり、どんな研究も実際の生活に役に立ってこそ意味があるので、どこかに出かけたときには、いろんな所を見れるだけ見るように歩いたりしている。）
１．場所がわかりにくい
新潟駅からで徒歩だと結構ある。というか、普通はバスを使うべき距離だった、と後で気がつく。しかしながら、バスが通る大通りの古町のあたりからだと、どこにあるのか、よくわからない。大通りからも、それなりに歩くので、途中で「道間違えたか？」と心配になって帰りそうになった。
大通りからも分かるような矢印とかほしい。
２．到着しても、ここがカミフルだって気がつかない
すでにカミフルに到着してから１００メートルぐらい歩いてようやく、カミフルにすでに入っていると気がついた。例えば、通りにある柱に統一的なカラーをするとか、見た目だけで「このあたりは、何かの区域なの？」って分かるようになったらいいかと思う。個人的には、緑と青のパステルトーンにしたら似合いそうだと思うが、カミフルに引っ掛けてカラフルにするのもありだと思う。イメージとしては、ヴェネチアのパリーナみたいな感じのものが各お店の入り口にあったら、いいのでは？
３．アニメ・マンガ専門学校との共同作業があってもいいのかも
せっかくの新潟なので、このあたりで特色を出すのもいいかなと思う。例えば、東京にあるお店と同じようなお店は、もっと新潟駅の近くにあるラブラ万代でも見ることができたので、それとは被らないようにとも思うけど、こういった共同作業でいかにシナジー効果を出せるかが一筋縄ではいかないのも分かる。
今回、新潟の中でも特に「カミフルに行ってみよう」と思ったのは、マンハッタンでいうところのソーホーあるいはチェルシーのように若手の人が集まるアートエリアなのかな？と思ったところにある。
上にはいろいろと書いてはみたけど、実際に行ってみた感じでは、これからの成長力が面白いエリアになりつつあるのかも、と思っている。
2016年10月24日月曜日
arXiv のフォローを外す
今まで arXiv の math.OC カテゴリを RSS でフォローしていたが、このフォローをやめてみることにした。
理由としては、
「面白そうな論文が多すぎて、全部追いかけるのが大変になった」
というところ。
１日に１５本ぐらいずつ登録されているんじゃないか、と思うので１週間に１００本ぐらいになってしまい、情報過多になってしまったので、思い切ってサクッとやめてみることにしてみた。
理由としては、
「面白そうな論文が多すぎて、全部追いかけるのが大変になった」
というところ。
１日に１５本ぐらいずつ登録されているんじゃないか、と思うので１週間に１００本ぐらいになってしまい、情報過多になってしまったので、思い切ってサクッとやめてみることにしてみた。
2016年10月13日木曜日
Google Optimization Tools
RAMP の予稿集を見ていて、あとでチェックしてみようと思ったのが、
Google Optimization Tools
https://developers.google.com/optimization/
どうやら、ざっと見る限り、線形計画問題や整数計画問題のソルバーのインターフェース、およびナップサック問題の解法とネットワーク最適化計算が実装されているようだ。
ずっと以前にネットワーク最適化のソフトウェアを調べたときには、API などがソフトウェアごとにマチマチで、理論的研究成果がソフトウェア実装にどれだけ反映されているのか調べるのが面倒になってしまいギブアップしてしまった。
Google のソフトウェアがデファクトスタンダードになってくれば、理論的研究でも「Google Optimization Tools と比較して何パーセント性能向上」というような数値実験結果が増える方向にいくんじゃないかと思ったりする。
あと、LPやMIPについては既存ソフトウェアへのインターフェースだけ、ってところは気になるところ。既存ソフトウェアで Google が使うには十分なパフォーマンスが得られるのか。あるいは、LP, MIP は Google としては、それほど高性能である必要はないのか。どっちなんだろう。
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 先生に挨拶できたのが良かった。
５年前にお世話になっていながら、そのあとに直接お会いできる機会がなかったので、今回挨拶できたのは良かったと思う。
１．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 先生に挨拶できたのが良かった。
５年前にお世話になっていながら、そのあとに直接お会いできる機会がなかったので、今回挨拶できたのは良かったと思う。
2016年10月7日金曜日
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 を呼び出せるので、バグが回避できる。
まずは、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}$
というか、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.
このコマンドをコマンドラインから実行すると、
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 は、すごく便利。
もはや、これなしで資料を作るとか大変すぎる。
2016年10月5日水曜日
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 は、もともと広範囲のアルゴリズムなので、スピードアップについてもいろいろと研究があることだし。
コアとなるアルゴリズムは、Matlab なら 30 行程度で実装できる。
１反復当たりの計算量はADMM よりも小さい（計算量オーダーで違う）ので、各反復は高速だが、やはり収束までの反復回数が相当かかる。
特に、理論的に収束させるためのステップ幅が 1.0e-5 よりも短くなるのが厳しい。
適当にステップ幅を大きくすると、当然ながら点列は収束しないで、どっか明後日の方向に飛んでってしまう。
SDPA にある example1.dat-s なら 100 反復程度なので結構高速だが、SDPLIB にある control1.dat-s を解こうとしたところ 100 万反復（「万」に注意）しても、解に近づけなかった。
ちなみに、「Uzawa method は双対問題への劣勾配法に相当する」、と書いてある論文があった。
やはり参考にしている元論文と同じように特定の状況のみに使うべきか、あるいは、もう少し別のスピードアップを検討するべきか。Uzawa method は、もともと広範囲のアルゴリズムなので、スピードアップについてもいろいろと研究があることだし。
2016年10月4日火曜日
列生成法を勉強するための資料
列生成法を勉強する上で基本的なところを学ぶことができるのが、
"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
が非常によく書けていて参考になる。
"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
が非常によく書けていて参考になる。
2016年9月21日水曜日
ICCOPT の復習
ICCOPT 関係の仕事がようやく一段落というところまで来たので（完全には終わってないけど、他のところの作業が進むのを待っていればいい状態まできたところ）、ICCOPT から１か月ぐらいして、ICCOPT で勉強してきた内容を復習しているところ。
ICCOPT でも面白い論文がいくつもあったので全部紹介したいところだが、今回は２点だけ書いてみることにする。
両方とも、温故知新なところもありつつ、幅広く使えるので幅広く論文になりそうなものである。
ICCOPT でも面白い論文がいくつもあったので全部紹介したいところだが、今回は２点だけ書いてみることにする。
両方とも、温故知新なところもありつつ、幅広く使えるので幅広く論文になりそうなものである。
- Uzawa method
名前しか知らなかったが、これはうまく利用すれば first-order method が使われているようなところで first-order method よりも高性能にいけるかもしれない。 - Column generation
大規模な LP を解く上での重要なテクニック。ICCOPT での話や関係する論文を調べていると、Column generation は現在でも多くの論文が出ていて、SDP とも関係があったり、この計算手法をベースにしてヒューリスティクスにつないだりしている。たとえて言うなら、「高配当なディフェンシブ銘柄」と言ったところか。いくつかの論文を読んでいると、なぜこの計算手法がこれほど長く使われているか分かってきたりするのも面白い。
あと、ICCOPT に続いて行われた Workshop on Advances in Optimization でも、いくつか面白い内容があったので、そちらの論文もダウンロードをしているところ。
樹木園の問題をダウンロードできるようにしておいた
Workshop on Advances in Optimization であったように、樹木園の問題で出てくる数理最適化問題に対する SDP 緩和の問題を整理して、ダウンロードできるようにしておいた。
どういうように SDP 緩和の問題を生成するか、という生成手順と、そのスクリプトも一緒になっている。このスクリプトだと、そのまま SDPA や SDPT-3 などで、緩和問題を解けるようになっている。
比較的シンプルな緩和ではあるけど、数値的には難しい問題になっていて、問題の規模に対して数値的安定性も難しいし、計算時間もそれなりにかかる。ADMM なども、あまり効果的ではなかったし。
どうすると、こういった問題をきちんと解けるか、まだまだ SDP の求解も難しいことばかりだ。
どういうように SDP 緩和の問題を生成するか、という生成手順と、そのスクリプトも一緒になっている。このスクリプトだと、そのまま SDPA や SDPT-3 などで、緩和問題を解けるようになっている。
比較的シンプルな緩和ではあるけど、数値的には難しい問題になっていて、問題の規模に対して数値的安定性も難しいし、計算時間もそれなりにかかる。ADMM なども、あまり効果的ではなかったし。
どうすると、こういった問題をきちんと解けるか、まだまだ SDP の求解も難しいことばかりだ。
2016年7月22日金曜日
保守工程における問い合わせを用いたバグ予測モデルの提案
「保守工程における問い合わせを用いたバグ予測モデルの提案」という論文に目を通してみたが、なかなかに面白かったので、メモ。
だいたいのところで要約すると、
１．ソフトウェア開発が終わって納品したソフトウェアの保守工程において、メールの問い合わせ内容から「バグ」などの言葉を含んだメールを抽出する。
２．メールの内容や担当者などからきいたことから、複数ある保守工程をクラスタリングにより、いくつかの保守工程グループに分類する。
３．各グループごとに、「保守要員数を維持しておくべき」など判断できるような材料をつくる
といったあたり。
１については、Twitter への書き込み情報から自動的に株価取引を行うプログラムが行っていることと似たような字句解析・構文解析のあたりが行われているのではないかとおもう。
２のクラスタリングは、保守工程の数が多くなった場合には計算時間がかかりそうだけど、数理最適化の手法を使えば計算時間を短縮できるかもしれない。
３の部分は、決定木を用いているので、遺伝的プログラミングを導入すると「５５」などの具体的な数字を半自動的に決めることができる可能性がある。
あとは、各バグが独立ではなくて、あるバグが原因で他のバグが報告されている、など因果関係があったりする場合にクラスタリングをどうするのか、というあたりも気になるところ。やっぱり、グラフィカルモデリングなどとも関係したりするんだろうか。
だいたいのところで要約すると、
１．ソフトウェア開発が終わって納品したソフトウェアの保守工程において、メールの問い合わせ内容から「バグ」などの言葉を含んだメールを抽出する。
２．メールの内容や担当者などからきいたことから、複数ある保守工程をクラスタリングにより、いくつかの保守工程グループに分類する。
３．各グループごとに、「保守要員数を維持しておくべき」など判断できるような材料をつくる
といったあたり。
１については、Twitter への書き込み情報から自動的に株価取引を行うプログラムが行っていることと似たような字句解析・構文解析のあたりが行われているのではないかとおもう。
２のクラスタリングは、保守工程の数が多くなった場合には計算時間がかかりそうだけど、数理最適化の手法を使えば計算時間を短縮できるかもしれない。
３の部分は、決定木を用いているので、遺伝的プログラミングを導入すると「５５」などの具体的な数字を半自動的に決めることができる可能性がある。
あとは、各バグが独立ではなくて、あるバグが原因で他のバグが報告されている、など因果関係があったりする場合にクラスタリングをどうするのか、というあたりも気になるところ。やっぱり、グラフィカルモデリングなどとも関係したりするんだろうか。
ulem.sty を使うと雑誌名にアンダーラインがつくのを防ぐ
TeX で打消し線を使いたいときに ulem.sty を使うと、参考文献のところで雑誌名（ジャーナル名）にアンダーラインがついてしまう。
これについては
http://kawaiihaseigi.blogspot.jp/2013/01/ulemstyemph.html
に書いてある手法で対応できて、
\usepackage{ulem}
のところを
\usepackage[normalem]{ulem}
とすると解決できる。
これについては
http://kawaiihaseigi.blogspot.jp/2013/01/ulemstyemph.html
に書いてある手法で対応できて、
\usepackage{ulem}
のところを
\usepackage[normalem]{ulem}
とすると解決できる。
2016年7月20日水曜日
Flag 代数ってものが面白そう
arXiv に flag algebra というものに関する論文が出てきていた。
http://arxiv.org/abs/1607.04741
ざっと読んだ限りだと、グラフ理論の構造とも関係している代数とのこと。
これに SDP や Sum of Squares などが関係しているみたい。
すぐには読めないだろうけど、ちょっと時間を見つけて読んでみたいような論文だと思う。
http://arxiv.org/abs/1607.04741
ざっと読んだ限りだと、グラフ理論の構造とも関係している代数とのこと。
これに SDP や Sum of Squares などが関係しているみたい。
すぐには読めないだろうけど、ちょっと時間を見つけて読んでみたいような論文だと思う。
2016年7月13日水曜日
シンプレックスへの射影についての新しい論文が出ていた
計算としては、シンプレックスへの射影は
$ \{ x \in R^N : \sum_{i=1}^N x_i, x \ge 0\}$
への射影をどう計算するか、という問題で基礎的な問題ではあるが、ソートと同じような感じでいろいろなアルゴリズムが開発されている。
今日気がついたところでは、この内容について新しい論文が出ていた。
"Fast projection onto the simplex and the $\ell_1$ ball"
http://link.springer.com/article/10.1007/s10107-015-0946-6
数値実験用のソフトは C で組んであるとのこと。
前に別の論文にあったアルゴリズムをMatlabで実装してみたときは、setdiff や union などの集合を扱う計算に計算時間を取られていたが、そのあたりは C で組むと解消できているのかもしれない。
基礎的な問題であるけど、基礎的な問題であるからこそ、常に新しいアルゴリズムが研究されていて面白い。
$ \{ x \in R^N : \sum_{i=1}^N x_i, x \ge 0\}$
への射影をどう計算するか、という問題で基礎的な問題ではあるが、ソートと同じような感じでいろいろなアルゴリズムが開発されている。
今日気がついたところでは、この内容について新しい論文が出ていた。
"Fast projection onto the simplex and the $\ell_1$ ball"
http://link.springer.com/article/10.1007/s10107-015-0946-6
数値実験用のソフトは C で組んであるとのこと。
前に別の論文にあったアルゴリズムをMatlabで実装してみたときは、setdiff や union などの集合を扱う計算に計算時間を取られていたが、そのあたりは C で組むと解消できているのかもしれない。
基礎的な問題であるけど、基礎的な問題であるからこそ、常に新しいアルゴリズムが研究されていて面白い。
2016年7月11日月曜日
ウキウキである
最近になって出てきた論文をチェックしていたら、自分が定式化までして「これはどうしたものか」と思っていた放っておいた最適化問題に使えそうな解法が出てきていた。
また、この論文から芋づる式で他の論文もチェックすることができて、似たような解法がどこにあるのか、というあたりを探すことができるようになった。
以前に Google scholar などを使っていたときには検索ワードが良くなかったらしく、こういった情報にたどり着けていなかった。
ということで、今日の時間を使って論文読みはじめ。なかなかに面白い。
著者にあったことはないけれど、こういった論文を書いてくれていることは、とてもありがたいことだなぁ、と思ったりもする。
こういう論文を見つけてしまうと、もはやウキウキである。
また、この論文から芋づる式で他の論文もチェックすることができて、似たような解法がどこにあるのか、というあたりを探すことができるようになった。
以前に Google scholar などを使っていたときには検索ワードが良くなかったらしく、こういった情報にたどり着けていなかった。
ということで、今日の時間を使って論文読みはじめ。なかなかに面白い。
著者にあったことはないけれど、こういった論文を書いてくれていることは、とてもありがたいことだなぁ、と思ったりもする。
こういう論文を見つけてしまうと、もはやウキウキである。
2016年6月27日月曜日
ICCOPT の発表資料の作成スタート
今後のスケジュールから逆算して、ICCOPT の発表資料を作っておかないと時間が無くなる可能性があるので、今のうちに発表資料を作成しておく。
ICCOPT は、今回は 20 分の発表時間＋５分の質疑応答なので、その時間をうまくやりくりできるように作りたいものである。
ICCOPT は、今回は 20 分の発表時間＋５分の質疑応答なので、その時間をうまくやりくりできるように作りたいものである。
2016年6月24日金曜日
Deep Learning とかで BLAS は高速化できるのだろうか？
OpenBLAS のコンパイルの情報などを調べていて、
http://unity-memo.hatenablog.com/entry/2015/03/03/104238
を読んでみたところ、手動で最適化されている OpenBLAS が自動チューニングである ATLAS よりも高速であることから、
「現代の技術をもってしても 自動チューニングは手動オプティマイズに打ち勝つことはできないという事だろうか。」
と述べている。
非常に興味深い内容だ。
Deep Learning などの技術を取り込めば、どこまで BLAS を高速化できるのか、などなど考えてみると、今後の最適化技術にも関係しそうで面白い。
http://unity-memo.hatenablog.com/entry/2015/03/03/104238
を読んでみたところ、手動で最適化されている OpenBLAS が自動チューニングである ATLAS よりも高速であることから、
「現代の技術をもってしても 自動チューニングは手動オプティマイズに打ち勝つことはできないという事だろうか。」
と述べている。
非常に興味深い内容だ。
Deep Learning などの技術を取り込めば、どこまで BLAS を高速化できるのか、などなど考えてみると、今後の最適化技術にも関係しそうで面白い。
2016年6月23日木曜日
ADMM よりも高速な Newton 法
A Distributed Newton Method for Large Scale Consensus Optimization
http://arxiv.org/abs/1606.06593
をざっくりとチェックしたので簡単なまとめ。
計算したい最適化問題をざっくりと書くと、
$\min_{x_1,x_2,\ldots,x_n} \sum_{i=1}^n f_i (x_i) \mbox{ s.t. } x_1 = x_2 = ... = x_n \in R^p$
となり、$x_i$ と $x_j$ が関係があるかはグラフとして別に与えられている。
さらに関数 $f$ は、ヘッセ行列の固有値に上限と下限があって、ヘッセ行列の逆行列は Lipshitz 連続である。
こういった最適化問題のときに、この論文では双対問題に Newton 法を使うことで問題を解いている。特に、グラフから得られる構造で双対問題のヘッセ行列が疎行列になるとのこと。おそらく、このあたりはグラフィカルモデリングにあった性質と同じなのではないかと推測できる。たぶん、行列補完ともかんけいあるはず。
http://arxiv.org/abs/1606.06593
をざっくりとチェックしたので簡単なまとめ。
計算したい最適化問題をざっくりと書くと、
$\min_{x_1,x_2,\ldots,x_n} \sum_{i=1}^n f_i (x_i) \mbox{ s.t. } x_1 = x_2 = ... = x_n \in R^p$
となり、$x_i$ と $x_j$ が関係があるかはグラフとして別に与えられている。
さらに関数 $f$ は、ヘッセ行列の固有値に上限と下限があって、ヘッセ行列の逆行列は Lipshitz 連続である。
こういった最適化問題のときに、この論文では双対問題に Newton 法を使うことで問題を解いている。特に、グラフから得られる構造で双対問題のヘッセ行列が疎行列になるとのこと。おそらく、このあたりはグラフィカルモデリングにあった性質と同じなのではないかと推測できる。たぶん、行列補完ともかんけいあるはず。
IguanaTeX で platex が動かないときに
Powerpoint で数式を入れたりするときに便利な IguanaTeX だが、たまに platex (PDF->PNG) がエラーで停止することがある。
どういったタイミングで起こるか特定できていないが、エラーとしては「ghostscript が見つからない」というようなエラーが出る。（ついさっきまで出てなかったのに、１行だけつけてみたら、このエラーが出たときもある。）
原因はよく分からないが、このときには、 platex (PDF->PNG) から latex (DVI->PNG) に切り替えると上手くコンパイルできる。
それにしても、IguanaTeX は非常に便利。これなしでは、やってけない。
どういったタイミングで起こるか特定できていないが、エラーとしては「ghostscript が見つからない」というようなエラーが出る。（ついさっきまで出てなかったのに、１行だけつけてみたら、このエラーが出たときもある。）
原因はよく分からないが、このときには、 platex (PDF->PNG) から latex (DVI->PNG) に切り替えると上手くコンパイルできる。
それにしても、IguanaTeX は非常に便利。これなしでは、やってけない。
2016年6月13日月曜日
Optima 100 の原稿に SDPA-GMP が引用されていた
Optima 100 の中に "Computer-assited proofs and semidefinite programming" という内容が掲載されていたが、SDP 関係だったのでチェックしてみたら、 SDPA-GMP が参考文献に載っていた。
SDPA-GMP は多倍長計算を用いて演算を行っているので、数値的に不安定になりやすい SDP には効果が高い。やはり、こういうソフトウェアって需要があるんだなぁ、と再確認したりする。
SDPA-GMP は多倍長計算を用いて演算を行っているので、数値的に不安定になりやすい SDP には効果が高い。やはり、こういうソフトウェアって需要があるんだなぁ、と再確認したりする。
2016年6月8日水曜日
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$ となって、連続緩和と強さが変わらない。
なるほど、なるほど。なかなかに面白い結果だ。
これを、$-x^2(x-1)^2 \ge 0$ として、Sum of Squares の緩和をするとどうなるか。
得られる緩和は $ 0 \le x \le 1$ となって、連続緩和と強さが変わらない。
なるほど、なるほど。なかなかに面白い結果だ。
2016年6月7日火曜日
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-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 で入力するほうがインデントの自動調節が素早く行われる。
（このあたりのスピードの差がどこから来るのかは、まだ良く調べてないけど。）
2016年6月3日金曜日
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 よりも遅い印象になっている。
数理最適化のプログラムを組んでいくには、現状では大変な感じだ。
でも、面白い機能も多いので、スピードが改善されてメモリ消費量が抑えられたら、こっちに移るのもありだと思う。
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 との計算比較が載っていなかったりするので、それほど性能が良くない可能性もあり。
確率最適化の論文としては、なかなかに面白いと思う。
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
以下に気付いた点をメモ代わりに書いておくことにする。
- binary 変数の設定の仕方が面白い。自分が行っているところにも、この手法を利用してみようと思う。
- SDP 緩和の評価が比較的わかりやすいところが載っているが、このあたりはもっと詳しく解析する方法が載っている論文もあるので、使えるかもしれない
- 目的関数が convex の最大化なので、整数制約だけでなく凸性がない点も難しさがあるところ。ただ、数値実験結果は良好なので、目的関数に現れる行列（共分散行列）の性質がいいのだと思われる。
- 定式化されている SDP は内点がないので、主双対内点法だと数値的不安定性が現れやすいと予測できる。数値実験では M = 250, K = 5 で行列のサイズが 1250x1250 と小規模なところになっているが、おそらく 5000x5000 あたりの中規模問題から数値的不安定性がシリアスになってくる。 データにも依存するけど、SDPA なら epsilonBar を若干大きくして (1.0e-4 など)、数値的不安定性を回避したほうがいいかもしれない。
- 数値実験を 72 core のマシンでありながら 1 core でしか行っていないので、SDPA を 72 core で実行したらどうなるか、気になるところ。
- ５節の最後のあたりに、"the next section investigates to incorporate a sparse learning technique" とありつつ、６節の内容が違う内容になっており、sparse learning とどう関係してくるのか、気になるところ。
などが、気がついた点。
内容としては面白かったし、１番の点については、あとで自分の研究にも実装してみようと思う。
2016年5月17日火曜日
量的遺伝学の論文読み
最近、空き時間を見つけて量的遺伝学の論文を読んでいる。
ある論文では、凸2次最適化問題を simulated annealing で解いていたりする。
数理最適化の手法を用いれば、こういった分野にも貢献できるのでは、と思って論文を読んでみると、いろいろと面白い。
ある論文では、凸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 がどういうときに使い勝手がいいのか、など把握できそう。
といったあたり。
2016年4月15日金曜日
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 も一度にインストールできるかもしれない。）
グラフィックス周りは当面は実行できないだろうけど、apt-get でインストールができるようになると数理最適化関連のソフトを Windows にインストールするのも格段に便利になるので、利便性が一気に向上するのでは？と思ったりする。
将来的に X が動くようにもなれば、TeX 関係も非常に簡単にインストールできるので、そのあたりも楽になりそう。
（# apt-get install yatex とすると、emacs も TeX も一度にインストールできる。試したことはないが、TeXworks をインストールすると TeX も一度にインストールできるかもしれない。）
2016年4月5日火曜日
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
に詳しく書かれている。
実際の手順は以下のサイトに書かれている通りである。
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
に詳しく書かれている。
2016年3月28日月曜日
2016年3月18日金曜日
OR学会でいろいろと聞いてきて
シンポジウムを含めて３日間の学会でいろいろと聞いてきて勉強になった。
特別講演では、
１．「もんだ」をやめる
２．「こども」になる
３．「自分」を信じる
といった内容を聞くことができた。普段接することのない視点での内容で、とても勉強になった。
また、DC programming のところを聞いていたら、自分の今の内容にどういった Lemma を作ればいいのか、というヒントがあったりで参考になった。
帰りの電車で考えてみたところ、Lemma の証明の概略も分かったので、また一歩前進かと思う。
特別講演では、
１．「もんだ」をやめる
２．「こども」になる
３．「自分」を信じる
といった内容を聞くことができた。普段接することのない視点での内容で、とても勉強になった。
また、DC programming のところを聞いていたら、自分の今の内容にどういった Lemma を作ればいいのか、というヒントがあったりで参考になった。
帰りの電車で考えてみたところ、Lemma の証明の概略も分かったので、また一歩前進かと思う。
2016年3月9日水曜日
2016年2月25日木曜日
ログを見るのに watch コマンドが便利
screen 環境で実行しているログから定期的にどうなっているかを自動的に表示させるのに watch コマンドを使と非常に便利。
例えば、
watch -d -n 5 'grep iteration screenlog.0 | tail -10'
例えば、
watch -d -n 5 'grep iteration screenlog.0 | tail -10'
とすると、screenlog.0 から iteration という文字列を含む最後の１０行だけを、５秒間隔で更新しながら表示してくれる。
2016年2月18日木曜日
多項式最適化問題の SDP 緩和の最適解の rank は 1 か 2 である
最近見つけた論文によると、
多項式最適化問題を SDP 緩和してできた SDP については、最適解集合の中に rank が 1 または 2 のものがある
ということらしい。
もし自分の読み違いでなければ、かなり強力なことを言っているはず。
rank 1 であれば、それは最適解になっているし、rank 2 であっても、randomization をするにあたっては rank が 2 という性質をもちいての randomization を使えば例えば Goemans and Williamson の比を改善できる可能性もあるのでは？と思う。
多項式最適化問題を SDP 緩和してできた SDP については、最適解集合の中に rank が 1 または 2 のものがある
ということらしい。
もし自分の読み違いでなければ、かなり強力なことを言っているはず。
rank 1 であれば、それは最適解になっているし、rank 2 であっても、randomization をするにあたっては rank が 2 という性質をもちいての randomization を使えば例えば Goemans and Williamson の比を改善できる可能性もあるのでは？と思う。
2016年2月8日月曜日
Julia で一括しての Pkg.add と reload
Julia でいくつかのパッケージをまとめてインストールするには、
以下のように for 文で行ったりすると一括でできる。
for i = ["Optim","JuMP","NLopt","Clp","Convex","Ipopt"]; Pkg.add(i); end
ちなみに、インストールされているものを一括して reload するのであれば
for i = collect(keys(Pkg.installed())); reload(i); end
でできる。
以下のように for 文で行ったりすると一括でできる。
for i = ["Optim","JuMP","NLopt","Clp","Convex","Ipopt"]; Pkg.add(i); end
ちなみに、インストールされているものを一括して reload するのであれば
for i = collect(keys(Pkg.installed())); reload(i); end
でできる。
2016年1月26日火曜日
Luenberger & Ye の本の第４版
Luenberger & Ye の Linear and Nonlinear Programming の最新版である第４版には ADMM の Section が追加されていた。
具体的には、14.7 節にあり、２つのブロックのときには収束すること、および３つのブロックのときには必ずしも収束しないこと等がまとめられている。
少し参考にしてみようと思う。
具体的には、14.7 節にあり、２つのブロックのときには収束すること、および３つのブロックのときには必ずしも収束しないこと等がまとめられている。
少し参考にしてみようと思う。
2016年1月14日木曜日
論文レフリーをやってみて思うこと
いくつかの論文をレフリーして思うのは、何回かの改訂を経て、最終的に
「この論文、ついに accept できるなぁ」
というタイミングがあって、なんかちょっとホッコリとした気分になったりもする。
もちろん、それまでに「証明のここが間違っている」とか厳しいことも書かないといけない場面もあったりして、「これがうまく行けばいいのに」と凹んだりもするわけだけど、最終的にそれらがクリアされてくると、「おぉ！」とか思ったりもするし。
そんなこんなで、新しい論文が出来上がっていく過程では、著者とレフリーは直接会うことはないわけだけど（実際に会う機会があっても、「自分がレフリーやってます」とは言えないわけだけど）、いろいろとあるもんだなぁ、としみじみしたりもする。
「この論文、ついに accept できるなぁ」
というタイミングがあって、なんかちょっとホッコリとした気分になったりもする。
もちろん、それまでに「証明のここが間違っている」とか厳しいことも書かないといけない場面もあったりして、「これがうまく行けばいいのに」と凹んだりもするわけだけど、最終的にそれらがクリアされてくると、「おぉ！」とか思ったりもするし。
そんなこんなで、新しい論文が出来上がっていく過程では、著者とレフリーは直接会うことはないわけだけど（実際に会う機会があっても、「自分がレフリーやってます」とは言えないわけだけど）、いろいろとあるもんだなぁ、としみじみしたりもする。
2016年1月13日水曜日
DIMACS のクリークのデータを Matlab 用に変換する
DIMACS のクリーク用データは、
https://turing.cs.hbg.psu.edu/txn131/clique.html
のサイトから入手できるが、バイナリ形式であるので、これを Matlab で扱いやすいように変換をする。
実際のファイルは、
https://turing.cs.hbg.psu.edu/txn131/file_instances/clique/DIMACS_cliques.tar.gz
にある。
これを展開して、 ascii ファイルに一度変換する。
変換ファイルは、
https://turing.cs.hbg.psu.edu/txn131/file_instances/converter.tar.gz
にあって、make でコンパイルした後に、
$ ./bin2asc DIMACS_cliques/MANN_a9.clq.b
とすると ascii ファイルで MANN_a9.clq が出来上がる。
一括変換なら
$ for i in DIMACS/*.clq.b; do ./bin2asc $i; done
である。
これを Matlab で処理して、一括変換する。
ただし、枝の数が 10 万を超えるものは、大きいので変換はスキップする。
以下のスクリプトを使っている。
TOO_LARGE = 100000;
dirs = dir('*.clq');
for index = 1:length(dirs)
filename = dirs(index).name;
fprintf('index = %d, filename = %s... ', index, filename);
fp = fopen(filename, 'r');
m = 0;
n = 0;
comments = {};
while 1
line1 = fgets(fp);
if length(line1) == 1
% end of file
break;
end
if line1(1) == 'c'
comments{length(comments)+1} = line1;
end
if line1(1) == 'p'
strings = strsplit(line1);
n = str2double(strings(3));
m = str2double(strings(4));
fprintf('node = %d, edge = %d\n', n, m);
if m > TOO_LARGE
break;
end
I = zeros(m, 1);
J = zeros(m, 1);
count = 1;
end
if line1(1) == 'e'
strings = strsplit(line1);
I(count) = str2double(strings(2));
J(count) = str2double(strings(3));
% fprintf('e[%d] = %d, %d\n', count, I(count), J(count));
count = count + 1;
if rem(count, 5000) == 0
fprintf('e[%d]... ', count);
end
end
end % end of while
if m > TOO_LARGE
fprintf(' : SKIP too large \n');
continue; % to next file
end
A = sparse(I,J,ones(m,1),n,n);
A = A+A';
savefile = strrep(filename, '.clq', '.mat');
save(savefile, 'A', 'comments');
for i = 1:length(comments); fprintf('%s', comments{i}); end
end
出来上がったファイルは、
load MANN_a9
などで読み込むことができて、
for i = 1:length(comments); fprintf('%s', comments{i}); end
でコメントも表示できる。
https://turing.cs.hbg.psu.edu/txn131/clique.html
のサイトから入手できるが、バイナリ形式であるので、これを Matlab で扱いやすいように変換をする。
実際のファイルは、
https://turing.cs.hbg.psu.edu/txn131/file_instances/clique/DIMACS_cliques.tar.gz
にある。
これを展開して、 ascii ファイルに一度変換する。
変換ファイルは、
https://turing.cs.hbg.psu.edu/txn131/file_instances/converter.tar.gz
にあって、make でコンパイルした後に、
$ ./bin2asc DIMACS_cliques/MANN_a9.clq.b
とすると ascii ファイルで MANN_a9.clq が出来上がる。
一括変換なら
$ for i in DIMACS/*.clq.b; do ./bin2asc $i; done
である。
これを Matlab で処理して、一括変換する。
ただし、枝の数が 10 万を超えるものは、大きいので変換はスキップする。
以下のスクリプトを使っている。
TOO_LARGE = 100000;
dirs = dir('*.clq');
for index = 1:length(dirs)
filename = dirs(index).name;
fprintf('index = %d, filename = %s... ', index, filename);
fp = fopen(filename, 'r');
m = 0;
n = 0;
comments = {};
while 1
line1 = fgets(fp);
if length(line1) == 1
% end of file
break;
end
if line1(1) == 'c'
comments{length(comments)+1} = line1;
end
if line1(1) == 'p'
strings = strsplit(line1);
n = str2double(strings(3));
m = str2double(strings(4));
fprintf('node = %d, edge = %d\n', n, m);
if m > TOO_LARGE
break;
end
I = zeros(m, 1);
J = zeros(m, 1);
count = 1;
end
if line1(1) == 'e'
strings = strsplit(line1);
I(count) = str2double(strings(2));
J(count) = str2double(strings(3));
% fprintf('e[%d] = %d, %d\n', count, I(count), J(count));
count = count + 1;
if rem(count, 5000) == 0
fprintf('e[%d]... ', count);
end
end
end % end of while
if m > TOO_LARGE
fprintf(' : SKIP too large \n');
continue; % to next file
end
A = sparse(I,J,ones(m,1),n,n);
A = A+A';
savefile = strrep(filename, '.clq', '.mat');
save(savefile, 'A', 'comments');
for i = 1:length(comments); fprintf('%s', comments{i}); end
end
出来上がったファイルは、
load MANN_a9
などで読み込むことができて、
for i = 1:length(comments); fprintf('%s', comments{i}); end
でコメントも表示できる。
2016年1月7日木曜日
Matlab でのエディタとコマンド入力の間のキーボードショートカット
Matlab の IDE でエディタとコマンド入力のところを行ったり来たりするのにマウスでクリックするのがめんどくさいと思っていたが、キーボードショートカットを調べてみたら、
Ctrl + Tab
で移動できることが判明。これで、さらに便利になった。
欲しいキーボードショートカットとしては、エディタで編集している時に一つ前の履歴のコマンドを実行するショートカットがあればいいとは思う。
たとえば、function [x,y] = test01(a, b, c) などがあるときに、F5 を押しただけでは a,b,c を入力できないけど、a,b,c を変更せずにソースを修正しながら何回も実行してテストするときなどには、こういった機能があったりすると便利だ。
今の状態だと、「Ctrl + Tab => 上 => Enter => Ctrl + Tab」 とすればできるけど、これがF4 なり、F8 などで、一回でできると便利かとは思う。
Ctrl + Tab
で移動できることが判明。これで、さらに便利になった。
欲しいキーボードショートカットとしては、エディタで編集している時に一つ前の履歴のコマンドを実行するショートカットがあればいいとは思う。
たとえば、function [x,y] = test01(a, b, c) などがあるときに、F5 を押しただけでは a,b,c を入力できないけど、a,b,c を変更せずにソースを修正しながら何回も実行してテストするときなどには、こういった機能があったりすると便利だ。
今の状態だと、「Ctrl + Tab => 上 => Enter => Ctrl + Tab」 とすればできるけど、これがF4 なり、F8 などで、一回でできると便利かとは思う。
2016年1月5日火曜日
20年後の数理最適化はどうなっているか？
今からざっと２０年前は内点法がある程度できあがってきた頃。
年初めということで、現在から２０年たったら数理最適化の研究はどうなっているかを考えてみるのも一興かとも思う。
大まかな予想としては（一部に、「そうできたらいいなぁ」という願望も含む）、
１．純粋数学に近い研究と実用に近い研究へと、大きく２極化する
たとえば、Math Prog などに掲載されるようなものは、パッとすぐには実用化には結びつかないような、むしろ純粋数学に近いようなところが多くなるかと思う。これはこれで基礎理論として純粋に理論を追究していくタイプになって面白そう。
逆に実用に近いところでは、メタヒューリスティクスのように厳密な最適解ではないが、実用的な計算時間で妥当な近似解を出すようなところが増えるのではないかと思う。これはこれで、実社会への応用が着実に行われて面白いと思う。
２．リアルタイム最適化が行えるようになる
たとえば、分枝限定法などは長時間の計算になるので、計算している途中で変数を追加したり削除したりを行いたくなってくる。
途中のノードの計算結果を見たときに変数と制約の追加や削除を自由に行えるようなアルゴリズムを作れたら、非常に面白い。
これができれば、小さいデータでテストをしながらも、順調に進めば大きなデータにアルゴリズムをリスタートすることなく移行することができるようになる。
たとえば、データの変化を追いかけたい金融のポートフォリオの計算などに使えるかと思う。
３．クラウドソーシングで研究機関が個人からも研究を受注できるようになる
数理最適化分野だけに限る必要はないが、クラウドソーシングを利用することによって、企業のような大組織だけでなく個人からも研究を受注できるようになる。
クラウドソーシングを使うと、もっと気軽に「こういった研究が欲しい」という声を聴ける可能性もあり、今までは把握できなかった研究テーマなどが発掘でできるようになるだけでなく、研究成果をよりダイレクトに還元することができるようになる。
数理最適化や確率・統計などの一部を含むオペレーションズ・リサーチは、「問題解決学」という側面ももっているので、非常に面白そう。
まずは思いつくのはこんなところ。
３については技術的には既に可能なので、２０年とかからずとも不思議ではない。
数理最適化に関係するいろんな人が「２０年後に数理最適化はどうなっているか」を予測し始めたら、それも見てみたかったりもする。
年初めということで、現在から２０年たったら数理最適化の研究はどうなっているかを考えてみるのも一興かとも思う。
大まかな予想としては（一部に、「そうできたらいいなぁ」という願望も含む）、
１．純粋数学に近い研究と実用に近い研究へと、大きく２極化する
たとえば、Math Prog などに掲載されるようなものは、パッとすぐには実用化には結びつかないような、むしろ純粋数学に近いようなところが多くなるかと思う。これはこれで基礎理論として純粋に理論を追究していくタイプになって面白そう。
逆に実用に近いところでは、メタヒューリスティクスのように厳密な最適解ではないが、実用的な計算時間で妥当な近似解を出すようなところが増えるのではないかと思う。これはこれで、実社会への応用が着実に行われて面白いと思う。
２．リアルタイム最適化が行えるようになる
たとえば、分枝限定法などは長時間の計算になるので、計算している途中で変数を追加したり削除したりを行いたくなってくる。
途中のノードの計算結果を見たときに変数と制約の追加や削除を自由に行えるようなアルゴリズムを作れたら、非常に面白い。
これができれば、小さいデータでテストをしながらも、順調に進めば大きなデータにアルゴリズムをリスタートすることなく移行することができるようになる。
たとえば、データの変化を追いかけたい金融のポートフォリオの計算などに使えるかと思う。
３．クラウドソーシングで研究機関が個人からも研究を受注できるようになる
数理最適化分野だけに限る必要はないが、クラウドソーシングを利用することによって、企業のような大組織だけでなく個人からも研究を受注できるようになる。
クラウドソーシングを使うと、もっと気軽に「こういった研究が欲しい」という声を聴ける可能性もあり、今までは把握できなかった研究テーマなどが発掘でできるようになるだけでなく、研究成果をよりダイレクトに還元することができるようになる。
数理最適化や確率・統計などの一部を含むオペレーションズ・リサーチは、「問題解決学」という側面ももっているので、非常に面白そう。
まずは思いつくのはこんなところ。
３については技術的には既に可能なので、２０年とかからずとも不思議ではない。
数理最適化に関係するいろんな人が「２０年後に数理最適化はどうなっているか」を予測し始めたら、それも見てみたかったりもする。
登録:
投稿 (Atom)