以特定分辨率查找连续函数的最大值

想象一下，函数在[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; 
}

来源

2013-10-03 Moop

若f（x）是连续的，最大值（也是最小值）出现在d/dx f（x）= 0处。虽然没有关于函数程度的信息并且仅通过调用它来评估函数，但这可能是唯一的方法。此外，随着您增加步数，除非对域值（即x的可能值）有其他已知限制，否则您可能会有更“接近最大值”的值。 –

如果你想看'd/dx f（x）'，你需要'f'来区分。有许多功能是连续的但不可区分的。 – Teepeemm

如果你知道一些关于连续“f”是什么的话，那可能会有所帮助。例如，如果'| f（x + s）-f（x）|'有界，那么当'f'远离它的最大值时，可以采取更大的步骤。 – Teepeemm

鉴于你正在讨论的函数是代码，那么不，该函数可以在任何点返回任意的最大值。

如果您可以对功能进行假设（如最大变化率），那么您可以优化。

来源

2013-10-03 03:03:40

假设有这样一种算法，也就是说，一种算法可以在不查看每个近似点的情况下找到连续函数的近似值的最大值。

现在选择一个正整数n，然后选择任意n个双打的有限序列。有无穷多个连续函数，使得f（n）等于序列中的第n个二元组，并且小于或等于其中最大的那个。选择其中之一。

现在使用你的算法找到n个双打的最大双倍。通过假设，它检查少于n个双打。我们假设它检查除第k个双数之外的所有数据。

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

现在很清楚为什么没有这样的算法？如果你想在抽屉里找到最长的字符串，你将不得不看看所有的字符串。

该功能的连续性根本无法帮到你。所有连续性给你一个保证，给定一个函数的一个点，你可以找到另一个函数的点，如你所愿接近第一个点。这不会告诉你关于该函数的最大值的信息。（嗯，好吧，它会告诉你东西。在一个封闭的有界区间则意味着最大的存在，这是一件好事，但它并不能帮助你找到它。）

来源

2013-10-03 06:28:33

我认为你的反例是有点不真诚的：改变第k个double会改变函数的“形状”，因此在理论上可能是一个算法，它会首先消除由于特定的局部边界条件导致的第k个值，如果第k个值是局部或全局最大值，则满足。 – InBetween

@InBetween：我不喜欢被称为不诚实，特别是在公共场合。我既不诚实地回答这个问题，也不试图假装我比我更了解微积分。当我们将最好的意图归于其他人时，我们都会在本网站上做得更好。 –

@InBetween：为了解决您的具体问题：除了在k-0.00000001和k + 0.0000001之间的所有点上取一个等于f（x）的新函数g（x），并在这些点之间选择一个连续函数。 –

以特定分辨率查找连续函数的最大值

回答

相关问题