Jensen’s 不等式： f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y) f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)
一階條件等價于梯度單調性： ( ∇ f ( x ) − ∇ f ( y ) ) T ( x − y ) ≥ 0 for all x , y ∈ dom f (\nabla f(x)-\nabla f(y))^{T}(x-y) \geq 0 \quad \text { for all } x, y \in \operatorname{dom} f (∇f(x)−∇f(y))T(x−y)≥0 for all x,y∈domf
也就是說凸函數的梯度 ∇ f : R n → R n \nabla f: R^n\to R^n ∇f:Rn→Rn 是一個單調映射。
2. Lipschitz continuity
函數 f f f 的梯度滿足**利普希茨連續(Lipschitz continuous)**的定義為
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ∗ ≤ L ∥ x − y ∥ for all x , y ∈ dom f \|\nabla f(x)-\nabla f(y)\|_{*} \leq L\|x-y\| \quad \text { for all } x, y \in \operatorname{dom} f ∥∇f(x)−∇f(y)∥∗≤L∥x−y∥ for all x,y∈domf
也被稱為 L-smooth。有了這個條件，我們可以推出很多個等價性質，這裡省略了證明過程
凸優化學習筆記 15：梯度方法
也就是說下面的式子都是等價的
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ∗ ≤ L ∥ x − y ∥ for all x , y ∈ dom f \|\nabla f(x)-\nabla f(y)\|_{*} \leq L\|x-y\| \quad \text { for all } x, y \in \operatorname{dom} f ∥∇f(x)−∇f(y)∥∗≤L∥x−y∥ for all x,y∈domf
( ∇ f ( x ) − ∇ f ( y ) ) T ( x − y ) ≤ L ∥ x − y ∥ 2 for all x , y ∈ dom f (\nabla f(x)-\nabla f(y))^{T}(x-y) \leq L\|x-y\|^{2} \quad \text { for all } x, y \in \operatorname{dom} f (∇f(x)−∇f(y))T(x−y)≤L∥x−y∥2 for all x,y∈domf
f ( y ) ≤ f ( x ) + ∇ f ( x ) T ( y − x ) + L 2 ∥ y − x ∥ 2 for all x , y ∈ dom f f(y) \leq f(x)+\nabla f(x)^{T}(y-x)+\frac{L}{2}\|y-x\|^{2} \quad \text { for all } x, y \in \operatorname{dom} f f(y)≤f(x)+∇f(x)T(y−x)+2L∥y−x∥2 for all x,y∈domf
( ∇ f ( x ) − ∇ f ( y ) ) T ( x − y ) ≥ 1 L ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ∗ 2 for all x , y (\nabla f(x)-\nabla f(y))^{T}(x-y) \geq \frac{1}{L}\|\nabla f(x)-\nabla f(y)\|_{*}^{2} \quad \text { for all } x, y (∇f(x)−∇f(y))T(x−y)≥L1∥∇f(x)−∇f(y)∥∗2 for all x,y
g ( x ) = L 2 ∥ x ∥ 2 2 − f ( x ) is convex g(x)=\frac{L}{2}\Vert x\Vert_2^2-f(x) \ \text{ is convex} g(x)=2L∥x∥22−f(x) is convex
Remarks 1：
上面的第 3 個式子
f ( y ) ≤ f ( x ) + ∇ f ( x ) T ( y − x ) + L 2 ∥ y − x ∥ 2 for all x , y ∈ dom f f(y) \leq f(x)+\nabla f(x)^{T}(y-x)+\frac{L}{2}\Vert y-x\Vert^{2} \quad \text { for all } x, y \in \operatorname{dom} f f(y)≤f(x)+∇f(x)T(y−x)+2L∥y−x∥2 for all x,y∈domf
實際上定義了一個二次曲線，這個曲線是原始函數的 Quadratic upper bound
凸優化學習筆記 15：梯度方法
并且由這個式子可以推導出
1 2 L ∥ ∇ f ( z ) ∥ ∗ 2 ≤ f ( z ) − f ( x ⋆ ) ≤ L 2 ∥ z − x ⋆ ∥ 2 for all z \frac{1}{2 L}\Vert\nabla f(z)\Vert_{*}^{2} \leq f(z)-f\left(x^{\star}\right) \leq \frac{L}{2}\left\Vert z-x^{\star}\right\Vert^{2} \quad \text { for all } z 2L1∥∇f(z)∥∗2≤f(z)−f(x⋆)≤2L∥z−x⋆∥2 for all z
這個式子中的上界 L 2 ∥ z − x ⋆ ∥ 2 \frac{L}{2}\left\|z-x^{\star}\right\|^{2} 2L∥z−x⋆∥2 帶有 x ⋆ x^\star x⋆ 是未知的，而下界隻與目前值 z z z 有關，是以在優化過程中我們可以判斷目前的 f ( z ) f(z) f(z) 與最優值的距離至少為 1 2 L ∥ ∇ f ( z ) ∥ ∗ 2 \frac{1}{2 L}\|\nabla f(z)\|_{*}^{2} 2L1∥∇f(z)∥∗2，如果這個值大于0，那麼我們一定還沒得到最優解。
Remarks 2：
上面的最後一個式子
( ∇ f ( x ) − ∇ f ( y ) ) T ( x − y ) ≥ 1 L ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ∗ 2 for all x , y (\nabla f(x)-\nabla f(y))^{T}(x-y) \geq \frac{1}{L}\|\nabla f(x)-\nabla f(y)\|_{*}^{2} \quad \text { for all } x, y (∇f(x)−∇f(y))T(x−y)≥L1∥∇f(x)−∇f(y)∥∗2 for all x,y
被稱為 ∇ f \nabla f ∇f 的 co-coercivity 性質。（這其實有點像 ∇ f \nabla f ∇f 的反函數的 L-smooth 性質，是以它跟 ∇ f \nabla f ∇f 的 L-smooth 性質是等價的）
3. 強凸函數
滿足如下性質的函數被稱為 **m-強凸(m-strongly convex)**的
f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) − m 2 θ ( 1 − θ ) ∥ x − y ∥ 2 for all x , y ∈ dom f , θ ∈ [ 0 , 1 ] f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)-\frac{m}{2} \theta(1-\theta)\|x-y\|^{2} \quad \text { for all } x, y\in\text{dom}f,\theta\in[0,1] f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)−2mθ(1−θ)∥x−y∥2 for all x,y∈domf,θ∈[0,1]
m-強凸跟前面的 L-smooth 實際上非常像，隻不過一個定義了上界，另一個定義了下界。
類似上面的 L-smooth 性質，我們課可以得到下面幾個式子是等價的
f is m-strongly convex f \text{ is m-strongly convex} f is m-strongly convex
( ∇ f ( x ) − ∇ f ( y ) ) T ( x − y ) ≥ m ∥ x − y ∥ 2 for all x , y ∈ dom f (\nabla f(x)-\nabla f(y))^{T}(x-y) \geq m\|x-y\|^{2} \quad \text { for all } x, y \in \operatorname{dom} f (∇f(x)−∇f(y))T(x−y)≥m∥x−y∥2 for all x,y∈domf
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) + m 2 ∥ y − x ∥ 2 for all x , y ∈ dom f f(y) \geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|^{2} \quad \text { for all } x, y \in \operatorname{dom} f f(y)≥f(x)+∇f(x)T(y−x)+2m∥y−x∥2 for all x,y∈domf
g ( x ) = f ( x ) − m 2 ∥ x ∥ 2 is convex g(x) = f(x)-\frac{m}{2}\Vert x\Vert^2 \ \text{ is convex} g(x)=f(x)−2m∥x∥2 is convex
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) + m 2 ∥ y − x ∥ 2 f(y) \geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\Vert y-x\Vert^{2} f(y)≥f(x)+∇f(x)T(y−x)+2m∥y−x∥2
f ( y ) ≤ f ( x ) + ∇ f ( x ) T ( y − x ) + L 2 ∥ y − x ∥ 2 f(y) \leq f(x)+\nabla f(x)^{T}(y-x)+\frac{L}{2}\Vert y-x\Vert^{2} f(y)≤f(x)+∇f(x)T(y−x)+2L∥y−x∥2
⟹ m 2 ∥ z − x ⋆ ∥ 2 ≤ f ( z ) − f ( x ⋆ ) ≤ 1 2 m ∥ ∇ f ( z ) ∥ ∗ 2 \Longrightarrow \frac{m}{2}\left\Vert z-x^{\star}\right\Vert^{2} \leq f(z)-f\left(x^{\star}\right) \leq \frac{1}{2 m}\Vert\nabla f(z)\Vert_{*}^{2} ⟹2m∥z−x⋆∥2≤f(z)−f(x⋆)≤2m1∥∇f(z)∥∗2
⟹ 1 2 L ∥ ∇ f ( z ) ∥ ∗ 2 ≤ f ( z ) − f ( x ⋆ ) ≤ L 2 ∥ z − x ⋆ ∥ 2 \Longrightarrow \frac{1}{2 L}\Vert\nabla f(z)\Vert_{*}^{2} \leq f(z)-f\left(x^{\star}\right) \leq \frac{L}{2}\left\Vert z-x^{\star}\right\Vert^{2} ⟹2L1∥∇f(z)∥∗2≤f(z)−f(x⋆)≤2L∥z−x⋆∥2
例子：如果函數 f f f 既是 m-強凸的，又是(關于2範數) L-smooth 的，那麼
函數 h ( x ) = f ( x ) − m 2 ∥ x ∥ 2 h(x)=f(x)-\frac{m}{2}\Vert x\Vert^2 h(x)=f(x)−2m∥x∥2 是 (L-m)-smooth 的
函數 h h h 的 co-coercivity 可以寫為
( ∇ f ( x ) − ∇ f ( y ) ) T ( x − y ) ≥ m L m + L ∥ x − y ∥ 2 2 + 1 m + L ∥ ∇ f ( x ) − ∇ f ( y ) ∥ 2 2 for all x , y ∈ dom f (\nabla f(x)-\nabla f(y))^{T}(x-y) \geq \frac{m L}{m+L}\|x-y\|_{2}^{2}+\frac{1}{m+L}\|\nabla f(x)-\nabla f(y)\|_{2}^{2} \quad \text { for all } x, y \in \operatorname{dom} f (∇f(x)−∇f(y))T(x−y)≥m+LmL∥x−y∥22+m+L1∥∇f(x)−∇f(y)∥22 for all x,y∈domf
4. 梯度方法收斂性分析
下面給出一些常見梯度下降方法的分析。先回顧一下梯度方法的一般表達式
x k + 1 = x k − t k ∇ f ( x k ) x_{k+1}=x_{k}-t_k \nabla f(x_k) xk+1=xk−tk∇f(xk)
首先有一些假設
f f f convex 且可導， dom f = R n \text{dom}f=R^n domf=Rn
∇ f \nabla f ∇f 關于2範數 L-Lipschitz continuous
最優解有限且可取
4.1 固定步長
固定步長為 t t t，則 x + = x − t ∇ f ( x ) x^+=x-t\nabla f(x) x+=x−t∇f(x)，根據 L-smooth 性質有
f ( x − t ∇ f ( x ) ) ≤ f ( x ) − t ( 1 − L t 2 ) ∥ ∇ f ( x ) ∥ 2 2 f(x-t \nabla f(x)) \leq f(x)-t\left(1-\frac{L t}{2}\right)\|\nabla f(x)\|_{2}^{2} f(x−t∇f(x))≤f(x)−t(1−2Lt)∥∇f(x)∥22
如果 0 < t ≤ 1 / L 0 < t \leq 1/L 0<t≤1/L，則有
f ( x + ) ≤ f ( x ) − t 2 ∥ ∇ f ( x ) ∥ 2 2 f\left(x^{+}\right) \leq f(x)-\frac{t}{2}\|\nabla f(x)\|_{2}^{2} f(x+)≤f(x)−2t∥∇f(x)∥22
這表明(隻要步長 t t t 比較小)函數值總是在不斷減小的。從上面的式子結合凸函數性質我們還可以得到
f ( x + ) − f ⋆ ≤ ∇ f ( x ) T ( x − x ⋆ ) − t 2 ∥ ∇ f ( x ) ∥ 2 2 = 1 2 t ( ∥ x − x ⋆ ∥ 2 2 − ∥ x − x ⋆ − t ∇ f ( x ) ∥ 2 2 ) = 1 2 t ( ∥ x − x ⋆ ∥ 2 2 − ∥ x + − x ⋆ ∥ 2 2 ) \begin{aligned} f\left(x^{+}\right)-f^{\star} & \leq \nabla f(x)^{T}\left(x-x^{\star}\right)-\frac{t}{2}\|\nabla f(x)\|_{2}^{2} \\ &=\frac{1}{2 t}\left(\left\|x-x^{\star}\right\|_{2}^{2}-\left\|x-x^{\star}-t \nabla f(x)\right\|_{2}^{2}\right) \\ &=\frac{1}{2 t}\left(\left\|x-x^{\star}\right\|_{2}^{2}-\left\|x^{+}-x^{\star}\right\|_{2}^{2}\right) \end{aligned} f(x+)−f⋆≤∇f(x)T(x−x⋆)−2t∥∇f(x)∥22=2t1(∥x−x⋆∥22−∥x−x⋆−t∇f(x)∥22)=2t1(∥x−x⋆∥22−∥∥x+−x⋆∥∥22)
從這個式子可以得到我們到最優點 x ⋆ x^\star x⋆ 的距離在不斷減小。那麼可以得到下面的式子
∑ i = 1 k ( f ( x i ) − f ⋆ ) ≤ 1 2 t ∑ i = 1 k ( ∥ x i − 1 − x ⋆ ∥ 2 2 − ∥ x i − x ⋆ ∥ 2 2 ) = 1 2 t ( ∥ x 0 − x ⋆ ∥ 2 2 − ∥ x k − x ⋆ ∥ 2 2 ) ≤ 1 2 t ∥ x 0 − x ⋆ ∥ 2 2 ⟹ f ( x k ) − f ⋆ ≤ 1 k ∑ i = 1 k ( f ( x i ) − f ⋆ ) ≤ 1 2 k t ∥ x 0 − x ⋆ ∥ 2 2 \begin{aligned} \sum_{i=1}^{k}\left(f\left(x_{i}\right)-f^{\star}\right) & \leq \frac{1}{2 t} \sum_{i=1}^{k}\left(\left\|x_{i-1}-x^{\star}\right\|_{2}^{2}-\left\|x_{i}-x^{\star}\right\|_{2}^{2}\right) \\ &=\frac{1}{2 t}\left(\left\|x_{0}-x^{\star}\right\|_{2}^{2}-\left\|x_{k}-x^{\star}\right\|_{2}^{2}\right) \\ & \leq \frac{1}{2 t}\left\|x_{0}-x^{\star}\right\|_{2}^{2} \end{aligned} \\ \Longrightarrow f(x_k)-f^\star\leq\frac{1}{k}\sum_{i=1}^{k}\left(f\left(x_{i}\right)-f^{\star}\right) \leq \frac{1}{2 kt}\left\|x_{0}-x^{\star}\right\|_{2}^{2} i=1∑k(f(xi)−f⋆)≤2t1i=1∑k(∥xi−1−x⋆∥22−∥xi−x⋆∥22)=2t1(∥x0−x⋆∥22−∥xk−x⋆∥22)≤2t1∥x0−x⋆∥22⟹f(xk)−f⋆≤k1i=1∑k(f(xi)−f⋆)≤2kt1∥x0−x⋆∥22
是以普通的固定步長的梯度下降有以下收斂性質
f ( x k + 1 ) < f ( x k ) f(x_{k+1}) < f(x_k) f(xk+1)<f(xk)
∥ x k + 1 − x ⋆ ∥ < ∥ x k − x ⋆ ∥ \Vert x_{k+1}-x^\star\Vert < \Vert x_{k}-x^\star\Vert ∥xk+1−x⋆∥<∥xk−x⋆∥
f ( x k ) − f ⋆ ≤ 1 2 k t ∥ x 0 − x ⋆ ∥ 2 2 f(x_k)-f^\star\leq \frac{1}{2 kt}\left\|x_{0}-x^{\star}\right\|_{2}^{2} f(xk)−f⋆≤2kt1∥x0−x⋆∥22，要想滿足精度 f ( x k ) − f ⋆ ≤ ϵ f(x_k)-f^\star \leq \epsilon f(xk)−f⋆≤ϵ 需要的疊代次數為 O ( 1 / ϵ ) O(1/\epsilon) O(1/ϵ)
4.2 線搜尋
線搜尋就是每步都要計算合适的步長，計算方法為不斷地疊代 t k : = β t k , 0 < β < 1 t_k:=\beta t_k,0<\beta<1 tk:=βtk,0<β<1 直到 t k t_k tk 滿足下面的條件
f ( x k − t k ∇ f ( x k ) ) < f ( x k ) − α t k ∥ ∇ f ( x k ) ∥ 2 2 f\left(x_{k}-t_{k} \nabla f\left(x_{k}\right)\right)<f\left(x_{k}\right)-\alpha t_{k}\left\|\nabla f\left(x_{k}\right)\right\|_{2}^{2} f(xk−tk∇f(xk))<f(xk)−αtk∥∇f(xk)∥22
形象了解就是下面這幅圖，一開始我們的 t k t_k tk 可能很大，表示梯度下降的步長過大，不能使函數值減小，那我們就減小步長 t k = β t k t_k=\beta t_k tk=βtk，直到進入綠線與藍線交點左側這部分，我們就可以保證一定有 f ( x k + 1 ) < f ( x k ) f(x_{k+1})<f(x_k) f(xk+1)<f(xk)，這時就是我們要取的 t k t_k tk，這也是線搜尋的含義，線搜尋實際上就是在搜尋合适的步長 t k t_k tk。
凸優化學習筆記 15：梯度方法
主要到上面的式子中有一個參數 α \alpha α 會影響我們的搜尋結果，比如上圖中 α \alpha α 越大，則綠線的斜率越大，那麼最終搜尋到的 t k t_k tk 應該就越小，表示我們每一步的步長都會更小。實際中往往取 α = 1 / 2 \alpha=1/2 α=1/2，此時理想的搜尋結果實際上就是 quadratic upper bound 的最小值點。也就是說我們用二次上界曲線來近似待優化的函數，而二次上界的最小值點對應的步長就是 t = 1 / L t=1/L t=1/L，但由于我們是線搜尋，實際得到的 t k t_k tk 一般會比這個值略小一點。
凸優化學習筆記 15：梯度方法
另一方面為了保證線搜尋在有限步能夠終止，還需要滿足 t k ≥ t m i n = min { t ^ , β / L } t_k\ge t_{min} =\min\{\hat{t},\beta/L\} tk≥tmin=min{t^,β/L}，其中 t ^ \hat{t} t^ 是預先指定的一個參數。
那麼線搜尋的收斂性怎麼樣呢？首先根據線搜尋的定義一定有
f ( x i + 1 ) ≤ f ( x i ) − t i 2 ∥ ∇ f ( x i ) ∥ 2 2 ≤ f ⋆ + ∇ f ( x i ) T ( x i − x ⋆ ) − t i 2 ∥ ∇ f ( x i ) ∥ 2 2 = f ⋆ + 1 2 t i ( ∥ x i − x ⋆ ∥ 2 2 − ∥ x i + 1 − x ⋆ ∥ 2 2 ) \begin{aligned} f\left(x_{i+1}\right) & \leq f\left(x_{i}\right)-\frac{t_{i}}{2}\left\|\nabla f\left(x_{i}\right)\right\|_{2}^{2} \\ & \leq f^{\star}+\nabla f\left(x_{i}\right)^{T}\left(x_{i}-x^{\star}\right)-\frac{t_{i}}{2}\left\|\nabla f\left(x_{i}\right)\right\|_{2}^{2} \\ &=f^{\star}+\frac{1}{2 t_{i}}\left(\left\|x_{i}-x^{\star}\right\|_{2}^{2}-\left\|x_{i+1}-x^{\star}\right\|_{2}^{2}\right) \end{aligned} f(xi+1)≤f(xi)−2ti∥∇f(xi)∥22≤f⋆+∇f(xi)T(xi−x⋆)−2ti∥∇f(xi)∥22=f⋆+2ti1(∥xi−x⋆∥22−∥xi+1−x⋆∥22)
這表明 f ( x i + 1 ) < f ( x i ) , ∥ x i − x ⋆ ∥ 2 > ∥ x i + 1 − x ⋆ ∥ 2 f(x_{i+1})<f(x_i),\left\|x_{i}-x^{\star}\right\|_{2}>\left\|x_{i+1}-x^{\star}\right\|_{2} f(xi+1)<f(xi),∥xi−x⋆∥2>∥xi+1−x⋆∥2，類似前面固定步長的分析，可以得到
f ( x k ) − f ⋆ ≤ 1 k ∑ i = 1 k ( f ( x i ) − f ⋆ ) ≤ 1 2 k t m i n ∥ x 0 − x ⋆ ∥ 2 2 f(x_k)-f^\star\leq\frac{1}{k}\sum_{i=1}^{k}\left(f\left(x_{i}\right)-f^{\star}\right) \leq \frac{1}{2 kt_{min}}\left\|x_{0}-x^{\star}\right\|_{2}^{2} f(xk)−f⋆≤k1i=1∑k(f(xi)−f⋆)≤2ktmin1∥x0−x⋆∥22
是以對于線搜尋的方法，我們可以得到如下的收斂性質
f ( x i + 1 ) < f ( x i ) f(x_{i+1})<f(x_i) f(xi+1)<f(xi)
∥ x i − x ⋆ ∥ 2 > ∥ x i + 1 − x ⋆ ∥ 2 \left\|x_{i}-x^{\star}\right\|_{2}>\left\|x_{i+1}-x^{\star}\right\|_{2} ∥xi−x⋆∥2>∥xi+1−x⋆∥2
f ( x k ) − f ⋆ ≤ 1 2 k t m i n ∥ x 0 − x ⋆ ∥ 2 2 f(x_k)-f^\star\leq \frac{1}{2 kt_{min}}\left\|x_{0}-x^{\star}\right\|_{2}^{2} f(xk)−f⋆≤2ktmin1∥x0−x⋆∥22
是以線搜尋實際上并不能提高收斂速度的階，他與固定步長的方法都是 O ( 1 / k ) O(1/k) O(1/k) 的，為 sublinear 收斂。
4.3 一階方法的收斂極限
不管是固定步長還是線搜尋，前面的方法都是一階方法，即
x k + 1 ∈ x 0 + span { ∇ f ( x 0 ) , ∇ f ( x 1 ) , … , ∇ f ( x k ) } x_{k+1}\in x_{0}+\operatorname{span}\left\{\nabla f\left(x_{0}\right), \nabla f\left(x_{1}\right), \ldots, \nabla f\left(x_{k}\right)\right\} xk+1∈x0+span{∇f(x0),∇f(x1),…,∇f(xk)}
而理論上也證明一階方法的收斂速度存在極限。
定理(Nesterov)： for every integer k ≤ ( n − 1 ) / 2 k ≤ (n−1)/2 k≤(n−1)/2 and every x 0 x_0 x0, there exist functions in the problem class such that for any first-order method
f ( x k ) − f ⋆ ≥ 3 32 L ∥ x 0 − x ⋆ ∥ 2 2 ( k + 1 ) 2 f\left(x_{k}\right)-f^{\star} \geq \frac{3}{32} \frac{L\left\|x_{0}-x^{\star}\right\|_{2}^{2}}{(k+1)^{2}} f(xk)−f⋆≥323(k+1)2L∥x0−x⋆∥22
也就是說收斂速度最多也就是 O ( 1 / k 2 ) O(1/k^2) O(1/k2)。
4.4 強凸函數的梯度方法
對于強凸函數，即使采用固定步長的梯度方法，也可以得到線性收斂速度！這就是強凸性帶來的好處。
考慮 0 < t < 2 / ( m + L ) 0<t<2/(m+L) 0<t<2/(m+L)，我們有
∥ x + − x ⋆ ∥ 2 2 = ∥ x − t ∇ f ( x ) − x ⋆ ∥ 2 2 = ∥ x − x ⋆ ∥ 2 2 − 2 t ∇ f ( x ) T ( x − x ⋆ ) + t 2 ∥ ∇ f ( x ) ∥ 2 2 ≤ ( 1 − t 2 m L m + L ) ∥ x − x ⋆ ∥ 2 2 + t ( t − 2 m + L ) ∥ ∇ f ( x ) ∥ 2 2 ≤ ( 1 − t 2 m L m + L ) ∥ x − x ⋆ ∥ 2 2 \begin{aligned} \left\|x^{+}-x^{\star}\right\|_{2}^{2} &=\left\|x-t \nabla f(x)-x^{\star}\right\|_{2}^{2} \\ &=\left\|x-x^{\star}\right\|_{2}^{2}-2 t \nabla f(x)^{T}\left(x-x^{\star}\right)+t^{2}\|\nabla f(x)\|_{2}^{2} \\ & \leq\left(1-t \frac{2 m L}{m+L}\right)\left\|x-x^{\star}\right\|_{2}^{2}+t\left(t-\frac{2}{m+L}\right)\|\nabla f(x)\|_{2}^{2} \\ & \leq\left(1-t \frac{2 m L}{m+L}\right)\left\|x-x^{\star}\right\|_{2}^{2} \end{aligned} ∥∥x+−x⋆∥∥22=∥x−t∇f(x)−x⋆∥22=∥x−x⋆∥22−2t∇f(x)T(x−x⋆)+t2∥∇f(x)∥22≤(1−tm+L2mL)∥x−x⋆∥22+t(t−m+L2)∥∇f(x)∥22≤(1−tm+L2mL)∥x−x⋆∥22
也就是說可以得到
∥ x k − x ⋆ ∥ 2 2 ≤ c k ∥ x 0 − x ⋆ ∥ 2 2 , c = 1 − t 2 m L m + L f ( x k ) − f ⋆ ≤ L 2 ∥ x k − x ⋆ ∥ 2 2 ≤ c k L 2 ∥ x 0 − x ⋆ ∥ 2 2 \left\|x_{k}-x^{\star}\right\|_{2}^{2} \leq c^{k}\left\|x_{0}-x^{\star}\right\|_{2}^{2}, \quad c=1-t \frac{2 m L}{m+L} \\ f\left(x_{k}\right)-f^{\star} \leq \frac{L}{2}\left\|x_{k}-x^{\star}\right\|_{2}^{2} \leq \frac{c^{k} L}{2}\left\|x_{0}-x^{\star}\right\|_{2}^{2} ∥xk−x⋆∥22≤ck∥x0−x⋆∥22,c=1−tm+L2mLf(xk)−f⋆≤2L∥xk−x⋆∥22≤2ckL∥x0−x⋆∥22
注意到前面是反比例下降，這裡變成了指數下降。如果要打到精度 f ( x k ) − f ⋆ ≤ ϵ f(x_k)-f^\star \leq \epsilon f(xk)−f⋆≤ϵ 需要的疊代次數為 O ( log ( 1 / ϵ ) ) O(\log(1/\epsilon)) O(log(1/ϵ))
如果我們記 g ( k ) = ∇ f ( x ( k ) ) and F ( k ) = ∇ 2 f ( x ( k ) ) \boldsymbol{g}^{(k)}=\nabla f\left(\boldsymbol{x}^{(k)}\right) \text { and } \boldsymbol{F}^{(k)}=\nabla^{2} f\left(\boldsymbol{x}^{(k)}\right) g(k)=∇f(x(k)) and F(k)=∇2f(x(k))，那麼一階方法就是 x ( k + 1 ) = x ( k ) − α k g ( k ) \boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}-\alpha_{k} \boldsymbol{g}^{(k)} x(k+1)=x(k)−αkg(k)，其中步長 α k \alpha_k αk 可以是固定的，也可以是線搜尋獲得的，一階方法簡單但是收斂速度慢。牛頓方法就是 x ( k + 1 ) = x ( k ) − ( F ( k ) ) − 1 g ( k ) \boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}-\left(\boldsymbol{F}^{(k)}\right)^{-1} \boldsymbol{g}^{(k)} x(k+1)=x(k)−(F(k))−1g(k)，其收斂速度更快，但是海森矩陣計算代價較大。而 BB方法就是用 α k g ( k ) \alpha_{k} \boldsymbol{g}^{(k)} αkg(k) 來近似 ( F ( k ) ) − 1 g ( k ) \left(\boldsymbol{F}^{(k)}\right)^{-1} \boldsymbol{g}^{(k)} (F(k))−1g(k)。
怎麼近似呢？假如定義 s ( k − 1 ) : = x ( k ) − x ( k − 1 ) and y ( k − 1 ) : = g ( k ) − g ( k − 1 ) s^{(k-1)}:=x^{(k)}-x^{(k-1)} \text { and } y^{(k-1)}:=g^{(k)}-g^{(k-1)} s(k−1):=x(k)−x(k−1) and y(k−1):=g(k)−g(k−1)，那麼海森矩陣實際上就是
F ( k ) s ( k − 1 ) = y ( k − 1 ) \boldsymbol{F}^{(k)}s^{(k-1)}=y^{(k-1)} F(k)s(k−1)=y(k−1)
現在的想法就是用 ( α k I ) − 1 (\alpha_k I)^{-1} (αkI)−1 來近似 F ( k ) \boldsymbol{F}^{(k)} F(k)，那麼應該有
( α k I ) − 1 s ( k − 1 ) = y ( k − 1 ) (\alpha_k I)^{-1}s^{(k-1)}=y^{(k-1)} (αkI)−1s(k−1)=y(k−1)
這個問題用最小二乘就可以解決了，下面兩種選擇都可以
α k − 1 = arg min β 1 2 ∥ s ( k − 1 ) β − y ( k − 1 ) ∥ 2 ⟹ α k 1 = ( s ( k − 1 ) ) T s ( k − 1 ) ( s ( k − 1 ) ) T y ( k − 1 ) α k = arg min α 1 2 ∥ s ( k − 1 ) − y ( k − 1 ) α ∥ 2 ⟹ α k 2 = ( s ( k − 1 ) ) T y ( k − 1 ) ( y ( k − 1 ) ) T y ( k − 1 ) \alpha_{k}^{-1}=\underset{\beta}{\arg \min } \frac{1}{2}\left\|s^{(k-1)} \beta-\boldsymbol{y}^{(k-1)}\right\|^{2} \Longrightarrow \alpha_{k}^{1}=\frac{\left(s^{(k-1)}\right)^{T} s^{(k-1)}}{\left(s^{(k-1)}\right)^{T} \boldsymbol{y}^{(k-1)}} \\\alpha_{k}=\underset{\alpha}{\arg \min } \frac{1}{2}\left\|s^{(k-1)}-\boldsymbol{y}^{(k-1)} \alpha\right\|^{2} \Longrightarrow \alpha_{k}^{2}=\frac{\left(\boldsymbol{s}^{(k-1)}\right)^{T} \boldsymbol{y}^{(k-1)}}{\left(\boldsymbol{y}^{(k-1)}\right)^{T} \boldsymbol{y}^{(k-1)}} αk−1=βargmin21∥∥∥s(k−1)β−y(k−1)∥∥∥2⟹αk1=(s(k−1))Ty(k−1)(s(k−1))Ts(k−1)αk=αargmin21∥∥∥s(k−1)−y(k−1)α∥∥∥2⟹αk2=(y(k−1))Ty(k−1)(s(k−1))Ty(k−1)
這兩個解有一個微妙的不同點在于 α k 1 \alpha_k^1 αk1 的分母 ( s ( k − 1 ) ) T y ( k − 1 ) \left(s^{(k-1)}\right)^{T} \boldsymbol{y}^{(k-1)} (s(k−1))Ty(k−1) 有可能等于 0，這會給計算帶來麻煩，而 α k 2 \alpha_k^2 αk2 則不會。
