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

时间:2024-04-03 14:25:09

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

算法简介

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


概念定义

临近算子(proximity operator)

proxf(x)=argminyRnf(y)+12||xy||2

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

Morean信封(Morean envelope)

ef(x)=minyRnf(y)+12||xy||22

  (这个玩意儿好像现在挺火,不过下文貌似没用到)

集合X的指示函数(indicator function of X)

lX(x)={0,xX,xX

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

minxXg(x)minxRng(x)+lX(x)

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

投影算子(projection operator)

projX(x)=argminyX||yx||2=argminyRnlX(x)+12||yx||2

  当f(x)=lX(x)时,projx(x)=proxf(x)

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

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

  此外,关于投影算子还有以下结论:

||proxf(x)proxf(y)||||xy||,x,y

  也就是,2个在集合外的点x,y之间的距离,一定大于这两点在凸集合X上的投影的距离,如下图所示(L2L1):

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

近端梯度(proximal gradient)

  设f(x)=f0(x)+f1(x)f0,f1f1,那么近端梯度

̃ f(x)=xproxf0(xf1(x))

  其中:
proxf0(z)=argminyXf0(y)+12||zy||2


近端梯度法流程

  目标函数:minxRnf(x)=f0(x)+f1(x)f1f2

迭代 r = 0,1,2,…

  xr+1=proxαrf0[xrαrf1(xr)]

  • f0=0
  • f1=0

算法改进

最优性条件(Optimality Condition):

x=argminX{f0(x)+<f1(x),xx>+12α||xx||2}

PG 迭代函数:

xr+1=argminX{f0(x)+<f1(xr),xxr>+12αr||xxr||2}

Bregman Distance

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

B(x,y)=μ(x)μ(y)<μ(y),xy>

  • 对于所有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)12||xy||2,x,y

  • 如果μ(x)=12||x||2,那么B(x,y)=12||xy||2

近端梯度下降法流程

  目标函数:minxRnf(x)=f0(x)+f1(x)f1f2

迭代 r = 0,1,2,…

  xr+1=argminxX{f0(x)+<f1(xr),xxr>+12αrB(x,xr)}

  当xXand||xx||Dandf(x)f(x0)andf(x0)f(x)2LD2时,迭代结束,跳出循环。