梯度下降法的两个收敛性证明

**梯度下降法:**
对于无约束最优化问题：$$\mathop{min}_{x} f(x)$$其中$f$是可微函数,梯度下降法的更新方式如下:
$$x_{k+1}=x_k-\alpha_k\nabla f(x_k)$$
步长$\alpha_k$有多种选择方式，普通的梯度法就选择固定步长$\alpha$。

下面介绍固定步长的梯度下降法在凸函数以及强凸函数的收敛性证明

**梯度法在凸函数上的收敛性**
假设$f(x)$为凸函数，是梯度L利普西茨连续，最优值$f^*=\mathop{inf}\limits_{x}f(x)$可达，且步长$\alpha\in\left(0,\frac{1}{L} \right) $，则梯度下降法得到的点列$\left\lbrace x^k \right\rbrace$的函数值列$\left\lbrace f_k \right\rbrace $收敛到$f^*$，且收敛速度为$O(\frac{1}{k})$

proof
由于$f$为凸函数且梯度皮利希茨连续，根据二次上界原理得到：
\begin{align*}
f_{k+1}&=f\left(x_k-\alpha \nabla f( x_k) \right)\\
&\leq f(x_k)-\alpha \Vert
\nabla f( x_k) \Vert^2+\frac{L\alpha^2}{2}\Vert
\nabla f( x_k) \Vert^2 \\
&= f(x_k)-\alpha\left( 1-\frac{\alpha L}{2}\right) \Vert
\nabla f( x_k) \Vert^2
\end{align*}
由于$\alpha\in\left(0,\frac{1}{L} \right)$，则
\begin{align*}
f_{k+1}&\leq f(x_k)-\frac{\alpha}{2} \Vert
\nabla f( x_k) \Vert^2\\
&\leq f^*+\nabla f(x_k)^\top \left(x_k-x^* \right)-\frac{\alpha}{2}\Vert
\nabla f( x_k) \Vert^2\\
&=f^*+\frac{1}{2\alpha}\left(\Vert x_k-x^* \Vert^2-\Vert x_k-x^*-\alpha\nabla f(x_k) \Vert^2 \right)\\
&=f^*+\frac{1}{2\alpha}\left(\Vert x_k-x^* \Vert^2-\Vert x_{k+1}-x^*\Vert^2 \right)\\
\end{align*}
其中第二个不等式是根据$f$的凸性得到的。

进一步得到$$f_{k+1}-f^*=\frac{1}{2\alpha}\left(\Vert x_k-x^* \Vert^2-\Vert x_{k+1}-x^*\Vert^2 \right)$$
分别令$k=0,1,\dots,n$然后累加得到:
\begin{align*}
\mathop{\sum}_{k=0}^{n}\left(f_{k+1}-f^* \right) &\leq \frac{1}{2\alpha}\left(\Vert x_0-x^* \Vert^2-\Vert x_{k+1}-x^*\Vert^2 \right)\\
&=\frac{1}{2\alpha}\Vert x_0-x^* \Vert^2
\end{align*}
有因为$\left\lbrace f_k\right\rbrace $是单调下降的，所以
$$f_{n+1}-f^*\leq \frac{1}{n+1}\mathop{\sum}_{k=0}^{n}\left(f_{k+1}-f^* \right) \leq \frac{1}{2(n+1)\alpha}\Vert x_0-x^* \Vert^2$$
得证.

**梯度法在强凸函数上的收敛性**
引理：$f(x)$是在$\mathbb{R}^n$上的可微凸函数，则以下结论等价：
(1)$f$是梯度$L-$利普西茨连续的；
(2)函数$g(x)=\frac{L}{2}x^\top x-f(x)$是凸函数；
(3)$\nabla f(x) $有余强制性，即对$\forall x,y\in \mathbb{R}^n$，有$$\left(\nabla f(x)-\nabla f(y) \right) ^\top \left(x-y \right) \geq \frac{1}{L}\Vert \nabla f(x)-\nabla f(y) \Vert^2$$
证明略.

假设$f(x)$为$m-$强凸函数，且是梯度L利普西茨连续的，最优值$f^*=f(x^*)=\mathop{inf}\limits_{x}f(x)$可达，且步长$\alpha\in\left(0,\frac{2}{m+L} \right) $，则梯度下降法得到的点列$\left\lbrace x^k \right\rbrace$收敛到$x^8$，且为$Q$收敛。

proof:由于$f$强凸且梯度$L$利普西茨连续，则：
$$g(x)=f(x)-\frac{m}{2}x^\top x$$
为凸函数且$\frac{L-m}{2}x^\top x-g(x)$为凸函数，根据引理得到$g$为梯度$L-m$利普西茨连续的，则有余强制性：
$$\left(\nabla g(x)-\nabla g(y) \right) ^\top \left(x-y \right) \geq \frac{1}{L-m}\Vert \nabla g(x)-\nabla g(y) \Vert$$
展开就得到:
$$\left(\nabla f(x)-\nabla f(y) \right) ^\top \left(x-y \right) \geq \frac{mL}{m+L}\vert x-y \Vert^2+\frac{1}{L+m}\Vert \nabla f(x)-\nabla f(y) \Vert^2$$
则在梯度下降法中有：
\begin{align*}
\Vert x_{k+1}-x^* \Vert^2 &=\Vert x_k-x^*-\alpha \nabla f(x_k)\Vert^2\\
&=\Vert x_k-x^* \Vert^2 -2\alpha\nabla f(x_k)^\top\left( x^k-x^* \right) +\alpha^2 \Vert\nabla f(x_k)\Vert^2\\
&=\Vert x_k-x^* \Vert^2 -2\alpha\left( \nabla f(x_k)-\nabla f(x^*)\right)^\top \left( x^k-x^* \right) +\alpha^2 \Vert\nabla f(x_k)-\nabla f(x^*)\Vert^2\\
&\leq \left(1-\alpha \frac{2mL}{m+L} \right) \Vert x_k-x^* \Vert^2 +\alpha\left(\alpha-\frac{2}{m+L}\Vert\nabla f(x_k)\Vert^2 \right)
\end{align*}
此时因为$\alpha\in\left(0,\frac{2}{m+L} \right)$，于是有
$$\Vert x_{k+1}-x^* \Vert^2 \leq \left(1-\alpha \frac{2mL}{m+L} \right) \Vert x_k-x^* \Vert^2 $$
且此时$\left(1-\alpha \frac{2mL}{m+L} \right)\in (0,1) $于是
$$\Vert x_{k+1}-x^* \Vert^2 \leq c^{k+1}\Vert x_0-x^* \Vert^2 $$
其中$0<c<1$，于是这是$Q$线性收敛的