优化弱单峰连续函数的分治法?

计算科学 优化
2021-12-24 21:34:24

是否有用于优化弱单峰连续函数的分而治之算法?

添加更多细节:

我的函数在左右两边都有一条平线,然后在两者之间有一个全局最小值,但是这个全局最小值在看起来像一条直线上重复了一段时间。在极小值的左侧和左侧平线的右侧,行为是单调递减的。在最小值的右侧和右侧平线的左侧,行为是单调递增的。此外,该函数是一个正函数,它的范围始终> 0。此外,该函数仅在零以上定义。即,它的域总是> 0。

我认为主要问题是最初的三分括号可能并不理想。如果初始括号是理想的,那么黄金分割搜索会收敛到最优解吗?还是问题更大——即使最初的括号是理想的?

1个回答

不,那里没有。

问题是您的弱单峰函数可能是恒定的,除了一个非常小的“凸起”。除非运气好,否则任何计算函数有限次的算法都无法将这样的函数与常量函数区分开来。

假设你有这样一个算法并在一个恒定的测试函数上运行它f(x)=c为此它停止了k函数评估(所有这些都具有相同的值。)接下来在函数上运行它g在每一个都具有相同的常数值k点,但也有一个隐藏的凹凸,不会击中任何这些点。您的算法将在相同之后停止k结果不正确的迭代。

用于非凸函数全局最小化的分治算法需要函数的附加属性(例如 Lipschitz 连续性)才能处理此问题。