凸优化：ADMM(Alternating Direction Method of _admm

4- 一般模式（）
本章主要探讨如何加速 x-和 z-更新步骤。主要考虑三种类型：
terms,and和terms.
我们首先表示 x-更新步骤为：
其中v=?Bz+c?u是一个常量。（对称适用于 z-更新步骤）
4-1 近似算子（）
考虑最简单的情况A=I，因此 x-更新步骤为
右边看做关于 u 的一个函数，标记为proxf,ρ(v)，叫做 f 关于 ρ 的近似算子（theof f withρ ）。
在变分分析，
是 f 的或 -，与接近点算（ point）的理论联系起来。因此接近算子（）中的 x-最小化被称为接近端最小化（）。
当 f 足够简单时，x- 就能评估分析。例如，f 是一个闭合非空凸集 C 的指示函数时，
x- 为
其中ΠC为 C 上的映射（范式）。等式成立与 ρ 无关。更多例子见 [41]
[41] P. L.and J. C. , “in,” arXiv:0912.3522, 2009.
4-2 二次型目标项（Terms）
假设 f 为（凸）二次函数，
其中P∈Sn+，对称正半定 n × n 矩阵。
假设P+ρATA是可逆的，x+是 u 的仿射函数（）
换句话说，计算 x- 等于求解一个关于正定系数矩阵（） P+ρATA和ρATv?q的线性系统。
4-2-1 直接法（）
求解Fx=g , 首先分解F=F1F2???Fk，Fi为简单矩阵，接着计算x=F?1b 通过解一系列问题Fizi=zi?1，其中z1=F?11g和x=zk。
4-2-2 利用稀疏（）
令F=P+ρATA，当 F 是稀疏时，
- if P and A aren × n , then both theand solve costs are
O(n).
- If P and A are , then so is F.
- If F iswithk, thecost isO(nk2)and the back-solve cost is O(nk). In this case, the x- can beout at a costO(nk2) , plus the cost ofF.
4-2-3 缓存分解（）
当 ρ 不变时，我们求解一些列Fx(i)=g(i),i=1,...,N,左边 F 一样，右边g(i)变化。因此，我们可以只求一次 F 。
4-2-4 矩阵求逆引理（Lemma）
矩阵求逆引理（Lemma）
当所有的逆元（）存在时成立。
这意味着如果关于因子矩阵 P 的线性系统能被有效地求解，和 p 较小时（至少不大于 n），x- 可以有效地求解。
4-2-5 限制于仿射集的二次函数（to anSet）
其中x+是关于 u 的仿射函数，更新涉及解一个 KKT（-Kuhn-）系统，
4-3 平滑目标项（Terms） 4-3-1 迭代求解（）
迭代求解。
4-3-2 提前终止（Early ）
提前终止迭代。
4-3-3 热启动（Warm Start）
【凸优化：ADMM(Alternating Direction Method of】初始化迭代方法。
4-3-4 二次型目标项（Terms）
当 f 为二次型时，在 x- 使用迭代方法也比直接法要好。
4-4 分解（） 4-4-1 块可分离（Block ）
当 x 块可分，f 关于 x 的块可分也可块可分，
剩余其他也可分，求解可以并行。
4-4-2 组件可分离（）
其中fi:R→R和ATA是对角矩阵。
x- 最小化可以通过 n 标量最小化执行。
4-4-3 软阈值（Soft ）
考虑f(x)=λ||x||1(withλ>0)和A=I，xi - 为
它的解为：
其中软阈值操作（soft） S 为

文章插图
或者
表示为(i.e., moves a pointzero) 形式
In theof §4.1, softis theof the L1 norm.
参考或延伸材料：
[1]andvia theof
[2] 凸优化讲义
[3] A Note on theof