近端梯度法（Proximal Gradient Method ，PG）

算法简介

  近端梯度法是一种特殊的梯度下降方法，主要用于求解目标函数不可微的最优化问题。如果目标函数在某些点是不可微的，那么该点的梯度无法求解，传统的梯度下降法也就无法使用。PG算法的思想是，使用临近算子作为近似梯度，进行梯度下降。

---

概念定义

临近算子（proximity operator）

<script type="math/tex; mode=display" id="MathJax-Element-1"> prox_f(x)=arg\min_{y\in R^n}f(y)+\frac{1}{2}||x-y||^2 </script>

  其中函数f可能是非光滑（即不可微）的。临近算子是对梯度的延伸，当函数f为光滑函数时，该临近算子就是梯度。

Morean信封（Morean envelope）

<script type="math/tex; mode=display" id="MathJax-Element-2"> e_f(x)=\min_{y\in R^n}f(y)+\frac{1}{2}||x-y||_2^2 </script>

  （这个玩意儿好像现在挺火，不过下文貌似没用到）

集合X的指示函数（indicator function of X）

<script type="math/tex; mode=display" id="MathJax-Element-3"> l_X(x)=\left\{ \begin{aligned}&0,\quad x\in X\\&\infty, \quad x\notin X \end{aligned} \right. </script>

  其中X是一个凸集合。利用指示函数，我们可以将有约束问题写成无约束问题,如下：

<script type="math/tex; mode=display" id="MathJax-Element-4"> \min_{x\in X}g(x) \iff \min_{x\in R^n}g(x)+l_X(x) </script>
  当x不在X中，等式为无穷大，因此x肯定不是最优值。因此就等于限定了x在凸集合X中。

投影算子（projection operator）

<script type="math/tex; mode=display" id="MathJax-Element-5"> \begin{equation} \begin{aligned} & proj_X(x)=arg\min_{y\in X}||y-x||^2 \\ & =arg\min_{y\in R^n}l_X(x)+\frac{1}{2}||y-x||^2 \\ \end{aligned}\end{equation} </script>

  当f(x)=lX(x)<script type="math/tex" id="MathJax-Element-6">f(x)=l_X(x)</script>时，projx(x)=proxf(x)<script type="math/tex" id="MathJax-Element-7"> proj_x(x)=prox_f(x)</script>。

  解释一下这里投影的含义：一个点x在集合X上的投影，就是X上离x的欧几里得距离最近的点。如下图：

  此外，关于投影算子还有以下结论：

<script type="math/tex; mode=display" id="MathJax-Element-8"> ||prox_f(x)-prox_f(y)||\le||x-y||,\quad \forall x,y </script>
  也就是，2个在集合外的点x，y之间的距离，一定大于这两点在凸集合X上的投影的距离，如下图所示（L2≥L1<script type="math/tex" id="MathJax-Element-9">L_2\ge L_1</script>）：

近端梯度（proximal gradient）

  设f(x)=f0(x)+f1(x)，其中f0,f1为凸函数，f1为光滑函数<script type="math/tex" id="MathJax-Element-10">f(x)=f_0(x)+f_1(x)，其中f_0,f_1为凸函数，f_1为光滑函数</script>，那么近端梯度

<script type="math/tex; mode=display" id="MathJax-Element-11"> \tilde{\nabla}f(x)=x-prox_{f_0}(x-\nabla f_1(x)) </script>
  其中：
<script type="math/tex; mode=display" id="MathJax-Element-12"> prox_{f_0}(z)=arg\min_{y\in X}f_0(y)+\frac{1}{2}||z-y||^2 </script>

---

近端梯度法流程

  目标函数：minx∈Rnf(x)=f0(x)+f1(x)f1非光滑，f2光滑<script type="math/tex" id="MathJax-Element-13">\min_{x\in R^n}f(x)=f_0(x)+f_1(x) \quad f_1非光滑，f_2光滑</script>

迭代 r = 0，1，2，…

  xr+1=proxαrf0[xr−αr∇f1(xr)]<script type="math/tex" id="MathJax-Element-14">x^{r+1}=prox_{\alpha^r f_0}[x^r-\alpha^r\nabla f_1(x^r)]</script>

• 当f0=0⇒梯度下降法<script type="math/tex" id="MathJax-Element-15">当f_0=0 \Rightarrow 梯度下降法</script>
• 当f1=0⇒近端点法<script type="math/tex" id="MathJax-Element-16">f_1=0 \Rightarrow 近端点法</script>

---

算法改进

最优性条件(Optimality Condition)：

<script type="math/tex; mode=display" id="MathJax-Element-17"> x^*=arg\min_{X}\{ f_0(x)+<\nabla f_1(x^*),x-x^* >+\frac{1}{2\alpha}||x-x^*||^2 \} </script>

PG 迭代函数：

<script type="math/tex; mode=display" id="MathJax-Element-18"> x^{r+1}=arg\min_{X}\{ f_0(x)+<\nabla f_1(x^r),x-x^r >+\frac{1}{2\alpha^r}||x-x^r||^2 \} </script>

Bregman Distance

  我们定义强凸可微函数μ(x)<script type="math/tex" id="MathJax-Element-19">\mu(x)</script>,那么我们可以用Bregman Distance代替上面的2范数。Bregman Distance 函数如下：

<script type="math/tex; mode=display" id="MathJax-Element-20"> B(x,y)=\mu(x)-\mu(y)-<\nabla\mu(y),x-y> </script>

• 对于所有x，y，有B(x,y)≥0<script type="math/tex" id="MathJax-Element-21">B(x,y)\ge 0</script>，且 B(x,y)=0, iff x=y 。因此B(x,y)是一种近端测量。

• Bregman Distance 不满足对称性：B(x,y)≠B(y,x)<script type="math/tex" id="MathJax-Element-22">B(x,y)\ne B(y,x)</script>。通过缩放我们可以假定
  

  B(x,y)≥12||x−y||2,∀x,y
  <script type="math/tex; mode=display" id="MathJax-Element-23"> B(x,y)\ge \frac{1}{2}||x-y||^2,\quad \forall x,y </script>

• 如果μ(x)=12||x||2<script type="math/tex" id="MathJax-Element-24">\mu(x)=\frac{1}{2}||x||^2</script>，那么B(x,y)=12||x−y||2<script type="math/tex" id="MathJax-Element-25">B(x,y)=\frac{1}{2}||x-y||^2</script>

近端梯度下降法流程

  目标函数：minx∈Rnf(x)=f0(x)+f1(x)f1非光滑，f2光滑<script type="math/tex" id="MathJax-Element-26">\min_{x\in R^n}f(x)=f_0(x)+f_1(x) \quad f_1非光滑，f_2光滑</script>

迭代 r = 0，1，2，…

  xr+1=argminx∈X{f0(x)+<∇f1(xr),x−xr>+12αrB(x,xr)}<script type="math/tex" id="MathJax-Element-27">x^{r+1}=arg\min_{x\in X} \{f_0(x)+<\nabla f_1(x^r),x-x^r >+\frac{1}{2\alpha^r}B(x,x^r) \}</script>

  当x∈Xand||x−x∗||≤Dandf(x)≤f(x0)andf(x0)−f(x∗)≤2LD2<script type="math/tex" id="MathJax-Element-28">x\in X\quad and \quad||x-x^*||\le D\quad and \quad f(x)\le f(x^0)\quad and \quad f(x^0)-f(x^*)\le 2LD^2</script>时，迭代结束，跳出循环。