梯度下降法
對于無約束最優化問題：$$\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$線性收斂的