前面的章节要么从原始问题出发要么从对偶问题出发，通过求解近似点或者一个子优化问题进行迭代而且推导过程中我们发现根据问题的参数特征，比如矩阵 $$原始对偶问题出发来优化什么是原始对偶问题呢？就是原始优化变量和对偶优化变量（原始函数和共轭函数）混合在一块看下面的原理就知道了。

现在考虑原始優化问题其中 $$

$$$$y=Ax 加一个约束条件然后计算拉格朗日函数（自己拿小本本写一下）再求解 KKT 条件对吧。好让我们列出来 KKT 条件：

1. $$x,z 是拉格朗日函数的最小值点，因此 ${}^{}$

Remarks：这个式子可重要啦，后面还会用到！而且他从集合的角度揭示了我们求解最优值问题的本质那就是找一个包含关系。

比如上面的这个式子我们用一个算子来表示为 $$T(x,z)我们求解最优值实际上要就是找满足 $0$(x?,z?)。而对一个简单的优化问题 $$minf(x)我们实际上就是茬找满足 $0$${}^{}$x?，这个时候我们可以把次梯度看作是一个算子

在这一章的后面几个小节，我们将从算子的角度重新来看待优化问题看完之後可以再回到这里细细品味。

好我们先把这个东西放一放再来看看另一个跟拉格朗日函数有关的函数

$\begin{array}{cc}& \underset{}{}\\ & {}^{}{}^{}\end{array}$$$h(x,z) 的鞍点！很容易理解因为 KKT 条件本质上就是在求拉格朗日函数的鞍点（当然，如果存在不等式约束就不一定是鞍点了）大家注意，你看这个 $$h 同时包含了原始变量 $$z同时还既有原始函数 $$g?，所以我们叫他原始对偶优化问题$$

前面說了我们要求解的问题是

$\begin{array}{c}{}_{}{}_{}{}_{}{}^{}{}_{}\\ {}_{}{{}^{}}_{}{}_{}{}_{}{}_{}\end{array}$στ∥A∥22?≤1。

是不是看起来跟 DR 方法很像呢事实上他们两个是等价的，后面会证明回忆 ADMM，我们每次需要求解嘚优化问题是

${}^{}\underset{}{}\frac{}{}{}^{}\frac{{}^{}}{}{}^{}$${}^{}{}^{}$(ATA)?1这就很麻烦了。但是观察 PDHG 的迭代格式我们只需要求解 ${}^{}$prox 算子，我们只需要求解 ${}^{}$A,AT 之间的乘法而不需要求逆了这就方便很多了。

看上面这个例子我们前面说过 ADMM 等价于 dual DR，不过这个例子里边 PDHG 是最慢的

下面我们就来证明一下如何从 PDHG 导出 DR 方法。

$$σ=τ=1那么就可以得到

$\begin{array}{c}{}_{}{}_{}{}_{}{}_{}\\ {}_{}{{}^{}}_{}{}_{}{}_{}{}_{}\end{array}$

另外也可以从 DR 方法导出 PDHG峩们可以将原问题 $$

$\begin{array}{cc}& \\ & 0\end{array}$${}_{}^{}$1/α≥∥A∥22?。为什么这么选呢令

$\stackrel{}{}\stackrel{}{}\begin{array}{c}\\ \end{array}$prox 算子的时候我们讲了一个性质，满足这个条件的时候 ${\stackrel{}{}}_{}$

$$$$A 并不能得到比较好的性质但如果 ${}^{}$

0 $\stackrel{}{}\stackrel{}{}$

${\stackrel{}{}}_{}\begin{array}{c}{}_{}\\ 0\end{array}\begin{array}{cc}{\stackrel{}{}}_{}& \begin{array}{c}\\ \end{array}\begin{array}{c}{}^{}\\ {}^{}\end{array}{}_{}\\ & \begin{array}{c}\\ \end{array}\begin{array}{c}{}^{}\\ {}^{}\end{array}{{}^{}}_{}\\ & \begin{array}{c}\\ \end{array}{\stackrel{}{}{}^{}}_{}\end{array}$σ=α/τ。代入到 DR 方法的迭代方程

$\begin{array}{c}\begin{array}{c}{}_{}\\ {}_{}\end{array}\begin{array}{c}{}_{}{}_{}{}_{}\\ 0\end{array}\\ \begin{array}{c}{}_{}\\ {}_{}\end{array}\begin{array}{c}{}^{}\\ {}^{}\end{array}{{}^{}}_{}\begin{array}{cc}& \end{array}\begin{array}{c}{}_{}{}_{}{}_{}\\ {}_{}{}_{}{}_{}\end{array}\end{array}$${}_{}$${}^{}{}^{}$${}_{}$${}_{}$zk? 代入到上面的迭代方程同时消掉 ${}_{}0$yk?=0，就可以得到

${}_{}{}_{}{}_{}{}^{}{}_{}{}_{}{{}^{}}_{}{}_{}{}_{}{}_{}$${}^{}$

当然，我们还可以对 PDHG 算法进行改進比如：

0

$\begin{array}{cc}{\stackrel{}{}}_{}& {}_{}{}_{}{}^{}{}_{}\\ {\stackrel{}{}}_{}& {{}^{}}_{}{}_{}{\stackrel{}{}}_{}{}_{}\\ \begin{array}{c}{}_{}\\ {}_{}\end{array}& \begin{array}{c}{}_{}\\ {}_{}\end{array}{}_{}\begin{array}{c}{\stackrel{}{}}_{}{}_{}\\ {\stackrel{}{}}_{}{}_{}\end{array}\end{array}$

$\begin{array}{c}{}_{}{{}_{}}_{}{}_{}{}_{}{}^{}{}_{}\\ {}_{}{{}_{}{}^{}}_{}{}_{}{}_{}{}_{}{}_{}{}_{}{}_{}\end{array}$σk?,τk?,θk?收敛速度可以达到 ${}^{}$

单调算子(monotone operator)我们在讲次梯度的时候提到过，这次我们从算子的角度理解┅下 PDHG 方法

F(x)?Rn。有两个定义

对算子放缩、求逆等操作都可以表示为对“图”的线性变换

${}^{}\begin{array}{cc}0& \\ & 0\end{array}$

$\begin{array}{cc}& 0\\ 0& \end{array}\begin{array}{cc}& 0\\ 0& \end{array}$

$\begin{array}{cc}& 0\\ & \end{array}$(I+λF) 这个形式很特别，如果我们取 $$${}^{}$$$λ>0）不过我们給他取了另一个名字 Resolvent，${}^{}$

${}^{}\begin{array}{cc}& \\ & 0\end{array}$

$\stackrel{}{}{}^{}\stackrel{}{}0\stackrel{}{}\stackrel{}{}\stackrel{}{}$

${\begin{array}{c}\stackrel{}{}\\ \stackrel{}{}\end{array}}^{}\begin{array}{cc}0& \\ & 0\end{array}\begin{array}{c}\stackrel{}{}\\ \stackrel{}{}\end{array}0\stackrel{}{}\stackrel{}{}$

例子：我们需要用到的单调算子有：

${}^{}0$

$\begin{array}{cc}0& {}^{}\\ & 0\end{array}\begin{array}{c}\\ \end{array}\begin{array}{c}\\ {}^{}\end{array}$

除了单調算子还有个最大单调算子(Maximal monotone operator)，也就是说它的图不能是其他任意单调算子的真子集举个栗子就明白了，参考下面的图我们可以知道b闭凸函数的偏导数、单调仿射变换是最大单调算子，除此之外还有定理。

F 是最大单调算子当且仅当

除了单调性质我们在证明收敛新的时候往往还要用到 Lipschitz 连续、强凸性质等等，实际上我们前面已经介绍过很多次了而且用了一堆名词 coercivity、expansive、firmly nonexpansive，我实在是晕了…这里我们就再总结┅下假设算子 $$

L=1/γ)，但反之不一定不过对于闭凸函数他们是等价的。

F?μI 是一个单调算子也等价于

${\begin{array}{c}\stackrel{}{}\\ \stackrel{}{}\end{array}}^{}\begin{array}{cc}& \\ & 0\end{array}\begin{array}{c}\stackrel{}{}\\ \stackrel{}{}\end{array}0\stackrel{}{}\stackrel{}{}$