Eine unbekannte Funktion optimieren, die nur ausgewertet werden kann?

Bei einer unbekannten Funktion können wir ihren Wert an jedem Punkt in ihrer Domäne bewerten, aber wir haben keinen Ausdruck. Mit anderen Worten, f ist für uns wie eine Black Box.$f:\mathbb R^d \to \mathbb R$$f$

Wie heißt das Problem, den Minimierer von ? Welche Methoden gibt es da draußen?$f$

Wie heißt das Problem, die Lösung für die Gleichung ? Welche Methoden gibt es da draußen?$f(x)=0$

In den obigen zwei Problemen ist es eine gute Idee, einige Auswertungen von f zu interpolieren oder anzupassen: Verwendung einer Funktion g θ mit bekannter Form und bekanntem Parameter θ bestimmt werden und dann g θ minimieren oder seine Wurzel finden?$(x_i, f(x_i)), i=1, \dots, n$$g_\theta$$\theta$$g_\theta$

Danke und Grüße!

Die Methoden, nach denen Sie suchen, dh die nur Funktionsbewertungen, aber keine Ableitungen verwenden, werden als derivatfreie Optimierungsmethoden bezeichnet . Es gibt eine große Menge an Literatur darüber, und ein Kapitel über solche Methoden finden Sie in den meisten Büchern zur Optimierung. Typische Ansätze sind

• Annäherung des Gradienten durch endliche Differenzen, wenn vernünftigerweise erwartet werden kann, dass die Funktion glatt und möglicherweise konvex ist;
• Monte-Carlo-Methoden wie simuliertes Tempern;
• Genetische Algorythmen.

Ich denke, Sie sollten beginnen mit: GECCO-Workshop zum Real-Parameter-Black-Box-Optimierungs-Benchmarking (BBOB 2016) http://numbbo.github.io/workshops/index.html

Sie werden viele verschiedene Algorithmen finden, die in früheren Wettbewerben verwendet wurden und die auf einer gemeinsamen Basis verglichen wurden. Wenn Sie anderswo anfangen, werden Sie bald in den Hunderten von Artikeln ertrinken, in denen behauptet wird, dass ihre Methoden und Algorithmen eine bessere Leistung erbringen als andere, ohne dass tatsächlich Beweise für diese Behauptungen vorliegen.

Bis vor kurzem war es, um ehrlich zu sein, ein schändlicher Zustand und jede Macht für INRIA, GECCO und viele andere für die Bemühungen, die sie unternommen haben, um einen Rahmen für rationale Vergleiche zu schaffen.

Ich möchte nur hinzufügen, dass einer der Schlüssel hier darin besteht, die Optimierungsmethode auf Multicore-CPUs zu skalieren . Wenn Sie mehrere Funktionsauswertungen gleichzeitig durchführen können, erhalten Sie eine Beschleunigung, die einer Anzahl der beteiligten Kerne entspricht. Vergleichen Sie dies mit der Verwendung eines etwas genaueren Antwortmodells, wodurch Sie etwa 10% effizienter sind.

Ich würde empfehlen, sich diesen Code anzusehen . Er kann für Benutzer nützlich sein, die Zugriff auf viele Kerne haben. Eine Mathematik dahinter ist in diesem beschriebenen Papier .