c# - 在特定分辨率下查找连续函数的最大值

Question

假设有一个函数在 [0.0,n] 范围内连续。在给定最小步长 s 的情况下，是否有任何算法可以比简单迭代更快地找到函数的最大值？简单的迭代很容易编程，但是当 n/s 很大时，时间复杂度会增加。

double maxValue = 0;
double maxValueX = 0;
double s = 0.1 * n;
for (double x = 0.0; x <= n; x += s)
{
     double value = someFunction(x);
     if(value > maxValue) {
         maxValue = value;
         maxValueX = x;
     }
} 

我已经尝试过这种方法，速度更快，但不知道它是否会卡在局部最大值上。

double min = 0;
double max = n;
int steps = 10;
increment = (max - min) / steps;
while (increment > s)
{
    double maxValue = 0;
    double maxValueX = X;
    for (double x= min; x <= max; x+= increment)
    {
         double value = someFunction(x);
         if(value > maxValue) {
             maxValue = value;
             maxValueX = x;
         }
    }
    min = Math.Max(maxValueX - increment, 0.0);
    max = Math.Min(maxValueX + increment, n);
    increment = (max - min) / steps;
}

Answer 1

假设有这样一种算法，即一种算法可以找到连续函数逼近的最大值，而无需查看逼近的每个点。

现在选择一个正整数 n 并选择您想要命名的 n 个 double 的任何有限序列。有无限多个连续函数使得 f(n) 等于序列中的第 n 个 double ，并且在所有地方都小于或等于其中的最大值。选择其中之一。

现在使用您的算法找到 n 个 double 中最大的 double 。根据假设，它检查了少于 n 个 double 。假设它检查了除第 k 个 double 之外的所有对象。

现在假设我们创建一个与第一个序列相同的新序列，只是第 k 个 double 值是最大值。该算法是不是很神奇，当给定一个输入它不读取时，它会改变它的输出？

现在清楚为什么没有这样的算法了吗？如果你想在抽屉里找到最长的一根绳子，你将不得不查看所有的绳子。

函数的连续性对你一点帮助都没有。所有连续性都为您提供了一种保证，即给定函数上的一个点，您可以在函数上找到与第一个点尽可能接近的另一个点。这并没有告诉你函数所取的最大值。 (嗯，好吧，它告诉你一些东西。在一个封闭的有界区间上它意味着存在一个最大值，这是一个东西。但它不能帮助你找到它。)