前言
无论是机器学习还是深度学习都需要对目标函数进行优化求解，那么这里我先抛开最底层的数学证明，重点介绍几类算法的收敛条件问题，以及梯度相关算法的原理。毕竟不是教学性质，所以我只讲要点。
1.优化理论
1.1凸优化
设集合$S \subset {R^n}$，若S中的任意两点连线仍属于S，则称S为凸集，即
$$ {x_1} + \lambda \left( {{x_2} - {x_1}} \right) \in S $$
在此基础上，凸函数的定义就是,设集合$S \subset {R^n}$,f是定义在S上的实函数，若对任意x1,x2属于S，$\lambda \in \left( {0,1} \right)$，都有
$$ f\left( {{x_1} + \lambda \left( {{x_2} - {x_1}} \right)} \right) \le f\left( {{x_1} + \lambda \left[ {f\left( {{x_2}} \right) - f\left( {{x_1}} \right)} \right]} \right) $$
可以理解为，函数上任意两点的连线一定在两点之间弧的上方。基于这个定义实际上就可以推理出，凸函数的局部极小值点就是全局极小点。
那么对于凸规划，实质就是求凸函数在凸集上的极小点，这里就不给出正式的形式说明了。
顺便提一下算法难度评级：
NP问题：可以在多项式时间内被验证的问题。或者说，可以在非确定性多项式时间内被解决的问题。
P问题：可以在多项式时间内被解决的问题。
NP-Hard问题：不确定是否可以在多项式时间内被验证。
NP-Complete问题：如果一个问题已经被证明是一个NP-Hard问题，并且可以证明该问题是一个NP问题，那么该问题是NPC问题。
1.2最优性条件
对于凸优化来说，最优性条件一般有KT、KKT、F-J等。首先我们介绍下泰勒展开，由此推导出函数的极值条件以及函数在某点出的下降方向：
$$ \begin{array}{l} \because f\left( {\bar x + \lambda \vec d} \right) = f\left( {\bar x} \right) + \lambda \nabla f{\left( {\bar x} \right)^T}\vec d + o\left( {\left\| {\lambda \vec d} \right\|} \right),\lambda \in \left( {0,\delta } \right)\\ \therefore \lambda \to 0,\nabla f{\left( {\bar x} \right)^T}\vec d \le 0 \Rightarrow f\left( {\bar x + \lambda \vec d} \right) \le f\left( {\bar x} \right) \end{array} $$
上面给出的正是极值条件的必要条件，从中可以看出，如果x0是极小点，那么一定不存在满足上述条件的$\lambda$，进而可以推出对于无约束极值问题来说负梯度方向是下降方向。
对于有约束极值问题，有下面的一般问题形式：
$$ \begin{array}{l} \min \;\;\;f(x)\\ s.t.\;\;{g_i}\left( x \right) = 0\\ \;\;\;\;\;\;{h_j}\left( x \right) \le 0 \end{array} $$
那么有存在有Fritz John条件，还有KKT条件来作为极值点的必要条件，下面只给出KKT条件形式：
$$ \left\{ \begin{array}{l} \nabla f + \sum\limits_i^n {{\lambda _i}\nabla {g_i}} + \sum\limits_j^m {{\mu _j}\nabla {h_j}} = 0\\ {g_i} = 0\\ {h_j} \le 0\\ {\mu _j} \ge 0\\ {\mu _j}{h_j} = 0\; \end{array} \right. $$
最后一个条件一般被称作互补松弛条件，关于这个理论，利用对偶问题会比较好解释，这里参照知乎网友的评论如下图：
最后要记住，当f,h都是凸函数，且可行解满足KKT条件，则其一定为最优解。
2.拉格朗日乘子法
基于KKT条件，可以引出广义的Lagrange函数：
$$ L\left( {x,w,v} \right) = f\left( x \right) + \sum\limits_{i = 1}^m {{w_i}{g_i}\left( x \right)} + \sum\limits_{j = 1}^n {{v_j}{h_j}\left( x \right)} $$
其中w,v就是拉格朗日乘子，可以理解为将KKT条件中的微分算子移到一侧，即：
$$ \frac{{\partial L}}{{\partial f}},\frac{{\partial L}}{{\partial {g_i}}},\frac{{\partial L}}{{\partial {h_i}}} = 0 $$
3.梯度下降法
第一章中介绍了，最速下降方向是凸函数f(x)在x0处的负梯度方向，也就是说，最优解的位置一定在x0的负梯度方向，这时候我们只需要利用更新公式即可迭代求解逼近最优解：
$$ \begin{array}{l} {x^{k + 1}} = {x^k} + {\lambda _k}{d^k}\\ {d^k} = - \nabla f\left( {{x^k}} \right) \end{array} $$
其中d平行于负梯度方向，影响归一化项可以用学习率$\lambda$来代替，这类迭代算法的特性就是要注意两个点：
- 学习率：当学习率过大时，更新震荡会变大，可能不容易接近最优解；当学习率过小时，更新太慢；
- 终止条件：一般终止条件有两种，一种是当x或者f(x)的值变化幅度很小的时候停止，另一种是设定迭代次数。
而实际上在问题规模较小时，学习率可以利用简单的搜索算法进行求解，将子问题转化为关于学习率的搜索问题，如：
$$ \min \;f\left( {{x^k} + \lambda {d^k}} \right) $$
但是面对深度学习这种参数量大，样本多的问题，这种搜索会极大降低算法效率。另外由于一维搜索的存在：
$$ \begin{array}{l} \varphi \left( x \right) = f\left( {{x^k} + \lambda {d^k}} \right),{d^k} = - \nabla f\left( {{x^k}} \right)\\ \Rightarrow \varphi '\left( \lambda \right) = \nabla f{\left( {{x^k} + \lambda {d^k}} \right)^T}{d^k} = 0\\ \Rightarrow - \nabla f\left( {{x^{k + 1}}} \right)\nabla f\left( {{x^k}} \right) = 0 \end{array} $$
所以相邻两次的迭代方向是垂直的，从而也就导致收敛过程存在锯齿现象。
4.牛顿法
4.1牛顿法
如果说梯度下降法是根据一阶泰勒展开得到的，那么我们不妨看看二阶泰勒展开的形式：
$$ \begin{array}{l} f\left( x \right) \approx \varphi \left( x \right) = f\left( {{x^k}} \right) + \nabla f{\left( {{x^k}} \right)^T}\left( {x - {x^k}} \right) + {\left( {x - {x^k}} \right)^T}\frac{{{\nabla ^2}f\left( {{x^k}} \right)}}{2}\left( {x - {x^k}} \right)\\ \Rightarrow \varphi '\left( x \right) = \nabla f\left( {{x^k}} \right) + {\nabla ^2}f\left( {{x^k}} \right)\left( {x - {x^k}} \right) = 0\\ \Rightarrow x = {x^k} - {\nabla ^2}f{\left( {{x^k}} \right)^{ - 1}}\nabla f\left( {{x^k}} \right) \end{array} $$
可以看到，牛顿法的迭代更像是曲面的拟合，其对于二次凸函数，可以在有限迭代次数收敛，其中步长中的二阶导数指的是Hessian矩阵：
为了保证最速下降方向，所以Hessian矩阵必须正定，但是当函数不是二次型凸函数时，如果当前点距离极值点很远，则有可能导致Hessian矩阵不正定，那么可能迭代过程目标值会增大。
另外，当变量非常多的时候，求解Hessian矩阵的复杂度也很高。
4.2阻尼牛顿法
对于牛顿法的缺点，阻尼牛顿法做了两点改进，一个是一维搜索，这个就不再赘述，主要用来保证目标值在迭代过程中有所下降，另一个就是构造矩阵解决Hessian矩阵不正定的问题：
$$ {G_k} = {\nabla ^2}f\left( {{x^k}} \right) + {\varepsilon _k}IQ $$
由此解决了牛顿法收敛方向的问题，但是求解速度依然没有解决。
4.3拟牛顿法
常见的拟牛顿法包括拟牛顿法、BFGS、L-BFGS法等。
$$ \begin{array}{l} f\left( x \right) = f\left( {{x^k}} \right) + \nabla f{\left( {{x^k}} \right)^T}\left( {x - {x^k}} \right) + {\left( {x - {x^k}} \right)^T}\frac{{{\nabla ^2}f\left( {{x^k}} \right)}}{2}\left( {x - {x^k}} \right)\\ \Rightarrow \nabla f\left( x \right) - \nabla f\left( {{x^k}} \right) = {\nabla ^2}f\left( {{x^k}} \right)\left( {x - {x^k}} \right) = 0\\ \Rightarrow {x^{k + 1}} = {x^k} - {\nabla ^2}f{\left( {{x^k}} \right)^{ - 1}}\left( {\nabla f\left( {{x^{k + 1}}} \right) - \nabla f\left( {{x^k}} \right)} \right) \end{array} $$
可以看到当前步的Hessian矩阵本身跟其他的四个变量相关，因此拟牛顿法要做的就是利用迭代的方式更新Hessian矩阵:
$$ \begin{array}{l} {s_k} = {x^{k + 1}} - {x^k},{y_k} = \nabla f\left( {{x^{k + 1}}} \right) - \nabla f\left( {{x^k}} \right),{D_k} = {\nabla ^2}f{\left( {{x^k}} \right)^{ - 1}}\\ BFGS:{D_{k + 1}} = {D_k} + \left( {\frac{1}{{s_k^T{y_k}}} + \frac{{y_k^T{D_k}{y_k}}}{{{{\left( {s_k^T{y_k}} \right)}^2}}}} \right){s_k}s_k^T - \frac{1}{{s_k^T{y_k}}}\left( {{D_y}{y_k}s_k^T + {s_k}y_k^T{D_k}} \right),{D_0} = I \end{array} $$
可以看到Hessian矩阵的求解只依赖于上一步的矩阵和s,y两个一维向量。而为了解决Hessian矩阵的存储问题，工业界又提出了L-BFGS算法，即保存近m步的s和y的值，然后在计算当前步的Hessian矩阵时，循环迭代求解，不需要保存Hessian矩阵。
5.共轭梯度下降法
共轭梯度下降法最初是用来求解二次凸函数的最优值的：
$$ \begin{array}{l} \min \;f{\rm{ = }}\frac{1}{2}{x^T}Ax + {b^T}x + c\\ {d_1} = - \nabla f\left( {{x^1}} \right) = - {g_1},{\lambda _1} = \mathop {\min }\limits_\lambda \;f\\ {x^{k + 1}} = {x^k} + {\lambda _k}{d_k} \Rightarrow {g_{k + 1}} = \nabla f\left( {{x^{k + 1}}} \right)\\ {\lambda _k} = - \frac{{g_k^T{d_k}}}{{d_k^TA{d_k}}},{\beta _k} = - \frac{{d_k^TA{g_{k + 1}}}}{{d_k^TA{d_k}}}\\ {d_{k + 1}} = - {g_{k + 1}} + {\beta _k}{d_k} \end{array} $$
6.最小二乘法
最小二乘法或者岭回归算法一般是用来做曲线拟合问题的，比如：
$$ \min \;f = \left\| {Ax - b} \right\|_2^2 = {\left( {Ax - b} \right)^T}\left( {Ax - b} \right) $$
很显然这个问题很适合共轭梯度下降法，不过，我们利用拉格朗日乘子法可以很轻易求解：
$$ \begin{array}{l} f = {\left( {Ax - b} \right)^T}\left( {Ax - b} \right)\\ \left( 1 \right)df = tr\left( {df} \right)\\ = tr\left( {d{{\left( {Ax - b} \right)}^T}\left( {Ax - b} \right) + {{\left( {Ax - b} \right)}^T}d\left( {Ax - b} \right)} \right)\\ = tr\left( {{{\left( {Adx} \right)}^T}\left( {Ax - b} \right) + {{\left( {Ax - b} \right)}^T}Adx} \right)\\ = tr\left( {{{\left( {Ax - b} \right)}^T}Adx + {{\left( {Ax - b} \right)}^T}Adx} \right)\\ = tr\left( {2{{\left( {Ax - b} \right)}^T}Adx} \right)\\ \therefore \frac{{\partial f}}{{\partial x}} = 2{A^T}\left( {Ax - b} \right) = 0\\ \therefore x = {\left( {{A^T}A} \right)^{ - 1}}{A^T}b\\ \left( 2 \right)df = tr\left( {df} \right)\\ = tr\left( {d{{\left( {Ax - b} \right)}^T}\left( {Ax - b} \right) + {{\left( {Ax - b} \right)}^T}d\left( {Ax - b} \right)} \right)\\ = tr\left( {{{\left( {dAx} \right)}^T}\left( {Ax - b} \right) + {{\left( {Ax - b} \right)}^T}dAx} \right)\\ = tr\left( {{{\left( {Ax - b} \right)}^T}dAx + x{{\left( {Ax - b} \right)}^T}dA} \right)\\ = tr\left( {2x{{\left( {Ax - b} \right)}^T}dA} \right)\\ \therefore \frac{{\partial f}}{{\partial A}} = 2\left( {Ax - b} \right){x^T} = 0\\ \therefore A = b{x^T}{\left( {x{x^T}} \right)^{ - 1}} \end{array} $$
