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 法を使うことで問題を解いている。特に、グラフから得られる構造で双対問題のヘッセ行列が疎行列になるとのこと。おそらく、このあたりはグラフィカルモデリングにあった性質と同じなのではないかと推測できる。たぶん、行列補完ともかんけいあるはず。