最速下降法（欧式空间）.md

最速下降法（欧式空间）

一.欧式空间的最速下降法

给定一个函数$f(\mathbf x)$,我们的目标是找到一个方向使得$f(\mathbf{x}+\Delta \mathbf x)$最小，因我们关心的只是$\Delta \mathbf x$的方向，对于它的模（只要足够小）我们并不关心，可得以下最优化问题。 $$ \begin{aligned} \mathrm{minmize} \ \ \ &f(\mathbf x+\Delta \mathbf x)\ s.t\ \ \ \ \ \ \ \ \ &||\Delta \mathbf x||_p \leq c\ &\lim c \rightarrow 0 \end{aligned} \tag{1-1} $$ 由于约束是在欧式空间中进行的，所以又称欧式空间中的最速下降法。

二.梯度下降法(一阶优化算法)

如果我们将p取为二范数，约束条件可以写为 $$ \Delta \mathbf x^T\Delta \mathbf x\leq c\ \lim c \rightarrow 0 \tag{1-2} $$ 于是1-1的约束问题可以重写为 $$ \begin{aligned} \mathrm{minmize} \ \ \ &f(\mathbf x+\Delta \mathbf x)\
s.t\ \ \ \ \ \ \ \ \ &||\Delta \mathbf x||^2 \leq c\ &\lim c \rightarrow 0 \end{aligned} \tag{1-3} $$ 引入拉格朗日乘子$\lambda \geq$0，拉格朗日函数为 $$ L=f(\mathbf x+\Delta \mathbf x)+\lambda(\Delta \mathbf x^T\Delta \mathbf x-c) $$ 在极值处，应有$\nabla _{\Delta\mathbf x}L=0$,即可推出 $$ \nabla f(\mathbf x)+2\lambda \Delta \mathbf x=0\ \ \ \ (\lim \Delta x\rightarrow 0)
\tag{1-4} $$ 由此得出$\Delta \mathbf x$的方向应该沿$f(\mathbf x)$梯度的负方向。（由此我们可以说梯度下降是在二范数下的最优算法）

迭代公式 $$ \mathbf x_{k+1}=\mathbf x_{k}-\eta\nabla f(\mathbf x_{k}) $$

三.梯度下降收敛速度分析.

在分析收敛性之前先引入几个数学概念。

$Lipschitz$连续函数：$\forall \mathbf x,\mathbf y \in \Bbb R^n,\exist \mathit L\in \Bbb R^+,$使得 $$ ||\nabla (\mathbf x)-\nabla f(\mathbf y)||\leq L||\mathbf x-\mathbf y||\ \Updownarrow\ f(\mathbf y)\leq f(\mathbf x)+\nabla f(\mathbf x)^T(\mathbf y-\mathbf x)+\frac{L}2 ||\mathbf y-\mathbf x||^2
\tag{1-5} $$ $Lipschitz$连续条件保证了函数不会剧烈变化，它使得函数足够光滑,我们把$L$称为光滑系数。

强凸函数：$\forall \mathbf x,\mathbf y \in \Bbb R^n,\exist \mu \in \Bbb R^+$使得 $$ \nabla ^2f(\mathbf x) \succ 0\ \Updownarrow\ \nabla ^2f(\mathbf x) \succeq \mu I\ \Updownarrow\ f(\mathbf y)\geq f(\mathbf x)+\nabla f(\mathbf x)^T(\mathbf y-\mathbf x)+\frac{\mu}2 ||\mathbf y-\mathbf x||^2
\tag{1-6} $$ 也就是说，目标函数需要比某个二次函数更凸，强凸函数保证目标函数一定存在一个全局极小值,我们称$\mu$为强凸系数。

假设函数是$Lipschitz$连续，设光滑系数为$L$,学习率$\eta \leq\frac{1}{L}$。令$\mathbf y = \mathbf x_{k+1},\mathbf x=\mathbf x_k,\mathbf x_{k+1}=\mathbf x_{k}-\eta\nabla f(\mathbf x_{k})$,带入式（1-5）中得 $$ f(\mathbf x_{k+1})\leq f(\mathbf x_k)-\frac{1}{2L}||\nabla f(\mathbf x_k)||^2
\tag{1-7} $$ 定义$\mathbf x^$为全局最优点。我们想知道$f(\mathbf x_k)$以什么样的速度接近$f(\mathbf x^)$。

对式（1-7）两边同时减去 $f(\mathbf x^)$ 得 $$ f(\mathbf x_{k+1})-f(\mathbf x^)\leq f(\mathbf x_k)-f(\mathbf x^)-\frac{1}{2L}||\nabla f(\mathbf x_k)||^2\tag{1-8} $$ 令$\mathbf y = \mathbf x^,\mathbf x =\mathbf x_k$,代入（1-6）中可得 $$ \begin{aligned} f(\mathbf x^)&\geq \underbrace{f(\mathbf x_k)+\nabla f(\mathbf x_k)^T(\mathbf x^-\mathbf x_k)+\frac{\mu}2 ||\mathbf x^-\mathbf x_k||^2}_{记为新的函数G(\mathbf x^)}\ & \end{aligned} $$ 其中，$G(\mathbf x^)$是一个关于$\mathbf x^$的凸函数，对其求导$\nabla {\mathbf x^}G(\mathbf x^)=0$可计算出$G(\mathbf x^)$的最小值。 $$ \mathbf x^=\mathbf x_k-\frac{1}{\mu}\nabla f(\mathbf x_k)\ \Downarrow\ G(\mathbf x^) \geq f(\mathbf x_k)-\frac{1}{2\mu}||\nabla f(\mathbf x_k)||^2\ \Downarrow\ f(\mathbf x^)\geq f(\mathbf x_k)-\frac{1}{2\mu}||\nabla f(\mathbf x_k)||^2\ \Downarrow\ -||\nabla f(\mathbf x)||^2\leq -2\mu(f(\mathbf x_k)-f(\mathbf x^*)) \tag{1-9} $$ 带入（1-8）中可得 $$ \begin{aligned} f(\mathbf x{k+1})-f(\mathbf x^)&\leq f(\mathbf x_k)-f(\mathbf x^)-\frac{1}{2L}||\nabla f(\mathbf x_k)||^2\ &\leq f(\mathbf x_k)-f(\mathbf x^)-\frac{\mu}{L}( f(\mathbf x_k)-f(\mathbf x^)) \ &=(1-\frac{\mu}{L})( f(\mathbf x_k)-f(\mathbf x^)) \end{aligned} $$ 因此在限制步长$\eta\leq\frac{1}{L}$ ,函数满足强凸以及$Lipschitz$连续，收敛速率为 $$ \frac{f(\mathbf x_{k+1})-f(\mathbf x^)}{ f(\mathbf x_k)-f(\mathbf x^*)}\leq 1-\frac{\mu}{L}\tag{1-10} $$ 梯度下降法作用在强凸和光滑函数上的收敛速率是线性的。

（在此之后的$BGD,SGD,AdaGrad,RMSProp,Adam$都是梯度下降法的衍生版本，虽然他们都对梯度下降进行了优化，但他们都只利用了函数的一阶信息，并未直接利用函数的二阶信息——$Hessian$矩阵）

三.牛顿法（二阶优化算法）

将目标函数利用到二阶可以获得关于函数的曲率信息，获得更精准的下降方向。记$H(\mathbf x)=\nabla^2 f(\mathbf x)$， 定义 $|\cdot|{H(\mathbf x)}$范数 $$ |\mathbf x|{H(\mathbf x)}=\mathbf x^TH(\mathbf x)\mathbf x
$$ 约束问题重写为 $$ \begin{aligned} \mathrm{minmize} \ \ \ &f(\mathbf x+\Delta \mathbf x) \
s.t\ \ \ \ \ \ \ \ \ &\mathbf \Delta x^TH(\mathbf x)\mathbf \Delta x \leq c\ &\lim c \rightarrow 0 \end{aligned} \tag{1-11} $$ 需要注意的是，如果$Hessian$矩阵负定，则以上约束问题无解（不存在极小值只有极大值）

构建拉格朗日函数为 $$ L=f(\mathbf x+\Delta \mathbf x)+\lambda (\mathbf \Delta x^TH(\mathbf x)\mathbf \Delta x -c) $$ 由$\nabla _{\Delta\mathbf x}L=0$得出 $$ \Delta \mathbf x =\frac{-H(\mathbf x)^{-1}}{\lambda}\nabla f(\mathbf x) $$

所以最优下降方向可定义为

$$ -(H(\mathbf x))^{-1}\nabla f(\mathbf x) \tag{1-12} $$

迭代公式

$$ \mathbf x_{k+1}=\mathbf x_{k}-\eta H(\mathbf x)^{-1}\nabla f(\mathbf x_{k})\tag{1-13} $$ 因此牛顿法可以认为是$|\cdot|_{H(\mathbf x)}$范数下的最优化算法

牛顿法在凸函数上有着更快的收敛速度，但是计算存储以及求$Heaaian$矩阵的逆有着高昂的计算复杂度，并且要求$Hessian$矩阵正定，更严重的是在非二次误差曲面上该算法可能不收敛

四.牛顿法收敛速度分析

可以证明牛顿法在条件足够好的情况下，能够以极快的速度收敛到最优点（二次收敛）。

我们假设目标函数的二阶导满足$Lipschitz$ 连续,即$\exist L\geq 0$使得 $$ ||\nabla ^2f(\mathbf x)-\nabla ^2f(\mathbf y)||\leq L||\mathbf x-\mathbf y||\tag{1-14} $$ 并且目标函数是强凸的 $$ ||\nabla^2 f(\mathbf x)||\geq \mu\tag{1-15}\ \Updownarrow\ ||\nabla^2 f(\mathbf x)^{-1}||\leq \frac{1}{\mu} $$ 给定步长为1，在（1-13）左右同时减去$\mathbf x^$,可得 $$ \begin{aligned} ||\mathbf x_{k+1}-\mathbf x^||&=||\mathbf x_{k}-\mathbf x^-H(\mathbf x)^{-1}\nabla f(\mathbf x_{k})||\ &=||H(\mathbf x)^{-1}(H(\mathbf x)(\mathbf x_k-\mathbf x^)-(\nabla f(\mathbf x_k)-\nabla f(x^)))||\ \ \ \ \ \ \ \ (因为\nabla f(\mathbf x^=0))\ &\leq ||H(\mathbf x)^{-1}||||H(\mathbf x)(\mathbf x_k-\mathbf x^)-(\nabla f(\mathbf x_k)-\nabla f(x^))|| \ &=||H(\mathbf x)^{-1}||||\int^1_0(H(\mathbf x_k)-H(\mathbf x_k+t(\mathbf x^-\mathbf x_k)))(\mathbf x^-\mathbf x_k)\mathrm dt||\ &\leq||H(\mathbf x)^{-1}||\int^1_0||H(\mathbf x_k)-H(\mathbf x_k+t(\mathbf x^-\mathbf x_k))||||\mathbf x^-\mathbf x_k||\mathrm dt\ &\leq ||H(\mathbf x)^{-1}||||\mathbf x^-\mathbf x_k||^2\int^1_0Lt\mathrm dt\ \ \ \ \ \ (Lipschitz连续)\ &=\frac{1}{2}L||H(\mathbf x)^{-1}||||\mathbf x^-\mathbf x_k||^2\ &\leq \frac{L}{2\mu}||\mathbf x^*-\mathbf x_k||^2\ \ \ \ \ \ \ (强凸性) \end{aligned} $$ 由此我们证明了牛顿法的收敛速度是超线性的二次收敛。