Finde das globale Maximum in der letzten Anzahl der Berechnungen

Question

Nehmen wir an, ich habe eine Funktion f definiert im Intervall [0,1], die glatt ist und bis zu einem gewissen Punkt a ansteigt, nach dem es anfängt zu sinken. Ich habe ein Gitter x[i] in diesem Intervall, z.B. mit einer konstanten Schrittgröße von dx = 0.01, und ich würde gerne herausfinden, welcher dieser Punkte den höchsten Wert hat, indem ich im Worst-Case-Szenario die kleinste Anzahl von Bewertungen von f mache. Ich denke, dass ich viel besser als eine erschöpfende Suche tun kann, indem ich etwas anwende, das mit gradientenartigen Methoden inspiriert ist. Irgendwelche Ideen? Ich dachte an etwas wie eine binäre Suche vielleicht oder parabolische Methoden.

Dies ist eine Halbierungsartige Methode I codiert:

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) 

Die Idee ist: Finden Sie die Mitte des Intervalls und berechnen m1 und m2 - die Punkte nach rechts und links von ihm. Wenn die Richtung dort zunimmt, gehen Sie für das rechte Intervall und machen Sie dasselbe, andernfalls gehen Sie nach links. Wenn das Intervall zu klein ist, vergleichen Sie einfach die Zahlen an den Enden. Dieser Algorithmus verwendet jedoch immer noch nicht die Stärke der Ableitungen an den von mir berechneten Punkten.

Answer 1

HAFTUNGSAUSSCHLUSS: Habe den Code nicht getestet. Nimm das als "Inspiration".

Angenommen, Sie haben die folgenden 11 Punkte

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) 

Sie so etwas wie inspiriert zum Bisektionsmethode tun können

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

von hier kann man sehen, dass die zunehmende Intervall [a, c [und es gibt keine Notwendigkeit für das Maximum, weil wir wissen, dass in diesem Intervall die Funktion zunimmt. Das Maximum muss im Intervall [c, b] liegen. So ändern Sie bei der nächsten Iteration den Wert eines s. a = c

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

Wieder [a,c] Erhöhung ist so a auf der rechten

bewegt Sie den Vorgang, bis a=b=c laufen kann.

Hier der Code, der diese Idee implementiert. Mehr Informationen 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

Punkte, wo Derivat (von f (x)) = (df/dx) = 0

• für derivative Sie Fünf-Punkte-Schablone oder ähnliche Algorithmen nutzen könnten.
  • sollte O (n) sein
• Dann diese mehreren Punkten passen (wobei d = 0) auf einer polynomialen Regression/Regression der kleinsten Quadrate.
  • sollte auch O (N) sein. Angenommen, alle Zahlen sind Nachbarn.
• Dann finden Sie oben auf dieser Kurve
  • sollte nicht mehr als O (M), wobei M Auflösung von Studien für Fit-Funktion ist.

Während Derivat nehmen, könnten Sie von k-Länge Schritten springen, bis derivate Vorzeichen ändert.

Wenn die Ableitung das Vorzeichen ändert, die Quadratwurzel von k nehmen und die umgekehrte Richtung fortsetzen.

Wenn wieder, Derivat ändert Zeichen, nehmen Sie die Quadratwurzel von neuen k wieder, ändern Sie die Richtung.

Beispiel: Sprung um 100 Elemente, Vorzeichenwechsel, Sprung = 10 und Rückwärtsrichtung, nächste Änderung ==> Sprung = 3 ... dann könnte es auf 1 Element pro Schritt fixiert werden, um den genauen Ort zu finden.

Answer 3

Eine solche Funktion heißt unimodal.

Ohne die Derivate Berechnung, können Sie arbeiten, indem sie

• zu finden, wo die Deltas x [i + 1] x [i] Vorzeichen ändern, durch Dichotomie (die Deltas positiv sind dann negativ nach dem Maximum); dies erfordert Log2 (n) -Vergleiche; Dieser Ansatz ist sehr nah an dem, was Sie beschreiben;

• Anpassung der Methode Golden section an den diskreten Fall; es dauert Logφ (n) Vergleiche (φ ~ 1,618).

Offensichtlich ist der goldene Schnitt teurer, als < φ 2, das aber eigentlich die dichotomischen Suche führt zu einem Zeitpunkt zwei Funktionsauswertungen, daher 2Log2 (n) = Log√2 (n).

Man kann zeigen, dass dies optimal ist, d.h. man kann nicht schneller als O (Log (n)) für eine beliebige unimodale Funktion gehen.

---

Wenn Ihre Funktion sehr regelmäßig ist, werden die Deltas reibungslos variieren. Sie können sich dievorstellen, die versucht, die gesuchte Position durch eine lineare Interpolation besser als durch einfache Halbierung vorherzusagen. Unter günstigen Bedingungen kann es O (Log (Log (n)) - Leistung erreichen. Ich kenne keine Anpassung dieses Prinzips an die Golden-Suche.

Tatsächlich ist die lineare Interpolation an den Deltas sehr nahe am Parabol Interpolation auf den Funktionswerten. der letztere Ansatz könnte die beste für Sie sein, aber Sie müssen über die Ecke Fällen vorsichtig sein.

---

Wenn Derivate erlaubt sind, können Sie eine beliebige root solving Verfahren auf dem ersten Derivat verwenden können, zu wissen, dass es in dem gegebenen Intervall eine isolierte Null gibt

Wenn nur die erste Ableitung ist verfügbar, verwenden Sie regula falsi. Wenn auch die zweite Ableitung möglich ist, können Sie Newton in Erwägung ziehen, bevorzugen aber eine sichere Belichtungsreihenmethode.

Ich vermute, dass die Vorteile dieser Ansätze (superlineare und quadratische Konvergenz) durch die Tatsache, dass Sie an einem Gitter arbeiten, ein wenig nutzlos gemacht werden.

Answer 4

Ich gehe davon aus, dass die Funktionsauswertung sehr aufwendig ist.

In dem speziellen Fall, dass Ihre Funktion näherungsweise mit einem Polynom versehen werden könnte, können Sie das Extrema mit der geringsten Anzahl von Funktionsbewertungen berechnen. Und da Sie wissen, dass es nur ein Maximum gibt, könnte ein Polynom vom Grad 2 (quadratisch) ideal sein.

Zum Beispiel: Wenn f(x) kann durch ein Polynom von einigen bekannten Grad dargestellt werden, sagen 2, dann können Sie Ihre Funktion an beliebigen 3 Punkte auszuwerten und die Polynomkoeffizienten mit Newtons Differenz oder Lagrange-Interpolationsverfahren berechnet werden.

Dann ist es einfach, für das Maximum für dieses Polynom zu lösen. Für einen Grad 2 können Sie leicht einen geschlossenen Ausdruck für das Maximum erhalten.

Um die endgültige Antwort zu erhalten, können Sie dann in der Nähe der Lösung suchen.