投稿
Julia でプログラムを実行していると、using のときに precompile が行われるのだけど、これが結構な頻度であって、しかも時間がかかる。しかも、「ちょうど計算を始めたタイミング」で起きるので、あんまり感じが良くない。
こういったのは、パッケージモードに入って precompile しておけばよいようだ。
julia > ]
(v1.3) pkg > precompile
これでインストールされているパッケージがすべてprecompileされた状態になる。
2020年2月19日水曜日
2020年2月3日月曜日
論文読み：Centering ADMM for the Semidefinite Relaxation of the QAP
今回チェックした論文は
Centering ADMM for the Semidefinite Relaxation of the QAP
http://www.optimization-online.org/DB_FILE/2020/01/7569.pdf
というもの。
タイトルにある通り、ADMMでQAPに対するSDP緩和を解くという話だけど、
単純なADMMではなく、内点法のバリア関数のように log det を導入して、
中心パスの近くに寄せようというもの。
アルゴリズムのアイデアについては面白いなぁ、と思う。
first-order method と second-order method の両方の性質を兼ね備えていると面白い。
数値実験については、計算時間が掲載されていないので、パフォーマンスは良く分からない。
あと、最後の Table 3 は、 mu < 1.0e-3 という比較的緩めの停止条件なので、
Centering LB と Standard LB の差はそれほど大きくない（有効桁数よりも小さいところ）。
個人的には、SDPに対して ADMM を使うのは、やはり固有値分解のボトルネックが気になるところ。
内点法だとCholesky分解で計算できるので入力行列の疎性をそのまま変数行列に引き継げるので、
そのあたりで工夫の面白さもあるけど、固有値分解を入れてしまうと、この疎性が壊れてしまうことが多い。
A fixed-point method for approximate projection onto the positive semidefinite cone
https://www.sciencedirect.com/science/article/pii/S0024379517300903
とかにあるような手法で近似計算したほうが良いのだろうか？
Centering ADMM for the Semidefinite Relaxation of the QAP
http://www.optimization-online.org/DB_FILE/2020/01/7569.pdf
というもの。
タイトルにある通り、ADMMでQAPに対するSDP緩和を解くという話だけど、
単純なADMMではなく、内点法のバリア関数のように log det を導入して、
中心パスの近くに寄せようというもの。
アルゴリズムのアイデアについては面白いなぁ、と思う。
first-order method と second-order method の両方の性質を兼ね備えていると面白い。
数値実験については、計算時間が掲載されていないので、パフォーマンスは良く分からない。
あと、最後の Table 3 は、 mu < 1.0e-3 という比較的緩めの停止条件なので、
Centering LB と Standard LB の差はそれほど大きくない（有効桁数よりも小さいところ）。
個人的には、SDPに対して ADMM を使うのは、やはり固有値分解のボトルネックが気になるところ。
内点法だとCholesky分解で計算できるので入力行列の疎性をそのまま変数行列に引き継げるので、
そのあたりで工夫の面白さもあるけど、固有値分解を入れてしまうと、この疎性が壊れてしまうことが多い。
A fixed-point method for approximate projection onto the positive semidefinite cone
https://www.sciencedirect.com/science/article/pii/S0024379517300903
とかにあるような手法で近似計算したほうが良いのだろうか？
登録:
投稿 (Atom)