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

算法简介

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

p r o x f (x) = a r g min y \in R n f (y) + 12 | | x - y | | 2

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

e f (x) = min y \in R n f (y) + 12 | | x - y | | 22

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

l X (x) = {0, x \in X \infty, x \notin X

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

min x \in X g (x) ⟺ min x \in R n g (x) + l X (x)

当x不在X中，等式为无穷大，因此x肯定不是最优值。因此就等于限定了x在凸集合X中。

p r o j X (x) = a r g min y \in X | | y - x | | 2 = a r g min y \in R n l X (x) + 12 | | y - x | | 2

当f(x)=lX(x)时，projx(x)=proxf(x)。

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

近端梯度法(Proximal Gradient Method, PG)

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

| | p r o x f (x) - p r o x f (y) | | \leq | | x - y | |, \forall x, y

也就是，2个在集合外的点x，y之间的距离，一定大于这两点在凸集合X上的投影的距离，如下图所示（L2≥L1）：

近端梯度法(Proximal Gradient Method, PG)

设f(x)=f0(x)+f1(x)，其中f0,f1为凸函数，f1为光滑函数，那么近端梯度

\nabla ̃ f (x) = x - p r o x f 0 (x - \nabla f 1 (x))

其中：

p r o x f 0 (z) = a r g min y \in X f 0 (y) + 12 | | z - y | | 2

目标函数：minx∈Rnf(x)=f0(x)+f1(x)f1非光滑，f2光滑

迭代 r = 0，1，2，…

xr+1=proxαrf0[xr−αr∇f1(xr)]

x * = a r g min X {f 0 (x) + < \nabla f 1 (x *), x - x * > + 1 2 α | | x - x * | | 2}

x r + 1 = a r g min X {f 0 (x) + < \nabla f 1 (x r), x - x r > + 1 2 α r | | x - x r | | 2}

我们定义强凸可微函数μ(x),那么我们可以用Bregman Distance代替上面的2范数。Bregman Distance 函数如下：

B (x, y) = μ (x) - μ (y) - < \nabla μ (y), x - y >

对于所有x，y，有B(x,y)≥0，且 B(x,y)=0, iff x=y 。因此B(x,y)是一种近端测量。
Bregman Distance 不满足对称性：B(x,y)≠B(y,x)。通过缩放我们可以假定
$B (x, y) \geq 12 | | x - y | | 2, \forall x, y$
如果μ(x)=12||x||2，那么B(x,y)=12||x−y||2

目标函数：minx∈Rnf(x)=f0(x)+f1(x)f1非光滑，f2光滑

迭代 r = 0，1，2，…

xr+1=argminx∈X{f0(x)+<∇f1(xr),x−xr>+12αrB(x,xr)}

当x∈Xand||x−x∗||≤Dandf(x)≤f(x0)andf(x0)−f(x∗)≤2LD2时，迭代结束，跳出循环。