計算の最大数でグローバルな最大値を見つけよう

Question

[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を計算

この

は私がコード化された二分のような方法です。その方向が増加している場合は、適切な間隔で移動して同じ操作を行い、そうでない場合は左に移動します。間隔が小さすぎる場合は、両端の数字を比較するだけです。しかし、このアルゴリズムは計算したポイントで微分の強さを使用しません。

Answer 1

免責事項：コードをテストしていない。これを「インスピレーション」と呼んでください。

、C [あなたは、あなたが増加間隔があることがわかります、ここから二分法

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

にインスピレーションを得たような何かを行うことができ、以下の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) 

を持っているとしましょう[そして、その間隔で機能が増えていることがわかっているので、最大限の必要はありません。最大値は区間[c、b]でなければなりません。ですから、次の反復ではstの値を変更します。 = 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]); 


} 

Answer 2

は、派生物の誘導体（F（x）の）=（DF/DX）= 0

• あなたは5点、ステンシルまたは類似のアルゴリズムを使用することができますポイントを探します。
  • はO（N）
• は次に多項式回帰/最小二乗回帰にそれら複数の点（ここで、d = 0）を取り付けなければなりません。
  • もO（N）でなければなりません。すべての数字が隣人であると仮定します。
• そしてその曲線の上部
  • Mが嵌合機能の試験の解像度はO（M）以上であるべきではない見つけます。

微分を取っている間誘導体が符号を変更するまで、あなたはK-長段階で飛躍できました。

派生記号が変更された場合は、kの平方根をとり、逆方向に進みます。

また、派生物は記号を変更し、新しいkの平方根を再度取って方向を変えます。

例：100個の要素で飛び越えて、符号の変化を見つけ、飛躍= 10、逆方向、次の変更==>飛躍= 3 ...正確な位置を見つけるためにステップごとに1要素に固定することができます。

Answer 3

このような機能をユニモーダルと呼びます。

誘導体を計算することなく、あなたはデルタX [I + 1] -x見つける

• によって働くことができるが[i]が変化記号は、二分法により（デルタ最大後陰性、陽性であります）;これにはLog2（n）の比較が必要です。このアプローチは、あなたが説明するものに非常に近いです。

• Golden sectionの方法を離散の場合に適合させる。 Logφ（n）の比較（φ〜1.618）が必要です。

は明らかに、黄金分割は< 2φとして、より高価であるが、実際には二分探索が2Log2（N）=Log√2（N）したがって、一度に2つの関数評価をとります。

これは最適であることを示すことができます。すなわち、任意の単峰性関数に対してO（Log（n））より速く進むことはできません。

---

機能が非常に規則的である場合、デルタはスムーズに変化します。 interpolation searchは、検索された位置を単純な半分ではなく線形補間によってよりよく予測しようとします。

実際、デルタでの線形補間は、放物線に非常に近いです（図2）。関数の値の補間。後者の方法は、あなたのための最良のかもしれませんが、あなたはコーナーケースに注意する必要があります。

---

誘導体が許可されている場合は、一次導関数に任意のroot solving方法を使用することができ、与えられた時間間隔に孤立したゼロがあることを知る。

1次導関数が使用可能な場合は、regula falsiを使用してください。二次微分も可能であれば、ニュートンと考えるかもしれませんが、安全なブラケット法が好まれます。

グリッド上で作業していることから、これらのアプローチ（スーパーリニアおよび2次コンバージェンス）の利点はほとんど役に立たないと思います。

Answer 4

私は関数評価が非常にコストがかかると仮定しています。

特別なケースでは、関数が近似的に多項式に適合することができるので、少なくとも関数評価の極値を簡単に計算できます。最大値が1つしかないことを知っているので、次の度数の多項式2（二次式）が理想的かもしれません。例えば

：f(x)は、いくつかの既知の多項式で表すことができる場合は、2を言って、それから、あなたはどの3ポイントであなたの機能を評価し、ニュートンの違いやラグランジュ補間法を用いた多項式の係数を計算することができます。

次に、この多項式の最大値を解くのは簡単です。度合いが2の場合、最大の閉じたフォーム式を簡単に取得できます。

最後の回答を得るには、ソリューションの近くで検索してください。