Proximal Algorithms--Accelerated proximal gradient method

4.3 Accelerated proximal gradient method：

加速近端梯度方法：
基本的近端梯度方法的所謂的“加速”版本，就是在算法中包含了一個外推(extrapolation)步驟，一個簡單的版本是：

yk+1:=xk+ωk(xk?xk?1)

xk+1:=proxλkg(yk+1?λk▽f(yk+1))

其中ωk∈[0,1)是外推參數，λk是一般的步長。這些參數必須以特定的方式進行選擇才能達到收斂加速的效果。一個簡單的選擇是：

ωk=kk+3

仍然需要選擇步長λk。
當▽f是Lipschitz連續，其常數為L。當使用固定步長λk=λ∈(0,1/L]時，該算法收斂速度為O(1/k2)。如果L未知的話，使用線性搜索確定步長λk。