三点一维搜索策略

实验九、三点一维搜索策略

0.618方法在一元函数的最优化方法中占有重要的地位，它是在解的存在区间中插入两个分点进而对该区间三分，通过比较两个分点处的函数值大小来扔掉区间某侧的一段来提高解的精度——本实验试图构造某种类似的一维搜索策略，主要不同在于这里一次迭代要在解的存在区间中插入三个分点进而对该区间四分，最后考虑在包括原来区间的两个端点在内的五个点中选择相邻的三点，其函数值具有“高低高”结构且区间长度最短，将之保留。 算法：

步1：给定参数p?0.25，精度要求??0，取初始三点a?a0，b?b0，令A?f(a)，B?f(b)，X?f(x)；

步2：若b?a??，则输出a、A、b、B，停；

x?a?b2x?a?b2，

步3.1：若

，则令x2?x，x1?a?(1?p)?(x2?a)，，X1?f(x1)，X3?f(x3)；否则，转步4.1；

x3?x2?p?(b?x2)，X2?X步3.2：若X2?Min ?Xii?1,2,3?，则取a?x1、A?X1、b?x3、B?X3，转步2；

若X1?X2，则取b?x2、B?X2、x?x1、X?X1，转步2； 若X3?X2，则取a?x1、A?X1、x?x3、X?X3，转步2；

x2?a?b2步4.1：令

，x1?a?(1?p)?(x2?a)，x3?x2?p?(b?x2)，

X1?f(x1)，X2?f(x2)，X3?f(x3)；

Ui(i?1,2,3,4)步4.2：对xi(i?1,2,3)、x按照从小到大排序，记为ui(i?1,2,3,4)，

表示它们的目标函数值，U*?Min ?Uii?1,2,3,4?；

* 若U1?U，则取x?u1、X?U1、b?u2、B?U2，转步2；

若U2?U转步2；

若

U3?U*，则取a?u1、A?U1、x?u2、X?U2、b?u3、B?U3，

*，则取a?u2、A?U2、x?u3、X?U3、b?u4、B?U4，

转步2；

*若U4?U，则取a?u3、A?U3、x?u4、X?U4，转步2。

仔细研究以上算法与0.618法的区别与联系，可以以幂函数x?(??0)的最

小化问题作为测试算例，编程实现之，讨论算法的计算效率以及收敛性。你有不同的改进建议吗？