非线性优化
假设有目标函数：
\min _{x} F(\boldsymbol{x})=\frac{1}{2}\|f(\boldsymbol{x})\|_{2}^{2}
我们要求其最小值，当然是对目标函数进行求导，但通常目标函数是非线性的，因此我们需要通过以下步骤对目标函数进行求解：
- 给定初值
x_0；
- 对于第
k次迭代，寻找增量
\Delta x，使
\|f(\boldsymbol{x}+\Delta \boldsymbol{x})\|_{2}^{2}最小；
- 若
\Delta x足够小，停止迭代；
- 否则，令
x_{k+1}=x_k+\Delta x，返回步骤2；
常见的寻找
\Delta x的方法有：
我们对上述目标函数进行泰勒展开：
F\left(\boldsymbol{x}_{k}+\Delta \boldsymbol{x}_{k}\right) \approx F\left(\boldsymbol{x}_{k}\right)+\boldsymbol{J}\left(\boldsymbol{x}_{k}\right)^{T} \Delta \boldsymbol{x}_{k}+\frac{1}{2} \Delta \boldsymbol{x}_{k}^{T} \boldsymbol{H}\left(\boldsymbol{x}_{k}\right) \Delta \boldsymbol{x}_{k}
其中，
J(x)为一阶导数，即Jacobian矩阵，
H(x)为二阶导数，即Hessian矩阵。我们将上式改写，则有下式：
\Delta \boldsymbol{x}=\underset{\Delta x}{\arg \min }\left(F(\boldsymbol{x})+\boldsymbol{J}(\boldsymbol{x})^{T} \Delta \boldsymbol{x}+\frac{1}{2} \Delta \boldsymbol{x}^{T} \boldsymbol{H}(\boldsymbol{x}) \Delta \boldsymbol{x}\right)
1. 最速下降法
我们将二阶导数忽略，只保留一阶导数，我们寻找最快下降方向，将导数取反，则可保证函数下降，则有：
\Delta \boldsymbol{x}=-\lambda \boldsymbol{J}(\boldsymbol{x})
其中，
\lambda称为步长，在深度学习中称为学习率。
这种方法是最简单的非线性优化方法，但其需要进行很多次迭代。
2. 牛顿法
我们将一阶导数，二阶导数全部保留，对增量
\Delta x进行求导，并令其为0，则可以得到增量方程：
H \Delta x=-J^{T}
则增量的解为：
\Delta x=-H^{-1}J^{T}
这种方法比最速下降法迭代少，更精确，但其Hessian矩阵计算过于复杂。
3. 高斯牛顿法
我们对
f(x)进行一阶泰勒展开，则有：
f(x+\Delta x) \approx f(x)+J(x) \Delta x
我们再对上式建立目标函数，如下所示：
\Delta x^{*}=\arg \min _{\Delta x} \frac{1}{2}\|f(x)+J(x) \Delta x\|_{2}^{2}
我们对上式进行求导，并令导数为0，则可以得到下面方程：
J^{T} J \Delta x=-J^{T} f(x)
将
J^TJ记作
H，
-J^Tf(x)记作
g，则有：
H \Delta x=g
高斯牛顿法，使用
J^TJ避免了对
H矩阵直接计算，减少了复杂度，但是通常
H是正定可逆的，一般情况下
J^TJ却是不可逆的，此时方程陷入病态，导致无法求解，算法不收敛。继续改进。
4.LM算法
高斯牛顿只有在展开点附件才会有比较好的近似效果，LM算法则给
\Delta x增加了一个信赖域，来限制其大小，信赖域内部认为可信，否则不可信。目标函数如下：
\Delta \boldsymbol{x}=\underset{\Delta x}{\arg \min } \frac{1}{2}\left\|f(\boldsymbol{x})+\boldsymbol{J}(\boldsymbol{x})^{T} \Delta \boldsymbol{x}\right\|_{2}^{2}, \quad \text { s.t. }\|\boldsymbol{D} \Delta \boldsymbol{x}\| \leq \mu
其中
\mu为信赖域半径，
D为系数矩阵，我们使用拉格朗日乘子将上式进行构造：
\mathcal{L}(\Delta \boldsymbol{x}, \lambda)=\frac{1}{2}\left\|f(\boldsymbol{x})+\boldsymbol{J}(\boldsymbol{x})^{T} \Delta \boldsymbol{x}\right\|_{2}^{2}+\frac{\lambda}{2}\left(\|\boldsymbol{D} \Delta \boldsymbol{x}\|_{2}^{2}-\mu\right)
其中
\lambda为拉格朗日乘子，对上式进行求导，可得:
\Delta \boldsymbol{x}=-\left(\boldsymbol{J} \boldsymbol{J}^{T}+\lambda \boldsymbol{D}^{T} \boldsymbol{D}\right)^{-1} \boldsymbol{g}
如果将信赖域当成球状，则有
D=I，上式为:
\Delta \boldsymbol{x}=-\left(\boldsymbol{J} \boldsymbol{J}^{T}+\lambda I\right)^{-1} \boldsymbol{g}
当
\lambda较小时，LM算法接近高斯牛顿法，
\lambda较大时，LM算法接近梯度下降法。
此外信赖域大小我们可以通过实际模型和近似模型变化量的比值来确定，差异较小，我们就放大信赖域，差异较大，我们就缩小信赖域，比值定义如下：
\rho=\frac{f(\boldsymbol{x}+\boldsymbol{\Delta} \boldsymbol{x})-f(\boldsymbol{x})}{\boldsymbol{J}(\boldsymbol{x})^{T} \Delta \boldsymbol{x}}
具体的算法流程为:
- 给定初值
x_0，系数矩阵
D和信赖域半径
\mu;
k次迭代求解增量
\Delta x_k；
- 若增量足够小，停止迭代；
- 若
\rho > \frac{3}{4}，则设置
\mu = 2\mu，返回步骤2；
- 若
\rho<\frac{1}{4}，则设置
\mu=\frac{1}{2}\mu，返回步骤2；
- 若
\rho大小合适，则
x_{k+1}=x_{k}+\Delta x_k，返回步骤2；
5 Dog-Leg算法
其结合了高斯牛顿法与最速下降法，我们先看最速下降法，有下式：
f\left(x+\alpha h_{s d}\right) \approx f(x)+\alpha J(x) h_{s d}
则：
F\left(x+\alpha h_{s d}\right) \approx \frac{1}{2}\left\|f(x)+\alpha J(x) h_{s d}\right\|^{2}
=F(x)+\alpha h_{s d}^{T} J(x)^{T} f(x)+\frac{1}{2} \alpha^{2}\left\|J(x) h_{s d}\right\|^{2}
我们对上式进行求导，令导数为0，可得：
\alpha=-\frac{h_{s d}^{T} J(x)^{T} f(x)}{\left\|J(x) h_{s d}\right\|^{2}}
再看高斯牛顿法：
J^{T} J h_{gn}=-J^{T} f(x)
至此我们有两个待选的解：
\alpha h_{sd}和
h_{gn}。
Dog-Leg的迭代步长
h_{dl}需要满足的关系式(trust region)：
if
\left\|h_{g n}\right\| \leq \Delta，
h_{dl}=h_{gn} else if
\left\|\alpha h_{s d}\right\| \geq \Delta，
h_{d l}=\frac{\Delta}{\left\|h_{g n}\right\| d} h_{s d} else
h_{d l}=\alpha h_{s d}+\beta\left(h_{g n}-\alpha h_{s d}\right)，选择
\beta使得
\left\|h_{d l}\right\|=\Delta 信赖域半径计算与LM算法类似，只不过半径选择不一样：
\left\{\begin{array}{ll}
\text { if } \rho>0.75 & \Delta=\max \left\{\Delta, 3 *\left\|h_{d l}\right\|\right\} \\
\text { if } \rho<0.25 & \Delta=\Delta / 2
\end{array}\right.
具体的算法流程：
- 初始化
\Delta_0；
- 求解最速下降法增量，如果太小，则退出；计算高斯牛顿法增量，如果太小，也退出；
- 计算信赖域半径，如果太小，则退出；
- 根据高斯牛顿法与最速下降法分别计算
h_{gn}和
h_{sd}，然后计算迭代步长
\alpha；
- 根据3，4计算Dog-Leg步进值
h_{dl}，若太小，则退出；
x_{k+1}=x_{k}+h_{dl}，计算增益
\rho更改信赖域半径，返回步骤2；
