引言

本節(jié)將介紹梯度下降法在凸函數(shù)上的收斂性。

回顧：

收斂速度：次線性收斂

關(guān)于次線性收斂，分為兩種判別類型：$\mathcal{R}$-次線性收斂與$\mathcal{Q}$-次線性收斂。而次線性收斂的特點(diǎn)是：隨著迭代次數(shù)的增加，相鄰迭代步驟產(chǎn)生的目標(biāo)函數(shù)結(jié)果$f(x_k),f(x_{k+1})$，其差異性幾乎完全相同：
$$\underset{k?\infty }{\lim }\frac{||x_{k+1}?x^{?}||}{||x_k?x^{?}||}=1$$
例如：如果數(shù)值解$x_k$的目標(biāo)函數(shù)結(jié)果$f(x_k)$與目標(biāo)函數(shù)最優(yōu)解$f^{?}$之間的差異性$||f(x_k)?f^{?}||$與迭代次數(shù)$k$存在如下函數(shù)關(guān)系$\mathcal{G}(k)$：
$$||f(x_k)?f^{?}||\le \mathcal{G}(k)=\frac{1}{k}$$
當(dāng)$k$充分大時(shí)，$f(x_k),f(x_{k+1})$與$f^{?}$之間差異性的比值表示如下：
$$\underset{k?\infty }{\lim }\frac{||f(x_{k+1})?f^{?}||}{||f(x_k)?f^{?}||}=\underset{k?\infty }{\lim }\frac{k}{k+1}=1$$
也就是說(shuō)：雖然隨著$k$的增加，$f(x_k)$在減小;但相鄰迭代結(jié)果$f(x_k),f(x_{k+1})$之間的差異性幾乎可以忽略不計(jì)。那么稱這種收斂速度為次線性收斂。
準(zhǔn)確的說(shuō)，是$?0$的次線性收斂：
lim ? k ? ∞ { f ( x k ) } ? lim ? k ? ∞ G ( k ) = 0 \mathop{\lim}\limits_{k \Rightarrow \infty} \{f(x_k)\} \Rightarrow \mathop{\lim}\limits_{k \Rightarrow \infty} \mathcal G(k) = 0 k?∞lim?{f(xk?)}?k?∞lim?G(k)=0

二次上界引理

關(guān)于二次上界引理的描述表示如下：如果函數(shù)$f(?)$可微，并對(duì)應(yīng)梯度函數(shù)$?f(?)$滿足利普希茲連續(xù)，則函數(shù)$f(?)$存在二次上界。即：
$$?x,y\in {\mathbb{R}}^n?f(y)\le f(x)+[?f(x){]}^T(y?x)+\frac{\mathcal{L}}{2}||y?x|{|}^2$$
而二次上界引理的作用是：可以通過(guò)該引理，得到最優(yōu)步長(zhǎng)上界的最小值：

• 假設(shè)$x$固定，令$\begin{array}{r}?(y)=f(x)+[?f(x){]}^T(y?x)+\frac{\mathcal{L}}{2}||y?x|{|}^2\end{array}$，通過(guò)選擇合適的$y_{min}$，使$?(y)$達(dá)到最小值：
  $$y_{min}=\underset{y\in {\mathbb{R}}^n}{\mathrm{argmin}}?(y)$$
• 令$??(y)?0$，有：
  $$y_{min}=x+\frac{1}{\mathcal{L}}?[??f(x)]$$
• 其中$??f(x)$即${\mathcal{P}}_k$，也就是最速下降方向；而$\begin{array}{r}\frac{1}{\mathcal{L}}\end{array}$則是最優(yōu)步長(zhǎng)的上確界：
  $$f(y)\le ?(y_{min})=\underset{y\in {\mathbb{R}}^n}{\min }?(y)$$
  也就是說(shuō)：
  • 在沒(méi)有二次上界引理的約束下，步長(zhǎng)${\alpha }_k$的選擇在其定義域內(nèi)沒(méi)有約束：$(0,+\infty )$；
  • 經(jīng)過(guò)二次上界引理的約束后，步長(zhǎng)${\alpha }_k$的選擇從原始的$(0,+\infty )$約束至$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$。

延伸：關(guān)于區(qū)間$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$可以模糊地認(rèn)為滿足$\text{Armijo}$準(zhǔn)則。關(guān)于步長(zhǎng)變量$\alpha$的函數(shù)$?(\alpha )=f(x_{k+1})$中，當(dāng)$\alpha \in \begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$時(shí)，等價(jià)于：存在一條直線$\mathcal{L}(\alpha )$，以該直線作為劃分邊界對(duì)應(yīng)$\alpha$的范圍正好是$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$：
吐槽：實(shí)際上用這張圖是不太合理的，因?yàn)橄旅娴膱D對(duì)應(yīng)的$f(?)$更加復(fù)雜，二次上界約束的范圍僅僅在下面$\alpha$軸的綠色實(shí)線部分，但很明顯，在該函數(shù)中，存在更優(yōu)質(zhì)的$\alpha$結(jié)果。

梯度下降法在凸函數(shù)上的收斂性

收斂性定理介紹

梯度下降法在凸函數(shù)上的收斂性定理表示如下：

• 條件：
  • 函數(shù)$f(?)$向下有界，在定義域內(nèi)可微，并且$f(?)$是凸函數(shù)；
  • 關(guān)于$f(?)$的梯度函數(shù)$?f(?)$滿足利普希茲連續(xù)；
  • 梯度下降法迭代過(guò)程中步長(zhǎng)${\alpha }_k(k=1,2,3,?)$有明確的約束范圍：$\begin{array}{r}{\alpha }_k\in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$；
• 結(jié)論：數(shù)值解序列 { x k } k = 0 ∞ \{x_{k}\}_{k=0}^{\infty} {xk?}k=0∞?對(duì)應(yīng)的目標(biāo)函數(shù)結(jié)果 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk?)}k=0∞?以$\begin{array}{r}\mathcal{O}\left(\frac{1}{k}\right)\end{array}$收斂于目標(biāo)函數(shù)最優(yōu)解$f^{?}$。
  其中$\begin{array}{r}\mathcal{O}\left(\frac{1}{k}\right)\end{array}$表示以$\begin{array}{r}\mathcal{G}(k)=\mathcal{C}?\frac{1}{k}\end{array}$的次線性收斂級(jí)別的收斂速度($\mathcal{C}$為常數(shù))。

證明過(guò)程

根據(jù)二次上界引理，依然將$x$設(shè)為上一次迭代的數(shù)值解$x_{i?1}$，對(duì)應(yīng)的$y$為當(dāng)前迭代步驟的數(shù)值解$x_i$。由于是梯度下降法，因而在線搜索方法的基礎(chǔ)上，將方向${\mathcal{P}}_i$表示為最速下降方向$?f(x_{i?1})$步長(zhǎng)依然使用步長(zhǎng)變量$\alpha$進(jìn)行表示：
$$y?x=x_i?x_{i?1}=??f(x_{i?1})?\alpha$$
將二次上界不等式進(jìn)行相應(yīng)替換：
將上式代入~
$$f(x_i)\le f(x_{i?1})+[?f(x_{i?1}){]}^T[??f(x_{i?1})?\alpha ]+\frac{\mathcal{L}}{2}||??f(x_{i?1})?\alpha |{|}^2$$
觀察不等式右側(cè)，可以繼續(xù)化簡(jiǎn)：

• 將內(nèi)積寫(xiě)作$||?|{|}^2$的形式。
• $||??f(x_{i?1})?\alpha |{|}^2=||?f(x_{i?1})?\alpha |{|}^2$,這里消掉一個(gè)負(fù)號(hào);
• 由于$\begin{array}{r}\alpha \in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$,是一個(gè)標(biāo)量，直接將其提到范數(shù)外側(cè)。
  $${\mathcal{I}}_{right}=f(x_{i?1})?\alpha ?||?f(x_{i?1})|{|}^2+\frac{\mathcal{L}}{2}?{\alpha }^2?||?f(x_{i?1})|{|}^2$$

由$\begin{array}{r}\alpha \le \frac{1}{\mathcal{L}}\end{array}$可知：$\begin{array}{r}\mathcal{L}\le \frac{1}{\alpha }\end{array}$。將該式代入到上式中：
消掉分母中的$\alpha$，并于前面的項(xiàng)結(jié)合。
$$\begin{array}{rl}{\mathcal{I}}_{right}& \le f(x_{i?1})?\alpha ?||?f(x_{i?1})|{|}^2+\frac{1}{2\alpha }?{\alpha }^2?||?f(x_{i?1})|{|}^2\\ & =f(x_{i?1})?\frac{\alpha }{2}?||?f(x_{i?1})|{|}^2\end{array}$$
基于梯度下降法，使用二次上界引理，可以得到$f(x_{i?1})$與$f(x_i)$之間存在如下關(guān)聯(lián)關(guān)系：
$$f(x_i)\le f(x_{i?1})?\frac{\alpha }{2}?||?f(x_{i?1})|{|}^{2}i=1,2,3,?$$
根據(jù)凸函數(shù)的性質(zhì)，必然有：函數(shù)$f(?)$任一位置的切線，$f(?)$均在該切線上方。見(jiàn)下圖：
由于條件:$f(?)$向下有界,因此，該函數(shù)必然’開(kāi)口向上‘。

其中紅色點(diǎn)$(x^{?},f^{?})$表示最優(yōu)點(diǎn)，以上一次迭代產(chǎn)生的$x_{i?1}$為切點(diǎn)做一條切線，必然有$x^{?}$在該切線函數(shù)上的函數(shù)值$f^{\prime }\le f^{?}$。$f^{\prime }$表示如下：
$$f^{\prime }=f(x_{i?1})?[?f(x_{i?1}){]}^T(x_{i?1}?x^{?})\le f^{?}$$
移項(xiàng)，從而有：
$$f(x_{i?1})\le f^{?}+[?f(x_{i?1}){]}^T(x_{i?1}?x^{?})$$
將上式代入，有：
$${\mathcal{I}}_{right}\le \underset{替換f(x_{i?1})}{\underbrace{f^{?}+[?f(x_{i?1}){]}^T(x_{i?1}?x^{?})}}?\frac{\alpha }{2}?||?f(x_{i?1})|{|}^2$$
為了湊平方項(xiàng)，將上式調(diào)整至如下形式：
將$\begin{array}{r}?\frac{\alpha }{2}\end{array}$湊出${\alpha }^2$,其他項(xiàng)跟隨變化。
$${\mathcal{I}}_{right}\le ?\frac{1}{2\alpha }\left\{{\alpha }^2||?f(x_{i?1})|{|}^2?2\alpha ?[?f(x_{i?1}){]}^T(x_{i?1}?x^{?})\right\}$$
對(duì)大括號(hào)內(nèi)的項(xiàng)進(jìn)行配方：
$$\begin{array}{rl}{\mathcal{I}}_{right}& \le f^{?}?\frac{1}{2\alpha }?\underset{平方項(xiàng)}{\underbrace{{\alpha }^2||?f(x_{i?1})|{|}^2?2\alpha ?[?f(x_{i?1}){]}^T(x_{i?1}?x^{?})+||x_{i?1}?x^{?}|{|}^2}}?||x_{i?1}?x^{?}|{|}^2?\\ & =f^{?}?\frac{1}{2\alpha }\left[||\alpha ??f(x_{i?1})?(x_{i?1}?x^{?})|{|}^2?||x_{i?1}?x^{?}|{|}^2\right]\end{array}$$
觀察中括號(hào)內(nèi)第一項(xiàng)：$||\alpha ??f(x_{i?1})?(x_{i?1}?x^{?})|{|}^2$，由于是范數(shù)的平方項(xiàng)，因而在范數(shù)內(nèi)部添加一個(gè)負(fù)號(hào)不會(huì)影響其值的變化：
$$||\alpha ??f(x_{i?1})?(x_{i?1}?x^{?})|{|}^2=||x_{i?1}?\alpha ??f(x_{i?1})?x^{?}|{|}^2$$
從迭代角度觀察：$x_{i?1}?\alpha ??f(x_{i?1})=x_i$，從而上式可繼續(xù)化簡(jiǎn)為：
提一個(gè)負(fù)號(hào)，調(diào)換一下位置。
$$?\begin{array}{l}||\alpha ??f(x_{i?1})?(x_{i?1}?x^{?})|{|}^2=||x_i?x^{?}|{|}^2\\ \\ \begin{array}{rl}{\mathcal{I}}_{right}& \le f^{?}?\frac{1}{2\alpha }\left[||x_i?x^{?}|{|}^2?||x_{i?1}?x^{?}|{|}^2\right]\\ & =f^{?}+\frac{1}{2\alpha }\left[||x_{i?1}?x^{?}|{|}^2?||x_i?x^{?}|{|}^2\right]\end{array}\end{array}$$

至此，可以得到如下不等式結(jié)果：
$$f(x_i)?f^{?}\le \frac{1}{2\alpha }(||x_{i?1}?x^{?}|{|}^2?||x_i?x^{?}|{|}^2)$$
觀察：不等式左側(cè)描述的意義是：當(dāng)前迭代步驟的目標(biāo)函數(shù)結(jié)果$f(x_i)$與最優(yōu)解$f^{?}$之間的偏差。從初始化數(shù)值解$x_0$開(kāi)始，我們會(huì)得到一系列的不等式結(jié)果：
$$?\begin{array}{l}\begin{array}{rl}f(x_1)?f^{?}& \le \frac{1}{2\alpha }(||x_0?x^{?}|{|}^2?||x_1?x^{?}|{|}^2)\\ f(x_2)?f^{?}& \le \frac{1}{2\alpha }(||x_1?x^{?}|{|}^2?||x_2?x^{?}|{|}^2)\\ & ?\\ f(x_k)?f^{?}& \le \frac{1}{2\alpha }(||x_{k?1}?x^{?}|{|}^2?||x_k?x^{?}|{|}^2)\end{array}\end{array}$$
將這些不等式對(duì)應(yīng)位置相加，有：

• 等式右側(cè)的中間項(xiàng)都被消掉了~
• 因?yàn)?/code>$||x_k?x^{?}|{|}^2\ge 0$恒成立，從而消掉含變量的項(xiàng)。
$$\sum _{i=1}^k[f(x_i)?f^{?}]\le \frac{1}{2\alpha }(|||x_0?x^{?}|{|}^2?||x_k?x^{?}|{|}^2)\le \frac{1}{2\alpha }||x_0?x^{?}|{|}^2$$

關(guān)于我們要證的$||f(x_k)?f^{?}||$，可以表示為如下形式：

• 由于優(yōu)化問(wèn)題的收斂性，必然有：$f(x_k)\le f(x_{k?1})\le ?\le f(x_1)$,從而每一項(xiàng):$||f(x_k)?f^{?}||\le ||f(x_{k?1})?f^{?}||\le ?\le ||f(x_1)?f^{?}||$,從而有:$\begin{array}{r}\sum _{i=1}^k[f(x_k)?f^{?}]\le \sum _{i=1}^k[f(x_i)?f^{?}]\end{array}$。
• 將上式結(jié)果帶入~

$$f(x_k)?f^{?}=\frac{1}{k}\sum _{i=1}^k[f(x_k)?f^{?}]\le \frac{1}{k}\sum _{i=1}^k[f(x_i)?f^{?}]\le \frac{1}{k}\left[\frac{1}{2\alpha }||x_0?x^{?}|{|}^2\right]$$

觀察：$\begin{array}{r}\left[\frac{1}{2\alpha }||x_0?x^{?}|{|}^2\right]\end{array}$中$\begin{array}{r}\alpha \in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$，$x_0,x^{?}$都是確定的常數(shù)，因而該項(xiàng)可視作常數(shù)$\mathcal{C}$。最終有：
$$f(x_k)?f^{?}\le \frac{1}{k}?\mathcal{C}$$
我們可以令$\begin{array}{r}\mathcal{G}(k)=\frac{1}{k}?\mathcal{C}\end{array}$，可以看出：它就是一個(gè)級(jí)別為$\begin{array}{r}\frac{1}{k}\end{array}$的次線性收斂。

相關(guān)參考：
【優(yōu)化算法】梯度下降法-凸函數(shù)的收斂性