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