凸优化：ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之四：
General Patterns

之四：
General Patterns"/>

凸优化：ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之四：
General Patterns

最近开始对凸优化(convex optimization)中的ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法开始感兴趣，接下来我会写一系列关于ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法的内容。

凸优化：ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之四： General Patterns

本文地址：

4- 一般模式（General Patterns）

本章主要探讨如何加速 x-和 z-更新步骤。主要考虑三种类型：quadratic objective
terms, separable objective and constraints 和 smooth objective terms.
我们首先表示 x-更新步骤为：

其中 v=−Bz+c−u <script type="math/tex" id="MathJax-Element-1"> v = −Bz + c − u </script> 是一个常量。（对称适用于 z-更新步骤）

4-1 近似算子（Proximity Operator）

考虑最简单的情况 A=I <script type="math/tex" id="MathJax-Element-2">A = I</script>，因此 x-更新步骤为

右边看做关于 u 的一个函数，标记为 proxf,ρ(v) <script type="math/tex" id="MathJax-Element-3">prox_{f, ρ}(v)</script>，叫做 f 关于 ρ 的近似算子（the proximity operator of f with penalty ρ ）。
在变分分析，

是 f 的 Moreau envelope 或 Moreau-Yosida regularization，与接近点算（proximal point algorithm ）的理论联系起来。因此接近算子（proximity operator）中的 x-最小化被称为接近端最小化（proximal minimization）。
当 f 足够简单时，x-update 就能评估分析。例如，f 是一个闭合非空凸集 C 的指示函数时，
x-update 为

其中 ΠC <script type="math/tex" id="MathJax-Element-4">Π_{C}</script> 为 C 上的映射（Euclidean范式）。等式成立与 ρ 无关。更多例子见 [41]

[41] P. L. Combettes and J. C. Pesquet, “Proximal Splitting Methods in Signal Processing,” arXiv:0912.3522, 2009.

4-2 二次型目标项（Quadratic Objective Terms）

假设 f 为（凸）二次函数，

其中 P∈Sn+ <script type="math/tex" id="MathJax-Element-5">P ∈ S^{n}_{+}</script> ，对称正半定 n × n 矩阵。
假设 P+ρATA <script type="math/tex" id="MathJax-Element-6">P + ρA_{T}A</script> 是可逆的， x+ <script type="math/tex" id="MathJax-Element-7">x^{+}</script> 是 u 的仿射函数（affine function）

换句话说，计算 x-update 等于 求解一个 关于正定系数矩阵（positive definite coefficient matrix） P+ρATA <script type="math/tex" id="MathJax-Element-8">P + ρA_{T}A</script> 和 ρATv−q <script type="math/tex" id="MathJax-Element-9">ρA^{T}v − q</script> 的线性系统。

4-2-1 直接法（Direct Methods）

求解 Fx=g <script type="math/tex" id="MathJax-Element-10">Fx = g</script>, 首先分解 F=F1F2⋅⋅⋅Fk <script type="math/tex" id="MathJax-Element-11">F = F_{1}F_{2} ··· F_{k}</script>， Fi <script type="math/tex" id="MathJax-Element-12">F_{i}</script> 为简单矩阵，接着计算 x=F−1b <script type="math/tex" id="MathJax-Element-13">x = F^{−1}b</script>通过解一系列问题 Fizi=zi−1 <script type="math/tex" id="MathJax-Element-14">F_{i}z_{i} = z_{i−1}</script> ，其中 z1=F−11g <script type="math/tex" id="MathJax-Element-15">z_{1} = F_{1}^{−1}g</script> 和 x=zk <script type="math/tex" id="MathJax-Element-16">x = z_{k}</script>。

4-2-2 利用稀疏（Exploiting Sparsity）

令 F=P+ρATA <script type="math/tex" id="MathJax-Element-17">F = P + ρA^{T}A</script>，当 F 是稀疏时，
- if P and A are diagonal n × n matrices, then both the factor and solve costs are
O(n).
- If P and A are banded, then so is F.
- If F is banded with bandwidth k, the factorization cost is O(nk2) <script type="math/tex" id="MathJax-Element-18">O(nk^{2})</script> and the back-solve cost is O(nk). In this case, the x-update can be carried out at a cost O(nk2) <script type="math/tex" id="MathJax-Element-19">O(nk^{2})</script>, plus the cost of forming F.

4-2-3 缓存分解（Caching Factorizations）

当 ρ 不变时，我们求解一些列 Fx(i)=g(i),i=1,...,N, <script type="math/tex" id="MathJax-Element-20">Fx^{(i)} = g^{(i)}, i = 1,...,N,</script> 左边 F 一样， 右边 g(i) <script type="math/tex" id="MathJax-Element-21">g^{(i)}</script> 变化。因此，我们可以只求一次 F。

4-2-4 矩阵求逆引理（Matrix Inversion Lemma）

矩阵求逆引理（Matrix Inversion Lemma）

当 所有的 逆元（inverses） 存在时成立。

这意味着 如果 关于 因子矩阵 P 的线性系统 能被有效地求解，和 p 较小时（至少不大于 n），x-update 可以有效地求解。

4-2-5 限制于仿射集的二次函数（Quadratic Function Restricted to an Affine Set）

其中 x+ <script type="math/tex" id="MathJax-Element-22">x^{+}</script> 是关于 u 的仿射函数，更新涉及解一个 KKT（Karush-Kuhn-Tucker）系统，

4-3 平滑目标项（Smooth Objective Terms）

4-3-1 迭代求解（Iterative Solvers）

迭代求解。

4-3-2 提前终止（Early Termination）

提前终止迭代。

4-3-3 热启动（Warm Start）

初始化迭代方法。

4-3-4 二次型目标项（Quadratic Objective Terms）

当 f 为二次型时，在 x-update 使用迭代方法也比直接法要好。

4-4 分解（Decomposition）

4-4-1 块可分离（Block Separability）

当 x 块可分， f 关于 x 的块可分也可块可分，

剩余其他也可分，求解可以并行。

4-4-2 组件可分离（Component Separability）

其中 fi:R→R <script type="math/tex" id="MathJax-Element-23">f_{i} : R → R</script> 和 ATA <script type="math/tex" id="MathJax-Element-24">A^{T}A</script> 是对角矩阵。
x- 最小化可以通过 n 标量最小化 执行。

4-4-3 软阈值（Soft Thresholding）

考虑 f(x)=λ||x||1(with  λ>0) <script type="math/tex" id="MathJax-Element-37">f(x) =λ|| x ||_{1} (with ~~ λ > 0)</script> 和 A=I <script type="math/tex" id="MathJax-Element-38">A = I</script>， xi <script type="math/tex" id="MathJax-Element-39">x_{i}</script>-update 为

它的解为：

其中 软阈值操作（soft thresholding operator） S 为

或者

表示为 shrinkage operator (i.e., moves a point toward zero) 形式

In the language of §4.1, soft thresholding is the proximity operator of the L1 norm.

参考或延伸材料：
[1]Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
[2] 凸优化讲义
[3] A Note on the Alternating Direction Method of Multipliers