投稿
計算としては、シンプレックスへの射影は
$ \{ 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月13日水曜日
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 には効果が高い。やはり、こういうソフトウェアって需要があるんだなぁ、と再確認したりする。
登録:
投稿 (Atom)