想写好这部分不容易，详情请看参考文献，这里只是做一个导读，秋招结束后再回来补。
最优化方法分为 Line Search 和 Trust Region 两类。Line Search 方法先固定下降方向，再在该方向上搜索步长，典型的有 最速下降法 和 高斯牛顿法 ； Trust Region 方法先固定搜索区域，再在该区域内找最优的点，典型的有 LM算法 。
考虑最小二乘问题：
$$
\underset{x}{min}\frac{1}{2}||f(x)||^2_2
$$
其中，这整个式子称为目标函数，自变量x有n维，f是任意非线性函数，它有m维。
参考：《计算机视觉中的数学方法》13.3.1 最速下降法
又叫一阶梯度法。让x加一个增量 $\Delta x$ ，让x朝着梯度下降的方向走，使得 $\underset{x}{min}\frac{1}{2}||f(x + \Delta x)||^2_2$ 变小。问题是走多远呢？将目标函数在x附近进行一阶泰勒展开，得到目标函数的近似函数，一般取 $\Delta x = -J^T(x)$ 。其中 $J(x)$ 也叫作雅克比矩阵，是向量 向量f(x)关于向量x 的一阶梯度。
但这样有2个问题，
问题一：直接取 $\Delta x = -J^T(x)$ （注意：这里 $J(x)是||f(x)||_2^2$关于向量x的导数，但是也叫雅克比矩阵）只能保证目标函数下降，并不能保证下降最快。为了更快的下降，有时候我们取 $\Delta x = -\lambda J^T(x)$ ，选择一个合适的 $\lambda$ ，令目标函数（注意不是它的近似函数，这里指的就是目标函数本身）在 $\Delta x$ 的方向上取得最小值（只是在这个方向上取得最小值）。那么这个 $\lambda$ 取值怎么确定呢？这又是一个最优化问题，这次可以对 $\lambda$ 做二阶泰勒展开，用牛顿法搜索到最好的 $\lambda$ （注意，前面是对向量x泰勒展开，这次是对 $\lambda$ 进行泰勒展开）。这个确定 $\lambda$ 的方法叫做线性搜索（在《计算机视觉中的数学方法》中好像叫一维搜索）。
问题二：最速下降法每次迭代，求出 $\lambda\Delta x$ 是为了让目标函数在 $\Delta x$ 方向下降最大，$\Delta x$ 方向只是目标函数在x处的梯度，走远了以后目标函数的梯度肯定发生改变，所以让目标函数在 $\Delta x$ 方向下降最大不一定目标函数就下降最大，这种方法过于贪心，容易走出锯齿路线，反而增加迭代次数。
注意：这里做一阶展开，一阶展开是个线性函数，在低维度来说就是一条直线，根本没有最小值一说，所以这种方法的近似函数只能确定个方向，要想确定步长，还得挨个把 $\lambda\Delta x$ 代入原目标函数，看看值是增大还是变小了，这样才能找得到在这个方向上目标函数的最小值，以此确定步长。这就是线性搜索。
又叫二阶梯度法。最速下降法只使用一阶泰勒展开，对目标函数近似不够，可能导致下降缓慢甚至失败。牛顿法与最速下降法类似，只不过在求近似函数时，是采用二阶泰勒展开。对近似函数求关于 $\Delta x$ 的导数，另导数为0可以得到近似函数的极值点，可以得到 $H\Delta x=-J^T$ ，其中H矩阵是向量f(x)关于向量x的二阶梯度，也叫作海森矩阵，如果海森矩阵有逆矩阵或者伪逆的话，则增量 $\Delta x=-H^+J^T$ 。
但这种这种方法存在1个问题：
问题一：当问题规模非常大时，海森矩阵的求解非常困难（我的理解是求解速度很慢？），我们通常避免去计算海森矩阵，而用其他矩阵去近似海森矩阵。
注意：这里 $J(x)是||f(x)||_2^2$关于向量x的导数，但是也叫雅克比矩阵
牛顿法中需要计算海森矩阵，对于大规模问题这是很困难的，因此高斯-牛顿法用 $J^T(x)J(x)$ 替代海森矩阵H，避免了海森矩阵的求解。
将 $f(x)$ 在向量x附近进行一阶泰勒展开（注意，不是对目标函数 $\frac{1}{2}||f(x)||^2_2$ 进行泰勒展开），得到 $f(x)$ 的近似函数。用近似函数去替换目标函数里的 $f(x)$ ，得到近似的目标函数，同理，依旧是对目标函数求导，令导数为0，求得目标函数的极值点。令导数为0，可以得到方程组 $J(x)^TJ(x)\Delta x = -J(x)^Tf(x)$ ，令 $H=J(x)^TJ(x), g=-J(x)^Tf(x)$ ，则可以得到与牛顿法近似的式子 $H\Delta x=g$ ，所以我们才说高斯-牛顿法用 $J^T(x)J(x)$ 替代海森矩阵H，避免了海森矩阵的求解。
与牛顿法一样，求解这个方程组，可以得到 $\Delta x$ 。
这个方法同样有一些问题：
问题一：$H=J(x)^TJ(x)$ 可能为奇异矩阵或者病态(illcondition)的情况，此时求解出来的 稳 $\Delta x$ 定性较差。
问题二：就算 $H=J(x)^TJ(x)$ 非奇异也非病态，求出来的 $\Delta x$ 的模值也可能太大，会导致我们的近似不准确，甚至无法保证目标函数下降。这种情况，可以使用线性搜索的方法，在确定了下降方向 $\Delta x$ 后，再确定一个步长 $\lambda$ ，采用 $\lambda \Delta x$ 作为下降的增量，这个 $\lambda$ 保证了近似目标函数在这一步迭代中达到最小（但不保证目标函数达到最小） 。
注意：这里 $J(x)是f(x)关于向量x的导数，但是也叫雅克比矩阵。
又叫阻尼牛顿法(Damped Newton Method)。由于高斯牛顿法中采用二阶泰勒展开去近似函数 $f(x)$ ，只能在站开点附近有比较好的近似效果，那么我们可以加一个约束，约束求出的 $\Delta x$ 在某个信赖区域内(Trust Region)，在信赖区域内我们认为近似是有效的，在信赖区域外，近似可能会出问题。LM算法就是这么一种信赖区域的方法。
怎么确定信赖区域的范围？我们可以用 $\rho=\frac{f(x+\Delta x)-f(x)}{J(x)\Delta x}$ 去评价近似得好不好，其中 $\rho$ 的分子表示实际函数的下降值，分母表示泰勒一阶展开的近似函数的下降值。如果 $\rho$ 接近1，则近似是好的，如果 $\rho$ 很小，则说明实际减小的值要远少于近似减小的值，则认为近似比较差，需要缩小近似范围；如果 $\rho$ 很大，则说明实际下降的值比预计的大，我们可以放大近似范围。（TODO:这里不太清楚 $\rho$ 很大有没有包括其大于1的情况，还有就是为什么很大就可以放大近似范围？）
注意：这里 $J(x)是f(x)关于向量x的导数，但是也叫雅克比矩阵。
$$
f(x) = \sum_{i=0}^{n}\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i = f(x_0) + f'(x_0)(x-x_0) + ...\\
f(x+\Delta x) = \sum_{i=0}^{n}\frac{f^{(i)}(x)}{i!}(\Delta x)^i = f(x) + f'(x)\Delta x + ...
$$
（1）广义定义：设M是n阶方阵，如果对任何非零向量x，都有 $x^TMx \gt 0$ ，就称M为正定矩阵。
（2）狭义定义：设M是n阶实对称方阵，当且仅当对任何非零实系数向量x，都有 $x^TMx>0$ ，就称M为正定矩阵。
（1）广义定义：设M是n阶方阵，如果对任何非零向量x，都有 $x^TMx \ge 0$ ，就称M为半正定矩阵。
（2）狭义定义：设M是n阶实对称方阵，当且仅当对任何非零实系数向量x，都有 $x^TMx \ge 0$ ，就称M为半正定矩阵。
判定定理1：对称矩阵A为正定的充分必要条件是:A的特征值全为正。（而对角阵的特征值正好等于对角线上的那些元素。）
判定定理2：对称矩阵A为正定的充分必要条件是:A的各阶(顺序)主子式都为正。注意：负定的充分必要条件是：奇数阶(顺序)主子式为负，偶数阶(顺序)主子式为正。
判定定理3：任意阵A为正定的充分必要条件是:A合同于单位阵。
参考：百度百科-主子式
主子式定义：在n 阶行列式中，取出的k行k列得到的新行列式，称为n阶行列式的k阶主子式。(注意：取得行号和列号要相同，如1,3,7行和1,3,7列)
特殊的，由前 $[1, k]$ 行和前 $[1, k]$ 列所确定的主子式即为n阶行列式的k阶顺序主子式。
举例：
设矩阵M
$$
M = \begin{bmatrix}
m_{11} & m_{12} & m_{13} \
m_{21} & m_{22} & m_{23} \
m_{31} & m_{32} & m_{33}
\end{bmatrix}
$$
那么其1阶、2阶、3阶顺序主子式分别为
$$
一阶： m_{11} \
二阶：\begin{vmatrix}
m_{11} & m_{12} \
m_{21} & m_{22} \
\end{vmatrix} \
三阶：\begin{vmatrix}
m_{11} & m_{12} & m_{13} \
m_{21} & m_{22} & m_{23} \
m_{31} & m_{32} & m_{33}
\end{vmatrix}
$$
将 $x^TMx$ 的表达式列出来可能有助于理解：
$$
\begin{array}{l}
\boldsymbol{x} = [x_1 \quad x_2 \quad x_3]^T \
M = \begin{bmatrix}
m_{11} & m_{12} & m_{13} \
m_{21} & m_{22} & m_{23} \
m_{31} & m_{32} & m_{33}
\end{bmatrix} \
\boldsymbol{x}^TM\boldsymbol{x} = \
= [m_{11}x_1+m_{21}x_2+m_{31}x_3 \quad m_{12}x_1+m_{22}x_2+m_{32}x_3 \quad m_{13}x_1+m_{23}x_2+m_{33}x_3]
\begin{bmatrix}
x_1 \
x_2 \
x_3
\end{bmatrix} \
= m_{11}x_1^2 + (m_{12}+m_{21})x_1x_2 + (m_{13}+m_{31})x_1x_3 + m_{22}x_2^2 + (m_{23}+m_{32})x_2x_3 + m_{33}x_3^2
\end{array}
$$
高斯牛顿法是牛顿法在最小二乘问题上的特例，但又不是完全套用牛顿法，而是在套用的过程中做了简化。
参考：https://zhuanlan.zhihu.com/p/103724149
也可以参考《视觉SLAM十四讲》，一个对目标函数 $\frac{1}{2} ||f(x)||_2^2$ 求导，一个对f(x)求导