在最少的计算次数中查找全局最大值

假设我在间隔[0,1]上定义了一个函数f，该函数是平滑的，并且在某些点开始减少之后增加到某个点a。我在此间隔上有一个网格x[i]，例如与步长为dx = 0.01，我想通过在最坏的情况下做最小数量的评估f，我想找到哪些点具有最高的价值。我认为我可以做得比穷举搜索更好，应用渐变式方法启发灵感。有任何想法吗？我正在考虑像二元搜索或抛物线方法。在最少的计算次数中查找全局最大值

这是一个二分样法我编码：

def optimize(f, a, b, fa, fb, dx): 
    if b - a <= dx: 
     return a if fa > fb else b 
    else: 
     m1 = 0.5*(a + b) 
     m1 = _round(m1, a, dx) 
     fm1 = fa if m1 == a else f(m1) 
     m2 = m1 + dx 
     fm2 = fb if m2 == b else f(m2) 
     if fm2 >= fm1: 
      return optimize(f, m2, b, fm2, fb, dx) 
     else: 
      return optimize(f, a, m1, fa, fm1, dx) 

def _round(x, a, dx, right = False): 
    return a + dx*(floor((x - a)/dx) + right)

的理念是：找到区间的中间，计算m1和m2 - 点到右侧和它的左侧。如果方向正在增加，请按照正确的时间间隔进行操作，否则继续向左。每当间隔太小时，只需比较两端的数字。然而，这个算法仍然不使用我计算的点处的导数的强度。

来源

2016-04-14 Ilya

你可能想看看nelder蜂蜜酒或模拟退火 – iedoc

@iedoc：不，这将是一个可怕的矫枉过正，因为这个函数被认为是单峰的。 –

有多少个网格点？ –

免责声明：未测试代码。以此为“灵感”。

比方说，你有以下11点

x,f(x) = (0,3),(1,7),(2,9),(3,11),(4,13),(5,14),(6,16),(7,5),(8,3)(9,1)(1,-1)

从这里你可以做这样的事情的启发，以二分法

a = 0 ,f(a) = 3 | b=10,f(b)=-1 | c=(0+10/2) f(5)=14

你可以看到，越来越多区间为[A，C [并且没有必要这么做，因为我们知道在那个区间内功能在增加。最大值必须在区间[c，b]中。因此，在下一次迭代中，您将更改s.t.的值。一个= C

a = 5 ,f(a) = 14 | b=10,f(b)=-1 | c=(5+10/2) f(6)=16

再次[a,c]增加使a移动右边

你可以重复这个过程，直到a=b=c。

这里实现这个想法的代码。更多信息here：

int main(){ 
#define STEP (0.01) 
#define SIZE (1/STEP) 
    double vals[(int)SIZE]; 
    for (int i = 0; i < SIZE; ++i) { 
     double x = i*STEP; 
     vals[i] = -(x*x*x*x - (0.6)*(x*x)); 
    } 
    for (int i = 0; i < SIZE; ++i) { 
     printf("%f ",vals[i]); 
    } 
    printf("\n"); 

    int a=0,b=SIZE-1,c; 
    double fa=vals[a],fb=vals[b] ,fc; 
    c=(a+b)/2; 
    fc = vals[c]; 

    while(a!=b && b!=c && a!=c){ 

     printf("%i %i %i - %f %f %f\n",a,c,b, vals[a], vals[c],vals[b]); 


     if(fc - vals[c-1] > 0){ //is the function increasing in [a,c] 
      a = c; 
     }else{ 
      b=c; 
     } 
     c=(a+b)/2; 
     fa=vals[a]; 
     fb=vals[b]; 
     fc = vals[c]; 
    } 
    printf("The maximum is %i=%f with %f\n", c,(c*STEP),vals[a]); 


}

来源

2016-04-14 11:55:03

关于增加间隔：如果f（c）> f（a）'，最大值仍可能位于它们之间。 – Ilya

@伊利亚是的，修好了。您应该只能找到哪个区间正在增加或减少。现在应该工作。 –

我不知道我可以按照你的算法，当然你在描述*中仍然存在这个问题*从这里你可以看到增加的区间是[a，c [并且没有必要那么做，因为我们知道在那段时间内，功能正在增加* – Ilya

找点哪里衍生物（F（x）的）=（DF/DX）= 0

衍生，你可以使用五点模板或类似算法。
- 应为O（n）
然后符合这些多个点（其中，d = 0）上的多项式回归/最小二乘回归。
- 应该也是O（N）。假设所有的数字都是邻居。
然后找到曲线
- 的顶部不得超过O（M），其中M是合适的，功能试验的分辨率也比较多。

同时采取衍生物，可以由k-长度步骤飞跃直到衍生物改变符号。

当微分改变符号时，取k的平方根并继续反向。

当再次导数变化时，再次取新k的平方根，改变方向。

示例：跳过100个元素，找到符号更改，跳跃= 10，反向，下一次更改==>跳跃= 3 ...然后它可以固定为每步1个元素以查找确切位置。

来源

2016-04-14 14:14:04

这样的函数被称为单峰。

在不计算所述衍生物，可以通过

工作发现其中增量X [I + 1] -x [I]改变符号，通过二分法（三角洲是正则最大后负）;这需要Log2（n）比较;这种方法与你所描述的非常接近;
将Golden section方法适用于离散情况;它需要Logφ（n）比较（φ〜1.618）。

显然，金部分是更昂贵的，因为φ< 2，但实际上二分搜索需要两个函数求值的时间，因此2Log2（N）=Log√2（N）。

可以证明这是最优的，即对于任意的单峰函数，你不能比O（Log（n））快。

如果你的函数非常规则，那么delta值将会平滑变化。你可以想到interpolation search，它试图通过线性插值来更好地预测搜索到的位置，而不是简单的减半。在有利条件下，它可以达到O（Log（Log（n））的性能。我不知道这个原理是否适用于Golden搜索。

实际上，deltas上的线性插值非常接近抛物线在函数值插值。后一种方法可能是最适合你的，但你必须要小心的极端案例。

如果衍生品是允许的，你可以使用任何root solving方法上的一阶导数，知道在给定的时间间隔内有一个孤立的零点

如果只有一阶导数是可用，使用regula falsi。如果二阶导数也是可能的，你可以考虑牛顿，但更喜欢安全的包围方法。

我想这些方法的好处（超线性和二次收敛）由于您正在使用网格而变得无用。

来源

2016-04-14 19:07:28

我假设功能评估是非常昂贵的。

在特殊情况下，您的函数可以近似拟合一个多项式，您可以轻松计算功能评估最少数量的极值。而且由于您知道只有一个最大值，因此2（二次）的多项式可能是理想的。

例如：如果f(x)可以通过一些已知的多项式表示，说2，那么，你可以在任何3点评估您的功能和使用牛顿差或拉格朗日插值法计算多项式系数。

然后它简单地求解这个多项式的最大值。对于程度2，您可以轻松获得最大封闭表单表达式。

为了得到最终答案，您可以在解决方案的附近进行搜索。

来源

2016-04-14 22:51:57

在最少的计算次数中查找全局最大值

回答

相关问题