时间戳

首页 > 解决方案 > 求区间内未知函数的最大值

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

问题描述

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

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

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

标签： javascriptalgorithmfunctionoptimizationmax

解决方案

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

端点 (a, f(a)) 和 (b, f(b)) 将 y 轴分为三个区域，水平边界位于 f(a) 和 f(b)。wlog 我将讨论限制在第一象限，假设 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]，我们还需要两个点。

选择点的简单方法是简单地平分或三等分有问题的区间。如果您想尝试更高级的东西，请使用您的点历史来近似函数（例如样条拟合）并选择点以便更快地收敛。

这能让你前进吗？

推荐阅读