求解Non-Linear Least Square问题
目前求解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算法的步骤如下:
[*]已知初始点 https://www.zhihu.com/equation?tex=x+%3D+x_0
[*]梯度下降量 https://www.zhihu.com/equation?tex=%5CDelta+x+%3D+-H%5E%7B-1%7D%28x%29+g%28x%29
[*]求 https://www.zhihu.com/equation?tex=%5Carg+%5Cmin_%5Cmu+%5Cfrac%7B1%7D%7B2%7D+%5C%7C+F%28x+%2B+%5Cmu+%5CDelta+x%29+%5C%7C%5E2
[*]如果足够小则停止迭代，否则 https://www.zhihu.com/equation?tex=x+%3D+x+%2B+%5Cmu+%5CDelta+x
[*]重新从步骤2开始执行直之收敛
其中是hessian矩阵的近似(求解hessian矩阵计算量较大，故一般采用hessian矩阵的近似), https://www.zhihu.com/equation?tex=g%28x%29 是gradient(即优化目标函数的一阶导数)。的不同选取策略会导致的下降方向有所不同。
trust region算法
trust region算法步骤如下:
[*]已知: 初始点 https://www.zhihu.com/equation?tex=x_0 和一个信任域
[*]求解:https://www.zhihu.com/equation?tex=+%5Carg+%5Cmin_%7B%5CDelta+x%7D+%5Cfrac%7B1%7D%7B2%7D%5C%7CJ%28x%29%5CDelta+x+%2B+F%28x%29%5C%7C%5E2 使得 https://www.zhihu.com/equation?tex=%5C%7CD%28x%29%5CDelta+x%5C%7C%5E2+%5Cle+%5Cmu+%5Cquad+and+%5Cquad+L+%5Cle+x+%2B+%5CDelta+x+%5Cle+U
[*]https://www.zhihu.com/equation?tex=%5Crho+%3D+%5Cfrac%7B%5Cdisplaystyle+%5C%7CF%28x+%2B+%5CDelta+x%29%5C%7C%5E2+-+++++++%5C%7CF%28x%29%5C%7C%5E2%7D%7B%5Cdisplaystyle+%5C%7CJ%28x%29%5CDelta+x+%2B+F%28x%29%5C%7C%5E2+-+++++++%5C%7CF%28x%29%5C%7C%5E2%7D
[*]如果 https://www.zhihu.com/equation?tex=%5Crho+%3E+%5Cepsilon则: https://www.zhihu.com/equation?tex=x+%3D+x+%2B+%5CDelta+x
[*]如果 https://www.zhihu.com/equation?tex=%5Crho+%3E+%5Ceta_1 则: https://www.zhihu.com/equation?tex=%5Cmu+%3D+2++%5Cmu
[*]否则 https://www.zhihu.com/equation?tex=%5Crho+%3C+%5Ceta_2 则: https://www.zhihu.com/equation?tex=%5Cmu+%3D+0.5+%2A+%5Cmu
[*]重新从步骤2开始执行
注释:是信任域半径, https://www.zhihu.com/equation?tex=D%28x%29 是在作用域 https://www.zhihu.com/equation?tex=F%28x%29 和内衡量步长好坏的参数; 比如增加步长，优化的目标函数的误差下降的多少。trust region通过增加和减小trust region的半径来控制优化目标函数的误差, 从而来影响
trust region算法可以简化成:
https://www.zhihu.com/equation?tex=%5Carg+%5Cmin_%7B%5CDelta+x%7D+%5Cquad+%5Cfrac%7B1%7D%7B2%7D%5C%7CJ%28x%29%5CDelta+x+%2B+F%28x%29%5C%7C%5E2+%5C%5C++++%5Ctext%7Bsuch+that%7D+%5Cquad+%5C%7CD%28x%29%5CDelta+x%5C%7C%5E2+%5Cle+%5Cmu%5C%5C+++++%5Cquad+L+%5Cle+x+%2B+%5CDelta+x+%5Cle+U+%5C%5C
参考资料:
[*]http://ceres-solver.org/nnls_solving.html#
页:
[1]