2019-11-23 Gauss-Newton

2019-11-26 本文已影响0人苏格兰低地弟弟打滴滴

gaol5.1

最小二乘

最小化问题：

$f(x)=\frac{1}{2} \sum_{i=1}^{m} r_{i}^{2}(x)=\frac{1}{2} r(x)^{\mathrm{T}} r(x), \quad x \in \mathbb{R}^{n}, m \geqslant n$

样本个数大于等于参数维度。

在考虑 $f(x+d)=\frac{1}{2}r^T(x+d)r(x+d)$ 的时候，考虑泰勒二次展开：

0阶项是：

$\frac{1}{2}r^T(x)r(x)$

1阶项是：

$d^T(J(x)^Tr(x))$ 其中 $J_{m \times n}=\left(\begin{array}{ccc}{\partial_{1} r_{1}} & {\partial_{2} r_{1}} & {\cdots} & {\partial_{n} r_{m}}\\ {\vdots} & {} & {\vdots} \\ {\partial_{1} r_{m}} & {\partial_{2} r_{m}} & {\cdots} & {\partial_{n} r_{m}}\end{array}\right)$ 每个r里面是 $(x+d)$

2阶项是：

$\frac{1}{2} d^{\top}\left(J^{\top} J+S\right) d$ ，其中 $S_{n \times n}=\left(S_{p q}(x)\right)_{n \times n}$ ，其中 $S_{p q}(x)=\sum_{r=1}^{m} r_{i}(x) \partial_{p q} r_{i}(x)$

最优点 $\left\|S^{*}\right\|$ 取决于问题的非线性程度或者残量的大小。

小剩余算法：处理 $\left\|S^{*}\right\|$ 等于0或者比较小的情况。大剩余算法处理else。

最小二乘的牛顿方法： $\left(J_{k}^{\mathrm{T}} J_{k}+S_{k}\right) d_{k}=-J_{k}^{\mathrm{T}} r_{k}$ 对于一般的问题假如每一步都求一下 $S_{k}$ 就太麻烦了。所以要忽略掉 $S_{k}$ 或者用一阶数的导数信息去近似。

Gauss-Newton方法

直接用上面的牛顿方法相当于在每一步最小化二次函数： $\frac{1}{2} d^{\mathrm{T}} (J_{k}^{\mathrm{T}} J_{k} +S_k)d+d^{\mathrm{T}}\left(J_{k}^{\mathrm{T}} r_{k}\right)+\frac{1}{2} r_{k}^{\mathrm{T}} r_{k}$

但是那个S很难把握，所以我们考虑直接忽略掉，去最小化：

$\frac{1}{2} d^{\mathrm{T}} J_{k}^{\mathrm{T}} J_{k} d+d^{\mathrm{T}}\left(J_{k}^{\mathrm{T}} r_{k}\right)+\frac{1}{2} r_{k}^{\mathrm{T}} r_{k}$

而这个相当于线性最小二乘问题的极小化： $\min _{d \in \mathbb{R}^{n}} q_{k}(d)=\frac{1}{2}\left\|J_{k} d+r_{k}\right\|_{2}^{2}$ 所以极小点满足：

$J_{k}^{\mathrm{T}} J_{k} d=-J_{k}^{\mathrm{T}} r_{k}$

$d_{k}^{\mathrm{T}} g_{k}=d_{k}^{\mathrm{T}} J_{k}^{\mathrm{T}} r_{k}=-d_{k}^{\mathrm{T}} J_{k}^{\mathrm{T}} J_{k} d_{k}=-\left\|J_{k} d_{k}\right\|^{2}$ 所以如果J是满秩的，就是下降的。

2019-11-23 Gauss-Newton

最小二乘

Gauss-Newton方法

猜你喜欢

热点阅读