单变量多峰无导数优化(对于表现良好的函数)

计算科学 优化 算法 遗传算法
2021-12-02 18:29:50

是否有成熟的单变量多模式优化方法?

给定f:RR那:

  • 在给定的兴趣范围内有几个局部最小值[a,b]
  • 在局部最小值附近是二次的

此外,鉴于:

  • f评估成本高昂
  • f不可用

你能推荐一种有效地找到局部最小值的算法吗?

我模糊地想象从均匀间隔的样本开始[a,b],然后细分有希望的区间,并最终(突然或逐渐)变形为一个适合小邻域的抛物线以收敛于局部最小值的过程。

1个回答

要找到区间中的最小值,可以使用黄金分割搜索基本上,这是一个迭代过程,您将每个区间分为 3 个部分,并根据边界处的函数值丢弃左侧或右侧部分。


但是,由于您有多个最小值,您可以拆分间隔[a;b]进入n几个较小的间隔[cj;cj+1], 和a=c0<c1<<cn1<cn=b这样您在每个间隔中最多只能有一个最小值(尽管在一个间隔中您可能有零最小值)。

另一种方法是找到最小值m1在区间[a;b]. 然后,我们将初始区间分成两个区间[a;m1)(m1;b],并在两者中搜索一个最小值(一次一个)。您找到的每个最小值都会将相应的区间分成两个较小的区间来搜索最小值。如果你没有找到区间中的最小值(mj;mk)您可以将其分成两半并重复搜索。如果发生以下情况之一,您可以停止迭代过程,从而拆分每个区间:(1)找到所有最小值(如果您知道存在多少);(2)区间幅度小于预定值。


编辑: 您也可以交替搜索局部最小值和局部最大值,因为在两个最大值之间至少有一个最小值(反之亦然)。