Warum werden Optimierungsalgorithmen im Hinblick auf andere Optimierungsprobleme definiert?

Ich forsche an Optimierungstechniken für maschinelles Lernen, bin jedoch überrascht, dass eine große Anzahl von Optimierungsalgorithmen im Hinblick auf andere Optimierungsprobleme definiert wurde. Ich illustriere im Folgenden einige Beispiele.

Zum Beispiel https://arxiv.org/pdf/1511.05133v1.pdf

Alles sieht schön und gut aus, aber dann gibt es dieses im . Was ist also der Algorithmus, der für das ? Wir wissen es nicht und es sagt es nicht. Also müssen wir auf magische Weise ein weiteres Optimierungsproblem lösen, nämlich den Minimierungsvektor so zu finden, dass das innere Produkt minimal ist - wie kann das geschehen?z k + $\text{argmin}_x$$z^{k+1}$$\text{argmin}$

Nehmen Sie ein anderes Beispiel: https://arxiv.org/pdf/1609.05713v1.pdf

Alles sieht schön und gut aus, bis Sie diesen proximalen Operator in der Mitte des Algorithmus treffen, und wie ist die Definition dieses Operators?

Boom:

Nun bitte sagen Sie, wie lösen wir dieses im proximalen Operator? Es sagt nicht. In jedem Fall sieht das Optimierungsproblem schwer aus (NP HARD), je nachdem, was ist.$\text{argmin}_x$$f$

Kann mich bitte jemand aufklären:

1. Warum sind so viele Optimierungsalgorithmen im Hinblick auf andere Optimierungsprobleme definiert?

(Wäre das nicht eine Art Henne-Ei-Problem: Um Problem 1 zu lösen, müssen Sie Problem 2 lösen, indem Sie die Methode zur Lösung von Problem 3 anwenden, die auf der Lösung des Problems beruht ...)

2. Wie lösen Sie diese Optimierungsprobleme, die in diese Algorithmen eingebettet sind? Zum Beispiel , wie finde den Minimierer auf der rechten Seite?$x^{k+1} = \text{argmin}_x \text{really complicated loss function}$

3. Letztendlich wundere ich mich, wie diese Algorithmen numerisch implementiert werden können. Ich erkenne, dass das Hinzufügen und Multiplizieren von Vektoren in Python einfach ist, aber was ist mit es eine Funktion (Skript), die Ihnen den Minimierer für eine Funktion auf magische Weise gibt?$\text{argmin}_x$

(Kopfgeld: Kann sich jemand auf ein Papier beziehen, für das die Autoren den Algorithmus für das in den Optimierungsalgorithmus auf hoher Ebene eingebettete Unterproblem klarstellen?)

Sie betrachten Algorithmus-Flussdiagramme der obersten Ebene. Einige der einzelnen Schritte im Flussdiagramm verdienen möglicherweise ihre eigenen detaillierten Flussdiagramme. In Veröffentlichungen mit Schwerpunkt auf Kürze werden jedoch oft viele Details ausgelassen. Details für Standard-Innenoptimierungsprobleme, die als "alter Hut" angesehen werden, werden möglicherweise überhaupt nicht bereitgestellt.

Die allgemeine Idee ist, dass Optimierungsalgorithmen die Lösung einer Reihe von allgemein einfacheren Optimierungsproblemen erfordern können. Es ist nicht ungewöhnlich, dass in einem Top-Level-Algorithmus drei oder sogar vier Stufen von Optimierungsalgorithmen enthalten sind, obwohl einige davon in Standardoptimierern enthalten sind.

Sogar die Entscheidung, wann ein Algorithmus beendet werden soll (auf einer der Hierarchieebenen), kann die Lösung eines Nebenoptimierungsproblems erforderlich machen. Zum Beispiel könnte ein nicht negativ eingeschränktes lineares Problem der kleinsten Quadrate gelöst werden, um die Lagrange-Multiplikatoren zu bestimmen, die zur Bewertung der KKT-Optimalitätsbewertung verwendet werden, um zu entscheiden, wann die Optimalität deklariert wird.

Wenn das Optimierungsproblem stochastisch oder dynamisch ist, gibt es möglicherweise noch weitere hierarchische Optimierungsebenen.

Hier ist ein Beispiel. Sequentielle Quadratische Programmierung (SQP). Ein anfängliches Optimierungsproblem wird durch iteratives Lösen der Karush-Kuhn-Tucker-Optimalitätsbedingungen behandelt, wobei von einem Anfangspunkt mit einem Ziel ausgegangen wird, das eine quadratische Approximation des Lagrange-Problems und eine Linearisierung der Beschränkungen ist. Das resultierende Quadratische Programm (QP) ist gelöst. Der QP, der gelöst wurde, weist entweder Vertrauensbereichsbeschränkungen auf, oder es wird eine Zeilensuche vom aktuellen Iterationsschritt zur Lösung des QP durchgeführt, der selbst ein Optimierungsproblem darstellt, um den nächsten Iterationsschritt zu finden. Wenn eine Quasi-Newton-Methode verwendet wird, muss ein Optimierungsproblem gelöst werden, um die Quasi-Newton-Aktualisierung des Hessischen des Lagrangen zu bestimmen - in der Regel handelt es sich dabei um eine Optimierung in geschlossener Form unter Verwendung geschlossener Formeln wie BFGS oder SR1. aber es könnte eine numerische Optimierung sein. Dann wird der neue QP gelöst, usw. Wenn der QP jemals undurchführbar ist, einschließlich zu Beginn, wird ein Optimierungsproblem gelöst, um einen durchführbaren Punkt zu finden. In der Zwischenzeit werden möglicherweise ein oder zwei Ebenen interner Optimierungsprobleme im QP-Solver aufgerufen. Am Ende jeder Iteration kann ein nicht negatives lineares Problem der kleinsten Quadrate gelöst werden, um die Optimalitätsbewertung zu bestimmen. Etc.

Wenn dies ein gemischtes ganzzahliges Problem ist, kann dieser gesamte Schebang an jedem Verzweigungsknoten als Teil eines Algorithmus höherer Ebene ausgeführt werden. In ähnlicher Weise wird für einen globalen Optimierer ein lokales Optimierungsproblem verwendet, um eine Obergrenze für die global optimale Lösung zu erzeugen. Anschließend werden einige Einschränkungen gelockert, um ein Optimierungsproblem für die Untergrenze zu erzeugen. Tausende oder sogar Millionen von "einfachen" Optimierungsproblemen aus Branch and Bound könnten gelöst werden, um ein gemischtes ganzzahliges oder globales Optimierungsproblem zu lösen.

Dies sollte Ihnen eine Idee geben.

Bearbeiten : Als Antwort auf die Henne-Ei-Frage, die der Frage nach meiner Antwort hinzugefügt wurde: Wenn es ein Henne-Ei-Problem gibt, dann ist es kein gut definierter praktischer Algorithmus. In den Beispielen, die ich gegeben habe, gibt es kein Huhn und Ei. Übergeordnete Algorithmusschritte rufen Optimierungslöser auf, die entweder definiert sind oder bereits existieren. SQP ruft iterativ einen QP-Löser auf, um Unterprobleme zu lösen, aber der QP-Löser löst ein einfacheres Problem, QP, als das ursprüngliche Problem. Wenn es einen noch höheren globalen Optimierungsalgorithmus gibt, kann er einen SQP-Löser aufrufen, um lokale nichtlineare Optimierungs-Teilprobleme zu lösen, und der SQP-Löser ruft wiederum einen QP-Löser auf, um QP-Teilprobleme zu lösen. Kein Küken und Ei.

Hinweis: Optimierungsmöglichkeiten gibt es "überall". Optimierungsexperten, wie z. B. diejenigen, die Optimierungsalgorithmen entwickeln, erkennen diese Optimierungsmöglichkeiten mit größerer Wahrscheinlichkeit und sehen sie als solche an als der Durchschnitt von Joe oder Jane. Und da sie algorithmisch geneigt sind, sehen sie ganz natürlich Möglichkeiten, Optimierungsalgorithmen aus untergeordneten Optimierungsalgorithmen aufzubauen. Formulierung und Lösung von Optimierungsproblemen dienen als Bausteine ​​für andere (übergeordnete) Optimierungsalgorithmen.

Edit 2 : Als Antwort auf eine Kopfgeldanforderung, die gerade vom OP hinzugefügt wurde. In dem Artikel, in dem der nichtlineare SQP-Optimierer SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf beschrieben wird , wird der QP-Solver SQOPT, der separat dokumentiert ist, speziell zur Lösung von QP-Teilproblemen in SNOPT verwendet.

Ich mag Marks Antwort, aber ich würde trotzdem "Simulated Annealing" erwähnen, das grundsätzlich auf jedem Optimierungsalgorithmus ausgeführt werden kann. Auf hohem Niveau funktioniert es so:

Es hat einen "Temperatur" -Parameter, der heiß beginnt. Während es heiß ist, tritt es häufig weg und (und weiter weg) von der Stelle, auf die der untergeordnete Optimierungsalgorithmus zeigt. Wenn es abkühlt, folgt es den Anweisungen des untergeordneten Algorithmus genauer, und bei Null folgt es ihm bis zu dem lokalen Optimum, bei dem es dann gelandet ist.

Die Intuition ist, dass es den Raum am Anfang weitgehend durchsucht und nach "besseren Orten" sucht, um nach Optimalwerten zu suchen.

Wir wissen, dass es keine wirkliche allgemeine Lösung für das lokale / globale Optimierungsproblem gibt. Jeder Algorithmus hat seine blinden Flecken, aber solche Hybriden scheinen in vielen Fällen bessere Ergebnisse zu liefern.

Ich denke, ein Hinweis, dass ich Ihren Wunsch befriedige, ist hier . Fahren Sie mit Abschnitt 4 - Optimierung in der modernen Bayes'schen Berechnung fort.

TL; DR - sie diskutieren proximale Methoden. Einer der Vorteile solcher Methoden ist die Aufteilung - Sie können eine Lösung finden, indem Sie einfachere Teilprobleme optimieren. Häufig (oder zumindest manchmal) finden Sie in der Literatur einen speziellen Algorithmus zur Bewertung einer bestimmten proximalen Funktion. In ihrem Beispiel machen sie Bildentrauschung. Einer der Schritte ist ein sehr erfolgreicher und viel zitierter Algorithmus von Chambolle.

Dies ist in vielen Optimierungspapieren durchaus üblich und hat mit Allgemeingültigkeit zu tun. Die Autoren schreiben die Algorithmen normalerweise auf diese Weise, um zu zeigen, dass sie für jede Funktion f technisch funktionieren. In der Praxis sind sie jedoch nur für sehr spezifische Funktionen nützlich, bei denen diese Unterprobleme effizient gelöst werden können.

Zum Beispiel, und jetzt spreche ich nur über den zweiten Algorithmus, wenn Sie einen proximalen Operator sehen (der, wie Sie bemerkt haben, ein anderes Optimierungsproblem darstellt, das in der Tat sehr schwer zu lösen ist), impliziert dies normalerweise, dass er eine geschlossene Lösung in hat damit der Algorithmus effizient ist. Dies gilt für viele Funktionen, die für maschinelles Lernen von Interesse sind, wie z. B. die l1-Norm, Gruppennormen und so weiter. In diesen Fällen würden Sie die Unterprobleme durch die explizite Formel des proximalen Operators ersetzen, und es ist kein Algorithmus erforderlich, um dieses Problem zu lösen.

Wenn Sie eine andere Funktion entwickeln und diesen Algorithmus anwenden möchten, prüfen Sie zunächst, ob das proximale Element eine geschlossene Form hat oder effizient berechnet werden kann. In diesem Fall stecken Sie einfach die Formel in den Algorithmus und Sie können loslegen. Wie bereits erwähnt, ist damit sichergestellt, dass der Algorithmus allgemein genug ist, um auf zukünftige Funktionen angewendet werden zu können, die nach der Erstveröffentlichung des Algorithmus auftreten können, zusammen mit ihren proximalen Ausdrücken effizienter Algorithmen, um diese zu berechnen.

Als letztes Beispiel nehmen wir das Originalpapier des klassischen FISTA-Algorithmus. Sie leiten den Algorithmus für zwei sehr spezifische Funktionen ab, den Quadratverlust und die l1-Norm. Sie stellen jedoch fest, dass keine Funktionen angewendet werden können, solange sie einige Voraussetzungen erfüllen, wobei eine davon darin besteht, dass das proximale des Regularisierten effizient berechnet werden kann. Dies ist keine theoretische, sondern eine praktische Voraussetzung.

Diese Kompartimentierung macht den Algorithmus nicht nur allgemeiner, sondern auch einfacher zu analysieren: Solange es Algorithmen für die Unterprobleme gibt, die diese Eigenschaften haben, wird der vorgeschlagene Algorithmus diese Konvergenzrate oder was auch immer haben.