javascript - 找出区间内未知函数的最大值

Question

给定一个连续但未知的函数 f(x)，我如何通过多次调用 f(x) 找到它在闭区间内达到的最大值尽可能？

这个函数是未知的，所以我不能明确地求导。检查值的唯一方法是调用它。 f(x)在给定区间内只有一个临界点，但最大值可以在端点。

我不需要超高精度。比方说，如果该方法超过一定的迭代次数，它将停止并返回当前的最大值。

Answer 1

这是一个分而治之的过程。

端点 (a, f(a)) 和 (b, f(b)) 将 y 轴分为三个区域，水平边界位于 f(a) 和 f(b)。 w.l.o.g.我将讨论限制在第一象限，假设 f(b) > f(a)

     |
     |
f(b)-+-------------------------*-----------
     |
     |
     |
     |
f(a)-+-*-----------------------------------
     |
     |
     +-a-------r--------s------b-----

取另外两个值，'r' 和 's' 使得 a < r < s < b .由于拐点不超过一个，因此对端点排序的f(r)和f(s)的各种可能性有一些限制。

如果两者都小于f(b)，那么最大点一定在s的右边, 区间 [s, b].

如果 f(r) 高，则 f(s) 也高。
f(r) > f(s) > f(b) 意味着最大值在区间 [a, s]
f(s) > f(r) > f(b) 意味着最大值在区间 [r, b]

剩下的情况是 f(a) < f(r) < f(b) 和 f(s) > f(b)。同样，我们得到最大值必须在 f(r) 的右侧，即前一种情况中的第二个点，区间 [r, b]。

做出这个决定后，迭代剩余的时间间隔。对于 [a, s] 或 [r, b]，我们已经在区间中有一个点；在较大的一侧再选择一个(如果两个大小相同，则选择其中一个)；对于 [s, b]，我们还需要两个点。

选择点的简单方法是简单地二等分或三等分所讨论的区间。如果您想尝试一些更奇特的东西，请使用您的点历史来近似函数(例如样条拟合)并选择点以便更快地收敛。

这会让你前进吗？