求解Non-Linear Least Square问题

APSchmidt · 发表于 2022-2-21 11:35

目前求解non linear least square问题的算法有很多种，但是总的可以归纳为两种:

基于trust region(信任域)的优化算法,代表是LM算法(Levenberg-Marquardt Mehod)
基于line search(线搜索)的优化算法,代表是GM算法(Gauss_netwon)

trust region和line search的区别是: trust region会先找下降的步长，再找下降的方向; 而line search会先找下降的方向，再找下降的步长。
line search算法

line search算法的步骤如下:

已知初始点 $x = x_0$
梯度下降量 $\Delta x = -H^{-1}(x) g(x)$
求 $\arg \min_\mu \frac{1}{2} \| F(x + \mu \Delta x) \|^2$
如果足够小则停止迭代，否则 $x = x + \mu \Delta x$
重新从步骤2开始执行直之收敛

其中是hessian矩阵的近似(求解hessian矩阵计算量较大，故一般采用hessian矩阵的近似), $g(x)$ 是gradient(即优化目标函数的一阶导数)。的不同选取策略会导致的下降方向有所不同。
trust region算法

trust region算法步骤如下:

已知: 初始点 $x_0$ 和一个信任域
求解: $\arg \min_{\Delta x} \frac{1}{2}\|J(x)\Delta x + F(x)\|^2$ 使得 $\|D(x)\Delta x\|^2 \le \mu \quad and \quad L \le x + \Delta x \le U$
$\rho = \frac{\displaystyle \|F(x + \Delta x)\|^2 - \|F(x)\|^2}{\displaystyle \|J(x)\Delta x + F(x)\|^2 - \|F(x)\|^2}$
如果 $\rho > \epsilon$ 则: $x = x + \Delta x$
如果 $\rho > \eta_1$ 则: $\mu = 2 \mu$
否则 $\rho < \eta_2$ 则: $\mu = 0.5 * \mu$
重新从步骤2开始执行

注释: 是信任域半径, $D(x)$ 是在作用域 $F(x)$ 和内衡量步长好坏的参数; 比如增加步长，优化的目标函数的误差下降的多少。trust region通过增加和减小trust region的半径来控制优化目标函数的误差, 从而来影响
trust region算法可以简化成:

$\arg \min_{\Delta x} \quad \frac{1}{2}\|J(x)\Delta x + F(x)\|^2 \\ \text{such that} \quad \|D(x)\Delta x\|^2 \le \mu\\ \quad L \le x + \Delta x \le U \\$
参考资料:

http://ceres-solver.org/nnls_solving.html#

		自动登录	找回密码
密码			立即注册