當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

UA MATH567 高维统计专题3 含L1-norm的凸优化4 Nesterov方法与Accelerate Proximal Gradient

發布時間：2025/4/14 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了 UA MATH567 高维统计专题3 含L1-norm的凸优化4 Nesterov方法与Accelerate Proximal Gradient 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

UA MATH567 高維統計專題3 含L1-norm的凸優化4 一階方法的加速

- Nesterov方法
- Accelerate Proximal Gradient (APG)

梯度下降與Proximal gradient descent都是一階方法，也就是借助目標函數的某種一階導進行迭代找最小值的方法，假設目標函數 $f (x)$ 是一個平滑的凸函數，則對于 $min_x f(x)$ ，一階方法可以用下面的遞推式表示
$xk+1=?k(x0,x1,?,xk,?f(x0),?f(x1),?,?f(xk))x_{k+1}=\phi_k(x_0,x_1,\cdots,x_k,\nabla f(x_0),\nabla f(x_1),\cdots,\nabla f(x_k))$

但是一階方法只利用了梯度信息，也就是單調性的信息（ $k$ 次迭代后誤差為 $O (1 / k)$ ，而誤差的下界為 $O(1/k^2)$ ），所以一階方法還有可以提高的空間。

Nesterov方法

Nesterov (1983)認為，一階方法會出現oscillation，也就是如下圖所示的，下降路徑存在很嚴重的“震蕩”，他覺得在當次下降中，比如在 $x_2$ 到 $x_3$ 的下降過程中，下降方向不應該只受到 $x_2$ 處梯度或者次梯度的影響，而是應該綜合 $x_2$ 處的梯度、次梯度以及 $x_1$ 到 $x_2$ 下降的“慣性”，所以Nesterov引入了一種Momentum用來修正下降方向。

基于Nesterov的思想，遞推式可以寫成
$xk+1=xk?α?f(xk)?GradientDescent+β(xk?xk?1)?Momentumx_{k+1}=\underbrace{x_k-\alpha\nabla f(x_k)}_{Gradient\ Descent}+\underbrace{\beta(x_k-x_{k-1})}_{Momentum}$

這個式子只是簡單描述Nesterov的思想，具體算法實現有很多種形式，比較常用的一種是：

假設 $?f\nabla f$ 是 $L$ -Lipschitz函數，取 $α=1/L\alpha=1/L$ , $t_1=1$ ，按下面的遞推式迭代
$tk+1=1+1+4tk22βk+1=tk?1tk+1pk+1=xk+βk+1(xk?xk?1)xk+1=pk+1?α?f(pk+1)t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2} \\ \beta_{k+1}=\frac{t_k-1}{t_{k+1}} \\ p_{k+1}=x_k+\beta_{k+1}(x_k-x_{k-1}) \\ x_{k+1}=p_{k+1}-\alpha\nabla f(p_{k+1})$

Accelerate Proximal Gradient (APG)

第二講介紹了Proximal Gradient Descent，在分解 $F = f + g$ 以及 $?f\nabla f$ 是 $L$ -Lipschitz函數的條件下，Proximal Gradient Descent可以用兩個公式表示出來：
$wk=xk??f(xk)Lxk+1=proxg/L(wk)w_k=x_k-\frac{\nabla f(x_k)}{L} \\ x_{k+1}=prox_{g/L}(w_k)$

其中 $prox_g$ 是凸函數 $g$ 的proximal operator為
$proxg(w)=arg?min?xg(x)+12∥x?w∥22prox_g(w)=\argmin_x \ g(x)+\frac{1}{2}\left\| x-w\right\|^2_2$

既然Proximal Gradient Descent的第一步也是一階方法，我們也就可以用Nesterov方法做加速：

$t1=1,tk+1=1+1+4tk22βk+1=tk?1tk+1pk+1=xk+βk+1(xk?xk?1)wk+1=pk+1?1L?f(pk+1)xk+1=proxg/L(wk)t_1= 1,t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2} \\ \beta_{k+1}=\frac{t_k-1}{t_{k+1}} \\ p_{k+1}=x_k+\beta_{k+1}(x_k-x_{k-1}) \\ w_{k+1}=p_{k+1}-\frac{1}{L}\nabla f(p_{k+1}) \\ x_{k+1}=prox_{g/L}(w_k)$

這個算法被稱為Accelerate Proximal Gradient (APG)，這里附一個用APG做Basis Pursuit問題
$min?x∥x∥1s.t.y=Ax\min_x \ \left\| x\right\|_1 \\ s.t.\ \ y=Ax$

的R代碼示例（請讀者自行調試）

soft.threshold <- function(x,tau){len0 = length(x)y = rep(0,len0)for(index0 in 1:len0){if(x[index0]>=tau){y[index0] = x[index0]-tau}if(x[index0]<=-tau){y[index0] = x[index0]+tau}}return(y) }APG <- function(y,A,x0,lambda,mu,maxiter = 100,eps = 1e-3){x1 = x0t1 = 1L = abs(max(eigen(t(A)%*%A)$values))numiter = 0diff.x = 1while(numiter<maxiter & diff.x>=eps){t = 0.5*(1+sqrt(1+4*t1^2))beta = (t1 - 1)/tp = x1 + beta*(x1 - x0)w = p - (t(A)%*%lambda + mu*t(A)%*%(A%*%p-y))/Lx = soft.threshold(w,1/L)diff.x = sqrt(sum((x-x1)^2))numiter = numiter + 1x0 = x1x1 = x}return(x1) }

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计专题3 含L1-norm的凸优化4 Nesterov方法与Accelerate Proximal Gradient的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： UA MATH567 高维统计专题3 含
下一篇：物理光学10 相干光与相干性