本文 是对 Boyd凸优化书第9章内容的摘记。
梯度方法我们都知道可以确保目标函数的单调下降， 然而如果要分析收敛性的话，除了单调性外， 我们更需要知道的是收敛速度。 否则，我们并无法分析算法能否收敛到最优解或是局部最优解。
收敛速度的证明依赖于所谓强凸性的假设： ∇ 2 f ( x ) ⪰ m I , ∀ x ∈ S \nabla^{2} f(x) \succeq m I, \forall x\in S ∇2f(x)⪰mI,∀x∈S S S S 为 x x x的可行域。
这个假设也可以等价为： Hessian矩阵 ∇ 2 f ( x ) \nabla^2 f(x) ∇2f(x)的最小特征值为m。
根据泰勒展开或柯西中值定理 https://zhuanlan.zhihu.com/p/25413823， 我们有: f ( y ) = f ( x ) + ∇ f ( x ) T ( y − x ) + 1 2 ( y − x ) T ∇ 2 f ( z ) ( y − x ) (1) f(y)=f(x)+\nabla f(x)^{T}(y-x)+\frac{1}{2}(y-x)^{T} \nabla^{2} f(z)(y-x)\tag{1} f(y)=f(x)+∇f(x)T(y−x)+21(y−x)T∇2f(z)(y−x)(1) 其中 z z z在线 [ x , y ] [x,y] [x,y]上。 那么基于强凸性假设， 即： f ( y ) ⩾ f ( x ) + ∇ f ( x ) T ( y − x ) + m 2 ∥ y − x ∥ 2 2 (2) f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|_{2}^{2}\tag{2} f(y)⩾f(x)+∇f(x)T(y−x)+2m∥y−x∥22(2) 对(2)式求最值，有： f ( y ) ⩾ f ( x ) + ∇ f ( x ) T ( y − x ) + m 2 ∥ y − x ∥ 2 2 ⩾ f ( x ) + ∇ f ( x ) T ( y ~ − x ) + m 2 ∥ y ~ − x ∥ 2 2 = f ( x ) − 1 2 m ∥ ∇ f ( x ) ∥ 2 2 (3) \begin{aligned} f(y) & \geqslant f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|_{2}^{2} \\ & \geqslant f(x)+\nabla f(x)^{T}(\tilde{y}-x)+\frac{m}{2}\|\tilde{y}-x\|_{2}^{2} \\ &=f(x)-\frac{1}{2 m}\|\nabla f(x)\|_{2}^{2} \end{aligned}\tag{3} f(y)⩾f(x)+∇f(x)T(y−x)+2m∥y−x∥22⩾f(x)+∇f(x)T(y~−x)+2m∥y~−x∥22=f(x)−2m1∥∇f(x)∥22(3) 其中 y ˉ = x − ( 1 / m ) ∇ f ( x ) \bar{y}=x-(1 / m) \nabla f(x) yˉ=x−(1/m)∇f(x), 也即(2)右边对 y y y求导为0的结果。 后续就是基于(3)这个式子进行收敛性的分析。 由于对于任何 y y y， （3）都成立， 因此假设最优解位 f ( y ∗ ) = p ∗ f(y^*)=p^* f(y∗)=p∗， 由(1)和(2)我们有： p ⋆ ⩾ f ( x ) − 1 2 m ∥ ∇ f ( x ) ∥ 2 2 (4) p^{\star} \geqslant f(x)-\frac{1}{2 m}\|\nabla f(x)\|_{2}^{2}\tag{4} p⋆⩾f(x)−2m1∥∇f(x)∥22(4) 由 (4) 可以看出，当梯度足够小时， 点 x x x无限接近于最优点。 有： ∥ ∇ f ( x ) ∥ 2 ⩽ ( 2 m ε ) 1 / 2 ⟹ f ( x ) − p ⋆ ⩽ ϵ \|\nabla f(x)\|_{2} \leqslant(2 m \varepsilon)^{1 / 2} \Longrightarrow f(x)-p^{\star} \leqslant \epsilon ∥∇f(x)∥2⩽(2mε)1/2⟹f(x)−p⋆⩽ϵ
然而这个结论只是证明了梯度为0时的结论， 却没有说明，梯度下降法能否在有限次数内达到梯度为0点。因此，继续分析： 这时候需要用到另一个假设： ∇ 2 f ( x ) ⪯ M I \nabla^{2} f(x) \preceq M I ∇2f(x)⪯MI 即 ∇ 2 f ( x ) \nabla^{2} f(x) ∇2f(x) 最大特征值为 M M M。类似的，我们有： f ( y ) ⩽ f ( x ) + ∇ f ( x ) T ( y − x ) + M 2 ∥ y − x ∥ 2 2 (5) f(y) \leqslant f(x)+\nabla f(x)^{T}(y-x)+\frac{M}{2}\|y-x\|_{2}^{2}\tag{5} f(y)⩽f(x)+∇f(x)T(y−x)+2M∥y−x∥22(5) 对 y y y求最值，有: p ⋆ ⩽ f ( x ) − 1 2 M ∥ ∇ f ( x ) ∥ 2 2 (6) p^{\star} \leqslant f(x)-\frac{1}{2 M}\|\nabla f(x)\|_{2}^{2}\tag{6} p⋆⩽f(x)−2M1∥∇f(x)∥22(6) 相比于(4)就是不等式方向变了，因此(4)和(6)分别给出了上下界。
以最速下降法为例， 令 x + = x + t Δ x x^{+}=x+t \Delta x x+=x+tΔx， 其中 t t t为步长， Δ x = − ∇ f ( x ) \Delta x=-\nabla f(x) Δx=−∇f(x)为负梯度方向。 将 y = x + y=x^+ y=x+代入 (6) 得到： f ( x + ) ⩽ f ( x ) − t ∥ ∇ f ( x ) ∥ 2 2 + M t 2 2 ∥ ∇ f ( x ) ∥ 2 2 {f}(x^+) \leqslant f(x)-t\|\nabla f(x)\|_{2}^{2}+\frac{M t^{2}}{2}\|\nabla f(x)\|_{2}^{2} f(x+)⩽f(x)−t∥∇f(x)∥22+2Mt2∥∇f(x)∥22 上式对 t t t求最小值， 可得，最优步长为 t = 1 M t=\frac{1}{M} t=M1，代入得： f ( x + ) ⩽ f ( x ) − 1 2 M ∥ ∇ ( f ( x ) ) ∥ 2 2 f\left(x^{+}\right)\leqslant f(x)-\frac{1}{2 M}\|\nabla(f(x))\|_{2}^{2} f(x+)⩽f(x)−2M1∥∇(f(x))∥22 为了衡量收敛速度， 因此，两边均减去最优值 p ∗ p^* p∗，有: f ( x + ) − p ⋆ ⩽ f ( x ) − p ⋆ − 1 2 M ∥ ∇ f ( x ) ∥ 2 2 f\left(x^{+}\right)-p^{\star} \leqslant f(x)-p^{\star}-\frac{1}{2 M}\|\nabla f(x)\|_{2}^{2} f(x+)−p⋆⩽f(x)−p⋆−2M1∥∇f(x)∥22 而基于(4)， 我们可以得到： ∥ ∇ f ( x ) ∥ 2 2 ⩾ 2 m ( f ( x ) − p ⋆ ) \|\nabla f(x)\|_{2}^{2} \geqslant 2 m\left(f(x)-p^{\star}\right) ∥∇f(x)∥22⩾2m(f(x)−p⋆) 代入可有： f ( x + ) − p ⋆ ⩽ ( 1 − m / M ) ( f ( x ) − p ⋆ ) f\left(x^{+}\right)-p^{\star} \leqslant(1-m / M)\left(f(x)-p^{\star}\right) f(x+)−p⋆⩽(1−m/M)(f(x)−p⋆) 也就是说，相比于初始点 f ( x ) f(x) f(x)与最优点的差距， 经过一次梯度下降后的点 f ( x + ) f(x^+) f(x+)与最优点的距离缩短了 ( 1 − m / M ) (1-m/M) (1−m/M)。
由这个结论我们可知：
- 条件数 m / M m/M m/M越大， 收敛速度越快。 即一个矩阵最大特征值和最小特征值越接近。
- 经过 log ( ( f ( x ( 0 ) ) − p ⋆ ) / ϵ ) log ( 1 / c ) \frac{\log \left(\left(f\left(x^{(0)}\right)-p^{\star}\right) / \epsilon\right)}{\log (1 / c)} log(1/c)log((f(x(0))−p⋆)/ϵ)次迭代，一定能得到 f ( x ( k ) ) − p k ⩽ ϵ 0 f\left(x^{(k)}\right)-p^{k} \leqslant \epsilon_{0} f(x(k))−pk⩽ϵ0。
