[原创]拟牛顿法/Quasi-Newton,DFP算法/Davidon-Fletcher-Powell,及BFGS算法/Broyden-Fletcher-Goldfarb-Shanno

 

在最优化领域,有几个你绝对不能忽略的关键词:拟牛顿、DFP、BFGS。名字很怪,但是非常著名。下面会依次地说明它们分别“是什么”,“有什么用” 以及 “怎么来的”。

但是在进入正文之前,还是要先提到一个概念上的区别,否则将影响大家的理解:其实DFP算法、BFGS算法都属于拟牛顿法,即,DFP、BFGS都分别是一种拟牛顿法。
阅读更多

[原创]最速下降法/steepest descent,牛顿法/newton,共轭方向法/conjugate direction,共轭梯度法/conjugate gradient 及其他

 

在最优化的领域中,这“法”那“法”无穷多,而且还“长得像”——名字相似的多,有时让人觉得很迷惑。

在自变量为一维的情况下,也就是自变量可以视为一个标量,此时,一个实数就可以代表它了,这个时候,如果要改变自变量的值,则其要么减小,要么增加,也就是“非左即右“,所以,说到“自变量在某个方向上移动”这个概念的时候,它并不是十分明显;而在自变量为n(n≥2)维的情况下,这个概念就有用了起来:假设自变量X为3维的,即每一个X是(x1, x2, x3)这样的一个点,其中x1,x2和x3分别是一个实数,即标量。那么,如果要改变X,即将一个点移动到另一个点,你怎么移动?可以选择的方法太多了,例如,我们可以令x1,x2不变,仅使x3改变,也可以令x1,x3不变,仅使x2改变,等等。这些做法也就使得我们有了”方向“的概念,因为在3维空间中,一个点移动到另一个点,并不是像一维情况下那样“非左即右”的,而是有“方向”的。在这样的情况下,找到一个合适的”方向“,使得从一个点移动到另一个点的时候,函数值的改变最符合我们预定的要求(例如,函数值要减小到什么程度),就变得十分有必要了。
阅读更多

[原创]Ridders求导算法

N年前,当我还是一个在校学生的时候,有一次到工厂里实习,看到某系统上运行的一个软件中显示的一条条曲线,以及其下的一些参数值,我问旁边开发那款软件的老师:某某值是怎么求出来的?老师说,是对曲线求导算出来的。当时我就心想,一个人开发出这款软件得综合多少个领域的知识才能做得到啊。从那时起,我的心中就埋下了一颗种子。时光匆匆,一眨眼就到了今天,因为学习其他算法的原因,涉及到了一些求导算法的编程,于是,本文必须得写。

求导算法应用广泛,例如,在LM算法中,需要对函数求导(但是,使用数值求导的方法来求导数值,会不会对LM算法的整个过程的效率造成较大影响,我不清楚,还没有试验),可以考虑使用数值求导算法来实现。

如何用程序实现求一个数学函数在某一点的导数值?由于计算机的舍入误差的存在,如果按导数的定义来求,精度将比较差。 我们先来看一下导数的定义:
阅读更多

[原创]选主元的高斯-约当(Gauss-Jordan)消元法解线性方程组/求逆矩阵

 

选主元的高斯-约当(Gauss-Jordan)消元法在很多地方都会用到,例如求一个矩阵的逆矩阵、解线性方程组(插一句:LM算法求解的一个步骤),等等。它的速度不是最快的,但是它非常稳定来自网上的定义:一个计算方法,如果在使用此方法的计算过程中,舍入误差得到控制,对计算结果影响较小,称此方法为数值稳定的,同时它的求解过程也比较清晰明了,因而人们使用较多。下面我就用一个例子来告诉你Gauss-Jordan法的求解过程吧。顺便再提及一些注意事项以及扩展话题。

对本文中所提到的“主元”等概念的解释,可以参考此链接

阅读更多

Brent's method

Brief introduction:

In numerical analysis, Brent's method is a complicated but popular root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less reliable methods.
在数值分析领域,Brent方法是一个复杂的、但是却很流行的寻根算法,它结合了二分法、割线法以及反向二次插值法的特点。它具有二分法的稳定性,但是它的速度却可与一些不太稳定的方法相比拟。

阅读更多

[原创]关于 最优化/Optimization 的一些概念解释

 

以下是我曾在学习“最优化”理论与实践中遇到的一些概念,我刚开始学的时候,有些东西看了很多遍都还觉得很别扭、晦涩难懂,在比较清楚地理解了之后,我打算把它们写下来,并试图以很通俗、但可能不十分严谨的方式解释、呈现出来,以使一部分正在这些概念中挣扎的人能有所解脱。

但是,请注意:有一些是我个人的理解,因个人水平有限,我不能保证完全正确,请您自己辨别。

 

(1)什么是“搜索方向”

阅读更多

[原创] LM(Levenberg-Marquard)算法的实现

 

LM算法,全称为Levenberg-Marquard算法,它可用于解决非线性最小二乘问题,多用于曲线拟合等场合。

LM算法的实现并不算难,它的关键是用模型函数 f 对待估参数向量 p 在其邻域内做线性近似,忽略掉二阶以上的导数项,从而转化为线性最小二乘问题,它具有收敛速度快等优点。LM算法属于一种“信赖域法”——所谓的信赖域法,此处稍微解释一下:在最优化算法中,都是要求一个函数的极小值,每一步迭代中,都要求目标函数值是下降的,而信赖域法,顾名思义,就是从初始点开始,先假设一个可以信赖的最大位移 s ,然后在以当前点为中心,以 s 为半径的区域内,通过寻找目标函数的一个近似函数(二次的)的最优点,来求解得到真正的位移。在得到了位移之后,再计算目标函数值,如果其使目标函数值的下降满足了一定条件,那么就说明这个位移是可靠的,则继续按此规则迭代计算下去;如果其不能使目标函数值的下降满足一定的条件,则应减小信赖域的范围,再重新求解。

事实上,你从所有可以找到的资料里看到的LM算法的说明,都可以找到类似于“如果目标函数值增大,则调整某系数再继续求解;如果目标函数值减小,则调整某系数再继续求解”的迭代过程,这种过程与上面所说的信赖域法是非常相似的,所以说LM算法是一种信赖域法。

 

阅读更多