[原创] 再谈 最速下降法/梯度法/Steepest Descent

转载请注明出处:http://www.codelast.com/

最速下降法(又称梯度法,或Steepest Descent),是无约束最优化领域中最简单的算法,单独就这种算法来看,属于早就“过时”了的一种算法。但是,它的理念是其他某些算法的组成部分,或者说是在其他某些算法中,也有最速下降法的“影子”。因此,我们还是有必要学习一下的。
我很久以前已经写过一篇关于最速下降法的文章了,但是这里我还打算再写一篇,提供更多一些信息,让大家可以从更简单生动的方面去理解它。… Read More

[原创]一维搜索中的划界(Bracket)算法

转载请注明出处:http://www.codelast.com/

很多最优化算法需要用到一维搜索(line search)子算法,而在众多的一维搜索算法中,大多数都要求函数被限制在一个单峰区间内,也就是说,在进行一维搜索的区间内,函数是一个单峰函数。尽管有一些改进的一维搜索算法(例如 H\ddot opfinger 建议的一种改进过的黄金搜索算法)可以处理函数非单峰的情况,但是,在没有确定函数在一个区间内是单峰的之前,即使在搜索过程中,函数值持续减小,我们也不能说极小值是一定存在的,因此,找出一个区间,在此区间之内使函数是单峰的,这个过程是必需的(我更倾向于接受这种观点)。这个过程就叫作划界Bracket)。Bracket这个单词是括号的意思,很形象——用括号包住一个范围,就是划界。在某些书中,划界算法也被称为进退法。… Read More

[原创]最优化/Optimization文章合集

转载请注明出处:http://www.codelast.com/

最优化(Optimization)是应用数学的一个分支,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。我一直对最优化比较感兴趣,所以写过一些相关的笔记,可能有不正确的地方,但请学术派、技术流们多多包涵。

【1】拟牛顿法/Quasi-Newton,DFP算法/Davidon-Fletcher-Powell,及BFGS算法/Broyden-Fletcher-Goldfarb-Shanno

【2】最速下降法/steepest descent,牛顿法/newton,共轭方向法/conjugate direction,共轭梯度法/conjugate gradient 及其他

【3】Ridders求导算法

【4】选主元的高斯-约当(Gauss-Jordan)消元法解线性方程组/求逆矩阵
文章来源:http://www.codelast.com/
【5】关于 最优化/Optimization 的一些概念解释

【6】最小二乘的理论依据

【7】Powell共轭方向集方法(Powell's Conjugate Direction Method)的实现Read More

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

转载须注明出处:http://www.codelast.com/

 

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

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

[原创]Ridders求导算法

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

另外,请注意下面的声明

转载必须注明出处:本文来自:http://www.codelast.com/

 

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

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

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

转载请注明出处:http://www.codelast.com/

 

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

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

 

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

Read More

[原创]黄金比例搜索算法(Golden Section Search)的实现

转载请注明出处:http://www.codelast.com/

 

黄金比例搜索算法/黄金分割法/0.618法/Golden Section Search/Golden Ratio Search 表达的都是同一个东西,它是一种精确的一维搜索(line search)算法。黄金比例搜索算法只需要计算目标函数值,而无需计算导数之类的值,因此用起来非常容易,应用广泛。
这里要瞎扯一下:我们都知道黄金比例是0.618,但是你可能没注意到黄金比例还有一些神奇的特性,例如1÷0.618=1+0.618。在建筑学中,也经常使用黄金比例来达到美学效果,例如,代表了全希腊建筑艺术的最高水平的帕特农神庙的立面高与宽的比例为19比31,接近黄金比例。

要使用黄金比例搜索算法,函数 f(x) 需要在某一区间内满足单峰unimodal)条件。那么什么是单峰呢?看这里

文章来源:http://www.codelast.com/

在这种情况下,就具备使用该算法的条件了。

有人说,我想用golden section search,但是我怎么能保证在我的搜索区间之内函数是单峰的呢?这就涉及到另一种技术了——划界。试想一下,类似于f(x)=sinx这样的函数图形,在一个区间之内可能有多个波峰波谷,你如何能确定它在一个区间内的极值呢?靠的就是划界。但是,这不在本文的讨论范围内,我们假设你的搜索区间已经使得目标函数在其上是单峰的了。

怎么那么麻烦呢?每次只要一涉及到一个算法,就会用到另一个算法/技术,没办法,数学就是这样层层相套。像最优化中的“单纯形法”那样对其他算法依赖很少的算法,应该算比较少的吧(相比之下,Powell算法真是个麻烦的角色)。

若已知f(x)在[a,b]上单峰,则可用一个含有f(x)最小值的子区间来代替区间I。有一个方法是:选取两个内点c,d(其中c<d),即有a<c<d<b。f(x)的单峰保证了f(c) < max {f(a), f(b)} 且 f(d) < max {f(a), f(b)}。

 

这里又提到了另一个概念:内点。什么是内点呢?

<定义>数学上,集合 S 的内部(又称开核)含有所有直观上“不在 S 的边界上”的 S 的点。S 的内部中的点称为 S 的内点。

文章来源:http://www.codelast.com/

现在有两种情况需要考虑:

(1) f(c) \le f(d) ,则极小值出现在子区间 [a,d] 中,所以我们用d代替b,继续在子区间 [a,d] 中搜索;

(2) f(d) < f(c) ,则极小值出现在子区间 [c,b] 中,所以我们用c代替a,继续在子区间 [a,c] 中搜索。

这里要注意了:我们选取的两个内点不是随意选定的,而是特殊选定的,我们人为地使[a, c]与[d, b]对称,即b-d = c-a,从而:

(3)c=a+(1-r)(b-a)=ra+(1-r)b

(4)d=b-(1-r)(b-a)=(1-r)a+rb

此处r∈(0.5, 1)可以保证c < d

其中,r是未知的,我们要求出来。

我们想让r值在每一个子区间内均保持不变,另外,在每一次搜索的过程中,其中一个旧的内点将被用作新的子区间的一个内点,而一个旧的内点则会成为新的子区间的一个端点。这样,每一次迭代过程中只需要找到一个新点,并且只需要计算一次新函数值。如果f(c) <= f(d)且只需计算一次新函数值的话,那么我们就有:

也可以写成:

文章来源:http://www.codelast.com/

将(3)、(4)式代入此式,得:

由于r∈(0.5, 1),故:

此r值即所谓的黄金比例。平常我们老是说“黄金分割点”,就是这个0.618了。

同理,当 f(d) < f(c) 时,也可求得同样的 r 值。

文章来源:http://www.codelast.com/
下面我用一幅图,从另一个角度来说明黄金比例搜索算法的寻优过程。

上图来自Wiki
{x_1},{x_2},{x_3} 是已知的三个点(函数值“高→低→高”),它们划界了一个单峰区间,函数值分别为 {f_1},{f_2},{f_3} 。现在的问题是:如何通过一个新点 {x_4} ,不断缩小该区间的范围,从而逼近极小值点?

首先,在最大的区间 ({x_2},{x_3}) 内安插 {x_4} 是最高效的,因为我们更倾向于相信极小值更有可能出现在大的区间内。
{x_4} 的函数值为图中 {f_{4a}} 所示时(即 {f_{4a}} /> {f_2} ),此时,区间缩小为 {x_1},{x_2},{x_4} (函数值“高→低→高”的3个点);当 {x_4} 的函数值为图中 {f_{4b}} 所示时(即 {f_{4b}} < {f_2} ),此时,区间缩小为 {x_2},{x_4},{x_3} (函数值“高→低→高”的3个点),每次迭代均按此规则进行选取。
文章来源:http://www.codelast.com/
其次, {x_4} 应该放在什么位置上呢?随意放置的话,若运气不好,有可能会导致收敛很慢。而事实证明,黄金比例是极好的,即 \frac{c}{b} = 1 - 0.618
黄金比例搜索算法是线性收敛的,那么其收敛准则是什么呢?也就是说,我们逐步逼近了极小值所在的区间,到什么程度的时候,我们就可以“收手”,不用再搜索下去了呢?各种参考资料上给出了不同的收敛准则,例如:
|{x_3} - {x_1}| < \tau \cdot |{x_2}| + |{x_4}|
或:
|{x_3} - {x_1}| < \tau \cdot INITINIT 为初始区间长度)
文章来源:http://www.codelast.com/
需要一提的是,在给定一个精度 \delta 的情况下,我们可以计算出试验的次数(即需要多少次能找到极小值点)为:
n \ge \frac{{\lg \delta }}{{\lg 0.618}} + 1 取整数。
例如:求函数 f(x) = x2 - x + 2[ - 1,3] 上的极小值点,精度要求 \delta = 0.08 (即搜索区间缩小为初始区间长的8%时停止搜索,就认为找到了极小值)。
则:估计试验次数 n \ge \frac{{\lg 0.08}}{{\lg 0.618}} + 1 = 6.24 ,实际实验次数 n = 7 (按第二个收敛准则)。
文章来源:http://www.codelast.com/
最后来看一下简单的黄金比例搜索算法代码(我根据Wiki中的代码修改的,更易于理解):

public static double PHI = (1 + Math.sqrt(5)) / 2;    // 0.618...
Read More

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

转载请注明出处:http://www.codelast.com/
 

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

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

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

 

Read More

[原创]VC中实现最小二乘法 直线拟合 Y=a0+a1X 以及 Y=aX

转载需注明出处:文章来源:http://www.codelast.com/
 
用最小二乘法做直线拟合真的是非常简单,我随便写了一下并经过测试,需要使用的朋友随便改几个地方(例如变量名等)就可以用在自己的应用程序中了。在这里给出拟合直线Y=a0+a1X 以及Y=aX的例子。
Read More