寻找函数最小值点的算法

Question

我希望找到一个具有最小试验次数的函数最小值。 函数 f(x) 必须具有最小值点。 给定输入 x，我可以计算 f(x)，但不能反向计算。 因此，它是一个黑匣子。

我想找到使 f(x) 最小化的输入 x，并使用最少的试验次数（一次试验是当我选择特定的 x 并将其插入以获得输出时）。 有没有算法可以实现这个目标？

结果不需要是绝对最小值，因为它来自于实际问题。 但它应该比大多数值都要小。

如果将函数限制为凸函数，是否有更好的方法实现这一点？

谢谢！

- Jarvis Du

---

函数的定义域是什么？ - kraskevich

你是否正在学习机器学习或凸优化相关的课程？如果没有，我敢打赌你一定想要学习。 - Jason Hu

@TimothyShields 这是一个很好的参考！ - Jarvis Du

对于具有无限定义域的任意函数，这将非常困难，除非您了解连续性或者（如果存在）导数等相关知识。 - G. Bach

这应该可以解决你的问题：http://en.wikipedia.org/wiki/Golden_section_search - Nayuki

Answer 1

假设该函数是凸函数且f(x)的导数在所有点上都存在，则只有一个最小值。我强调导数的限制是因为当函数在交点处看起来像两个相邻的凸函数时，导数不存在，但函数仍然是凸函数，并且有两个局部最小值。

导数在最小值左右具有相反的符号（斜率改变方向）。您可以在此处here看到这种情况的可视化效果。考虑到这一点，您可以在定义域上进行简单的二分查找，以找到满足f'(k-e) * f'(k+e) < 0的点k。选择e越小，结果的精度就越好。在进行搜索时，让[a,b]成为区间，k=(a+b)/2，如果f'(k)*f'(a) < 0，则选择左侧，否则选择右侧。

有一个函数f(x)，其导数为f'(x) = (f(x+e)-f(x))/e，你选择的e值越小，导数的精度就越高。

- Alexandru Barbarosie

Answer 2

如果函数是随机的，我认为找到最小值没有快速的方法，因为如果f(x)可以是任何东西（黑盒），则不能保证该函数是连续函数。

如果函数是凸函数，则可以用抛物线来近似。

如果函数实际上是抛物线状的，你可以选取6个随机点并计算它们的值。每个抛物线都可以由6个点表示，因此可以计算出它的函数，然后通过导数计算它的最小值。这仅是近似，但是您可以事先准备好导数函数（作为6个变量的函数），因此只需要7个步骤即可计算它（取决于f(x)有多复杂），但我认为这是其中最快的方法之一。但再次强调，这仅是最小值的良好猜测。

- Marko Zadravec

---

给定一个二元多项式 f(x,y)，5个点可以唯一确定一个圆锥曲线（其中抛物线是一个子集）。但问题说明我们只处理一个变量的函数 f(x)，因此我们只需要3个点来唯一确定它的方程。 - Synergist

他没有说那是一个抛物线。实际上，他甚至没有说它是凸的。他只是问了这个问题，并另外询问了凸性的作用。 - Davis Yoshida

#Davis Yoshida，每个凸函数都可以用抛物线来近似。我特别指出这只是猜测或近似（因为他指出最小值不需要精确）。我认为这个答案不应该被投-1票。 - Marko Zadravec