要約メモ：Math Prog A, Vol 144, No. 1-2

だいたいどんなことが研究されているか、一部の論文を抜粋して簡単にメモしておく。

[1] Iteration complexity of randomized block-coordinate descent methods for minimizing composite function
Richtarik and Takac

Nesterov の一次法のあたりでよく見かける
min : F(x) = f(x) + Psi(x)
の形式の問題を解いている。ベースになっているのは、Nesterov の 2012 の SIAM J. Optim の論文だが、ここでは、ベクトル x をいくつかのブロックに分解して、それぞれのブロックごとに手法を適用している。これは、例えば、 x のうちのx_1 から x_100 まで、などブロック単位で区切って処理しないとならないほど大きな問題などを想定できる。

解析の中では、Lipsitz 連続や strong convexity などを利用するタイプ。
また、完全に最適解に収束させるわけではなくて、確率的に収束させるタイプ。（99% 以上の確率で最適値とのずれが 0.01 以内、といった感じ。）


[2] On the complexity of finding first-order critical points in constrained nonlinear optimization
Cartis, Gould and Toint

min: f(x) such that c(x) = 0
という制約付き最適化問題に対する KKT 条件の近似解を求めるのに必要な計算量は、
min: fbar(x)
のように制約なしの場合から本質的には増えたりしない、ということを言っている。

解析の道具としては、信頼領域法のアルゴリズムを利用している。

[3] An introduction to a class of matrix cone programming
Ding, Sun and Toh

この論文のMatrix cone programming は、
min { c^T x | A x \in b + Q \times K}
の形で定式化されている。ここで、Qは基本的には対称錘なので、second-order cone や SDP などを含む。また、 K は　epigraph による錘で、
epi (f) = {(t,X) : t \ge f(X)}
といったもの。
このような定式化に含まれるのは、Matrix completion, Robust PCA, 低ランク行列近似などがある。

アルゴリズムの基本要素は、錘などへの射影計算。

[4] A unified approach for minimizing composite norms
Aybat and Iyengar

この論文も composite の関数の最小化で
min    mu_1 || F(X) -G ||_{alpha}   + mu_2 || C(X) -d ||_{beta}
subject to A(X) - b \in Q.
という問題が対象。ここで、alpha と beta のノルムは 1-norm, 2-norm などがある。
解法としては、augmented Lagrangian がベース。