首页 > 代码库 > 数值算法:无约束优化之一维搜索方法之划界法寻找极小点上下界

数值算法:无约束优化之一维搜索方法之划界法寻找极小点上下界

前面介绍的黄金分割法、斐波那契数列法、二分法、牛顿法、割线法寻找极小点方法的前提是: 给定初始区间,它包含一个单峰的f(x)。

如何寻找这个初始区间?

划界法:(挑选一个含有极小点的区间)

      随机挑选3个点x1、x2、x3, 如果 f(x2)<f(x1) 且 f(x2)<f(x3) ,那么 [x1, x3]包含极小点。如果f(x1)>f(x2)>f(x3),那么选择一个点x4,x4>x3, 使得 f(x2) <f(x4)成立,这样[x1, x4]包含极小点。如果f(x1)<f(x2)<f(x3),那么选择一个点x0,x0<x1, 使得 f(x1) <f(x0)成立,这样[x0, x3]包含极小点。通常情况下,新点的选择应该保证与前一个相邻点的距离超过其前两个点之间的距离,可以取倍增间距。

这种方法得到的区间不一定是单峰区间,还需要对区间多次细分、测试。

 

[测试数据]:fx.dat  intervals.dat

[算法代码]:test.cpp  partion.a  partion.so

数值算法:无约束优化之一维搜索方法之划界法寻找极小点上下界