一、最小二乘法

回顾最小二乘问题:

$$\underset{x}{\min }F(x)=\frac{1}{2}\sum _{i=1}^N{\Vert f(x)\Vert }_2^2$$

观察这个函数可以发现，它同二次函数一样，存在着极小值，要使得$F(x)$达到最小值，只需要令：

$$\frac{\partial \mathbf{F}(x)}{\partial x}=0$$
我们其成为(Jacobian)雅可比矩阵:
$$\begin{array}{rl}\mathbf{J}(x)& =\frac{\partial F(x)}{\partial x}\\ \mathbf{J}(x)& =(\frac{\partial \mathbf{F}(x)}{\partial x_1},\frac{\partial \mathbf{F}(x)}{\partial x_2},...,\frac{\partial \mathbf{F}(x)}{\partial x_n})\end{array}$$
我们将雅可比矩阵的转置称为梯度：
$$▽F(x)=J^T(x)=(\frac{\partial F(x)}{\partial x_1},\frac{\partial F(x)}{\partial x_2},...,\frac{\partial F(x)}{\partial x_n}{)}^T$$
如果无法直接求解最小二乘问题，我们就需要利用迭代的方法来实现求解最优值。

我们给定一个初值$x_0$以及$λ $步长，则参数的更新方式为：
$${\mathbf{x}}^{(\mathbf{k}+1)}={\mathbf{x}}^{(\mathbf{k})}-\mathbf{\lambda }{\mathbf{J}}^{\mathbf{T}}({\mathbf{x}}^{(\mathbf{k})})$$
这种方式我们称为梯度下降法。

具体的，存在一种映射变化h，观测值输入为x，输出为y(可以理解为数据集)，为了找到一种最优的映射来估计z状态，使得：

$$\begin{array}{rl}\underset{\theta }{\min }R(\theta )& =\frac{1}{2}\sum _{i=1}^N{\Vert z-h_{\theta }(x,\theta )\Vert }_2^2\\ & =\frac{1}{2}(z-h_{\theta }(x,\theta ){)}^T(z-h_{\theta }(x,\theta ))\end{array}$$
对其泰勒展开：
$$R(\theta +\Delta \theta )\approx R(\theta )+J_{\theta }\cdot \Delta \theta +\frac{1}{2}\cdot \Delta {\theta }^T\cdot H_{\theta }\cdot \Delta \theta ，（H_{\theta }为海塞矩阵）$$
其中雅克比矩阵：
$$\begin{array}{rl}{J}_{\theta }(\theta )& =\frac{\partial R(\theta )}{\partial \theta }\\ {\mathbf{J}}_{\mathbf{\theta }}(\mathbf{\theta })& =({\mathbf{h}}_{\mathbf{\theta }}(\mathbf{x},\mathbf{\theta })-\mathbf{z}{)}^{\mathbf{T}}\frac{\partial {\mathbf{h}}_{\mathbf{\theta }}(\mathbf{x},\mathbf{\theta })}{\partial \mathbf{\theta }}\end{array}$$
$$⟹{\mathbf{J}}_{\mathbf{\theta }}^{\mathbf{T}}(\mathbf{\theta })=(\frac{\partial {\mathbf{h}}_{\mathbf{\theta }}(\mathbf{x},\mathbf{\theta })}{\partial \mathbf{\theta }}{)}^{\mathbf{T}}\cdot ({\mathbf{h}}_{\mathbf{\theta }}(\mathbf{x},\mathbf{\theta })-\mathbf{z})$$

二、求解增量方程

我们也可以利用增量Δx来求最优解，把$\Delta x$当作参数，给定初值$x_0$，则最优解：

$$x=x_0+\Delta x$$
我们把$\Delta x$作为优化的参数：
$$\underset{\Delta x}{\min }F(x+\Delta x)=\frac{1}{2}\sum _{i=1}^N{\Vert f(x+\Delta x)\Vert }_2^2$$
对于$F(x+\Delta x)$的泰勒展开式：
$$F(x+\Delta x)\approx F(x)+J_x\cdot \Delta x+\frac{1}{2}\cdot \Delta x^T\cdot H_x\cdot \Delta x$$
令$F(x)$为无穷小量，对$\Delta x$求导，并令导数为0：
$$\begin{gathered} J_x+\Delta x^T{H}_x \\ ⟹J_x^T+H_x\Delta x=0 \end{gathered}$$
矩阵的求导用到 两个重要的知识点：

若a和A不是关于x的函数矩阵，则有：
$$\begin{gathered} \frac{\partial a\cdot \mathbf{x}}{\partial \mathbf{x}}=a \\ \frac{\partial {\mathbf{x}}^{T}A\cdot \mathbf{x}}{\partial \mathbf{x}}=2{\mathbf{x}}^{T}A \\ \frac{\partial {\mathbf{u}}^T\cdot \mathbf{v}}{\partial \mathbf{x}}={\mathbf{u}}^T\cdot \frac{\partial \mathbf{v}}{\partial \mathbf{x}}+{\mathbf{v}}^T\cdot \frac{\partial \mathbf{u}}{\partial \mathbf{x}} \end{gathered}$$
得到增量方程:
$$H_x\Delta x=-J_x^T$$
这种方法又被称为 牛顿法 ,但存在一个缺点就是H的计算太过复杂，不利于直接利用。所以对于最小二乘法，常常有比较实用的方法：高斯牛顿法和列文伯格-马夸尔特法。

高斯牛顿法

对于优化函数

$$\underset{\Delta x}{\min }F(x+\Delta x)=\frac{1}{2}\sum _{i=1}^N{\Vert f(x+\Delta x)\Vert }_2^2$$
对f(x)进行泰勒展开：
$$\begin{array}{rl}f(x+\Delta x)& \approx f(x)+J_x\cdot \Delta x+\frac{1}{2}\cdot \Delta x^T\cdot H_x\cdot \Delta x\\ ⟹F(x+\Delta x)& =\frac{1}{2}\sum _{i=1}^N{\Vert f(x)+J_x\cdot \Delta x\Vert }_2^2\\ & =\frac{1}{2}(f(x)+J_x\cdot \Delta x{)}^T(f(x)+J_x\cdot \Delta x)\end{array}$$求导：
$$\frac{\partial F(x+\Delta x)}{\partial \Delta x}=(f(x)+J_x\cdot \Delta x{)}^T\cdot J_x$$
令其等于0：
$$\begin{array}{rl}(f(x)+J_x\cdot \Delta x{)}^T\cdot J_x& =0\\ ⟹J_x^T\cdot (f(x)+J_x\cdot \Delta x)& =0\\ ⟹J^T(x)\cdot f(x)+J^T(x)\cdot J(x)\cdot & \Delta x=0\end{array}$$
所以增量方程为:
$$\begin{array}{rl}{J}^T(x)\cdot J(x)\cdot \Delta x& =-J^T(x)\cdot f(x)\\ ⟹H\Delta x& =b\\ (H=J^T(x)\cdot J(x),b=-J^T(x)\cdot f(x))& \end{array}$$

迭代步骤：
1.给定初值x0;
2.求出第k次迭代的$J(x_k)$和$f(x_k)$;
3.求解$\Delta x_k$,可以用$LD{L}^T$分解法求解
4.Δx满足要求，退出迭代，否则令$x_{(k+1)}=x_k+\Delta x_k$
 

列文伯格-马夸尔特方法

推导略；
目标函数：
$$L(\Delta x_k,\lambda )=\frac{1}{2}\sum _{i=1}^N{\Vert f(x_k)+J^T(x_k)\Delta x_k)\Vert }_2^2+\frac{\lambda }{2}({\Vert D\cdot \Delta x_k\Vert }^2-\mu )$$
一般的，D矩阵为$J^{T}J$的对角元素平方根；
相当于求解方程:
$$(\mathbf{H}+\lambda \mathbf{I})\cdot \Delta x_k=g$$
这种方法可以避免$H$矩阵为奇异矩阵（奇异矩阵不可逆），当λ趋近于0时，相当于是高斯牛顿法；当λ很大时，相当于是梯度下降法。