Eine Einführung in die robuste Optimierung [... und eine kleine Einkaufsliste, die ich vergessen habe ...]

Wie kann festgestellt werden, wie viele Personen für eine neue Erfüllung eingestellt werden müssen, mit was genau sie gefüllt werden sollen und wo ein bestimmtes Produkt platziert werden soll? Je größer das Geschäft, desto größer die Unsicherheit und desto teurer der Fehler. Das Chaos zu besiegen und die beste Lösung zu wählen, ist eine der Aufgaben des Data Science-Teams. Und da Mathematik die Grundlage der Datenanalyse ist, beginnen wir damit.

In diesem Beitrag werden Optimierungsprobleme mit Datenunsicherheit und deren Approximation durch deterministische konvexe Probleme betrachtet. Dies ist einer der Haupttricks bei der robusten Optimierung - eine Technik, mit der Sie Optimierungsaufgaben bewältigen können, die zu empfindlich auf Änderungen der Eingabedaten reagieren.

Das Thema Sensibilität ist sehr wichtig. Für Aufgaben, deren Qualität schwach von Änderungen der Daten abhängt, ist es einfacher, die übliche stochastische Optimierung zu verwenden. Bei Aufgaben mit hoher Empfindlichkeit führt dieser Ansatz jedoch zu einem schlechten Ergebnis. Es gibt viele solcher Aufgaben in den Bereichen Finanzen, Lieferkettenmanagement, Design und vielen anderen Bereichen.

Und ja, dies ist ein Beispiel für einen Beitrag, bei dem die Komplexität exponentiell zunimmt (Müll bereits) ...

Was bedeutet es, das Optimierungsproblem zu „lösen“?

Beginnen wir mit einer kurzen Erinnerung.

Die Optimierungsaufgabe sieht im Allgemeinen folgendermaßen aus:

$$

$$\ min_ {x \ in R ^ n} f (x) \\ s.t. \\ x \ in X$$

Hier $$$f (x)$ die Zielfunktion genannt, und $$$X$ - ein gültiger Satz.

Mit der Lösung des Optimierungsproblems meinen wir einen solchen Punkt $$$x ^ * \ in X$ für die es ausgeführt wird:

$$

$$f (x) - f (x ^ *) \ geq 0, \ quad \ forall x \ in X$$

Dies ist das Standardkonzept zur Lösung des Optimierungsproblems ohne Unsicherheit.

Was ist ein Optimierungsproblem mit Unsicherheit?

Es ist Zeit, sich über den Ursprung der Funktion zu wundern $$$f (x)$ und Einschränkungen $$$X$ .

Sehr nützlich zu teilen

• strukturelle Logik des Problems (mit anderen Worten, welche Funktionen verwendet werden),
• technische Einschränkungen (unabhängig von menschlicher Logik oder Daten),
• Parameter, die aus den Daten ausgewertet werden.

Zum Beispiel kam ein Unternehmer zu uns und zeigte das Problem der linearen Programmierung:

$$

$$\ min_ {x \ in R ^ 2} 2,16 x_1 + 3,7 x_2 \\ s.t. \\ 0,973 x_1 + 2,619 x_2 \ leq 3,32 \\ x_1 \ geq 0, x_2 \ geq 0$$

Sie sehen diese Aufgabe zum ersten Mal. Ein Mann auch (vielleicht nicht, aber in blauen Jacken ist alles so abstrakt!). Sie kennen die Bedeutung von Variablen nicht. Aber auch jetzt können wir mit viel Zuversicht sagen:

1. Höchstwahrscheinlich ist die Aufgabe linear, weil sich jemand dafür entschieden hat. Linearität ist die Struktur, die eine Person gewählt hat.
2. Einschränkungen $$$x_1 \ geq 0, x_2 \ geq 0$ sind technisch. Das heißt, sie stammten aus der "Physik" und nicht aus Daten (zum Beispiel können Verkäufe nicht negativ sein).
3. Spezifische Koeffizienten $$$\ {0,973, 2,619, 3,32 \}$ bei der Begrenzung $$$0,973 x_1 + 2,619 x_2 \ leq 3,32$ in unserem Beispiel wurden aus den Daten ausgewertet. Das heißt, zuerst sagte jemand, dass die Variable $$$x_1$ mit Variable verbunden $$$x_2$ Dann wurde gesagt, dass die Beziehung linear ist, und schließlich wurden die Koeffizienten in der Kopplungsgleichung aus den Daten geschätzt. Gleiches gilt für die Gewinnchancen. $$$\ {2.16, 3.7 \}$ in der Zielfunktion.

Wenn wir über Aufgaben mit Unsicherheit sprechen, zielen wir genau auf die Unsicherheit der aus den Daten geschätzten Parameter ab. Wir berühren nicht die technischen Einschränkungen oder die anfängliche Wahl der Struktur des Problems.

Zurück zu unserer Geschichte. Wir haben ein lineares Problem, jemand hat die Koeffizienten darin irgendwie geschätzt. Wenn wir in Bezug auf die Art der Koeffizienten in der Funktion Recht hatten, wurden wir tatsächlich gebeten, das Problem für ein Szenario der Entwicklung von Ereignissen (eine bestimmte Instanz des Problems) zu lösen.

Manchmal reicht uns das und wir lösen es einfach.

Manchmal ist es jedoch eine dumme Idee, ein Problem für ein Szenario zu lösen (z. B. wenn die Lösung sehr empfindlich auf Datenschwankungen reagiert).

Was ist in diesem Fall zu tun und wie wird die Unsicherheit in den Daten modelliert?

Beachten Sie zunächst, dass die Datenunsicherheit immer von der Zielfunktion auf Einschränkungen oder umgekehrt übertragen werden kann. Wie das geht, schauen Sie unter den Schnitt.

Stochastische, Online-, robuste Optimierungs- und Produktliste

Wir können viele Szenarien der Unsicherheit haben sowie Optionen, was damit zu tun ist. Wir veranschaulichen verschiedene Standardansätze anhand eines einfachen Beispiels.

Ich weiß nicht, wie die Situation mit einem angesehenen Leser ist, aber hier bin ich verheiratet (erfolgreich) und gehe regelmäßig zum Lebensmittelgeschäft. Natürlich mit einem Blatt (gibt Unverwundbarkeit durch impulsive Einkäufe). Manchmal nicht nur zum Laden, sondern auch zum bedingten Auchan, wo es billiger ist, aber wo man weit gehen kann.

Wir werden diese Situation modellieren: Wir kamen mit einem Blatt in der Hand zum Einkaufen nach Auchan.

Achtung, die erste Frage: Wie modellieren?

Eingabe: Informationen zu den zu kaufenden Produkten und der erforderlichen Menge.

Der Einfachheit halber können wir uns die Packungsbeilage als einen ganzzahligen nicht negativen Vektor vorstellen $$$y \ in Z _ + ^ n$ .

Als Variablen nehmen wir jeweils einen ganzzahligen nicht negativen Vektor $$$x \ in Z _ + ^ n$ - wie viele und welche Produkte werden wir letztendlich kaufen (unsere Lösung).

Der Punkt ist klein - nehmen Sie eine Art objektive Funktion $$$f (x, y)$ , was besagt, wie sehr wir bei der Auswahl der Produkte einen Fehler gemacht haben.

Je nach Kontext kann sich die Art der Funktion ändern, es gibt jedoch einige grundlegende Anforderungen:

• Funktion $$$f (x, y)$ sollte ein Minimum haben $$$x ^ * = \ arg \ min_ {x \ in R ^ n} f (x, y) = y$ (das heißt, im Optimum kaufen wir genau das, was in der Packungsbeilage steht)
• Funktion $$$f (x, y)$ muss konvex sein $$$x$ (und vorzugsweise glatt) - um effektiv berechnen zu können $$$min$ .

So erhalten wir das Problem:

$$

$$min_ {x \ in R ^ n} f (x, y)$$

Stellen Sie sich nun vor, das Blatt sei zu Hause geblieben ...

Mit einer Bemerkung sind wir mit Unsicherheit in die Welt der Aufgaben gekommen.

Was tun, wenn in der Aufgabe $$$min_ {x \ in R ^ n} f (x, y)$ uns unbekannt $$$y$ ?

Die Antwort hängt wiederum vom Kontext ab.

Stochastische Optimierung

Stochastische Optimierung beinhaltet (normalerweise)

• Die Unsicherheit in den Daten ist stochastischer Natur. Vollständige Kenntnis der probabilistischen Verteilung nicht deterministischer Parameterwerte
• Einschränkungen einschließlich Unsicherheit sind gering

In unserem Beispiel würden wir sagen, wenn wir es mit stochastischer Optimierung modellieren würden

• Okay, ich weiß nicht, was in der Packungsbeilage geschrieben steht, aber ich gehe jetzt seit 8 Jahren mit Flugblättern spazieren und habe genug Wissen über die Verteilung des Vektors $$$y$
• Auch wenn ich bei der Auswahl einen Fehler mache (d. H. Mit $$$x$ ), nach Hause zurückkehrend, finde ich das echte heraus $$$y$ und wenn ich völlig sicher bin, gehe ich nach Pyaterochka und kaufe dort ein, wenn auch teurer.
• Jetzt werde ich einen auswählen $$$x$ Dies minimiert eine Art Aggregat aus der ursprünglichen Zielfunktion und mögliche „Bußgelder“ für den Fehler.

Dies wird uns zu dieser Aufgabe führen:

$$

$$\ min_ {x \ in R ^ n} E_y [f (x, y) + \ psi (y, z)] \\ s.t. \\ x + z \ geq y$$

Beachten Sie, dass wir bei dieser Aufgabe de facto zweimal Entscheidungen treffen: Erstens die Hauptentscheidung für den Kauf bei Auchan, für die wir verantwortlich sind $$$x$ , dann "Fehlerkorrektur" mit $$$z$ .

Die Hauptprobleme bei diesem Ansatz sind:

• Es gibt oft keine Informationen über die Verteilung von Parametern.
• Einschränkungen können schwerwiegend sein (für Aufgaben mit hohem Risiko - Tod, Ruine, Atom- oder Zombie-Apokalypse usw.)
• Es ist nicht immer möglich, „Fehler zu korrigieren“ (eine Entscheidung wird einmal getroffen) oder umgekehrt, Entscheidungen werden häufig getroffen (in diesem Fall erscheinen viele verschachtelte Integrale und es ist sehr schwierig zu zählen).

Online-Optimierung

Die Online-Optimierung ist ein Framework, das konsistente Entscheidungen untersucht. Einer der Standardansätze für die Modellierung in diesem Rahmen sind mehrarmige Banditen, über die bereits viele Male auf Habré geschrieben wurde.

Im Kontext unseres Spielzeugbeispiels würden wir:

• hatte keine (und noch nie benutzte) Broschüre
  
• und zu Hause würden wir für die Produkte, die wir gekauft haben, gelobt / gescholten (gleichzeitig konnten wir nur das gewünschte Set erraten)
• Die Aufgabe wäre es, so schnell wie möglich zu lernen, wie man Lebensmittel kauft, ebenso wie ihren ehemaligen, imaginären Prinzen oder den besten Freund der Söhne ihrer Mutter.

Robuste Optimierung

Eine robuste Optimierung ist eine logische Erweiterung der Idee einer Minimax-Lösung.

Im Idealfall sollten wir jetzt eine Entscheidung treffen, die unabhängig von den Umständen immer akzeptabel ist. Menschen, die in der UdSSR Töpfe, Bügeleisen und Kühlschränke entworfen haben, haben dies im Rahmen einer robusten Optimierung getan: Das Produkt sollte auch dann funktionieren, wenn es seit 20 Jahren als Hauptinstrument für die Ausrottung von Mutanten verwendet wird, die nach dem Atomkrieg entstanden sind (es muss auch überlebt werden).

Außerdem möchte ich, dass die Aufgabe in einen normalen Löser verschoben wird - und sie verstehen die Einschränkungen "für jede Implementierung einer Zufallsvariablen" nicht (wenn es nicht eine begrenzte Anzahl dieser Implementierungen gibt).

Bei dem Problem mit einer Broschüre sollte die Entscheidung hier und jetzt getroffen werden und unter allen Umständen gültig bleiben:

$$

$$\ min_ {x \ in R ^ n, t \ in R} t \\ s.t. \\ f (x, y) \ leq t \ quad \ für alle y \\ x \ geq y \ quad \ für alle y$$

Es ist klar, dass auch in diesem Spielzeugbeispiel, wenn Sie nichts von benötigen $$$y$ , dann wird keine sinnvolle Lösung funktionieren.

Wie gehen Sie mit solchen Aufgaben um?

Erstellen einer robusten Version einer Aufgabe anhand des LP-Aufgabenbeispiels

Betrachten Sie ein lineares Optimierungsproblem mit Unsicherheit:

$$

$$\ min_ {x \ in R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

Parameter $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ wurden aus Daten abgeleitet und beinhalten Unsicherheit.

Annahme 1: Viele Werte (Implementierungen) $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ kann parametrisiert werden, d.h. es gibt solche $$$\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix}, \ begin {pmatrix} c_1 ^ T, d_1 \\ A_1, b_1 \ end {pmatrix}, \ dots, \ begin {pmatrix } c_k ^ T, d_k \\ A_k, b_k \ end {pmatrix}$ dass jede Datenimplementierung $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ liegt im Set:

$$

$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix} \ in U = \ left \ {\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ begin {pmatrix} c_i ^ T, d_i \\ A_i, b_i \ end {pmatrix} | \ quad \ zeta \ in Q \ Teilmenge R ^ k \ right \}$$

Hier $$$\ begin {pmatrix} c ^ T_0, d_0 \\ A_0, b_0 \ end {pmatrix}$ werden als "nominelle" Daten bezeichnet, und $$$\ begin {pmatrix} c ^ T_i, d_i \\ A_i, b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - "Verschiebungen".



Wir wissen bereits, dass alle Unsicherheiten in Bezug auf das Problem in den Einschränkungen beseitigt werden können. Lass es uns tun.

Wir bekommen das Problem

$$

$$\ min_ {x \ in R ^ n, t \ in R} t \\ st \\ c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ in U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ in U \\ $$

Robuste Version der Aufgabe

Jetzt ist die Zeit für einen der coolsten Tricks bei der robusten Optimierung gekommen - wie man von einer unendlichen Anzahl von Einschränkungen zu einer endlichen Menge guter Einschränkungen übergeht.

Betrachten Sie zunächst ein einfaches Beispiel, wenn

$$

$$Q = \ {\ zeta \ in R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

Alle Einschränkungen im System

$$

$$c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ in U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ in U \\ $$

der gleiche Typ - es sind nur lineare Ungleichungen. Lerne mit einem zu arbeiten - lerne mit jedem zu arbeiten.

Daher betrachten wir eine Einschränkung des Ungleichheitstyps:

$$

$$a ^ Tx \ leq b \ quad \ forall (a, b) \ in U = \ {(a_0, b_0) + \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i, b_i) | \ quad \ zeta \ in Q \} \\ (a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i) ^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ in Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ in Q \\ \ max _ {\ zeta \ in Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

Lassen Sie mich erklären, was passiert ist.

Zuerst haben wir alle Teile mit Unsicherheit auf die linke Seite der Ungleichung übertragen; $$$\ zeta$ .
Danach haben wir uns den schlimmsten Fall angesehen (für jeden $$$x$ er ist sein).
Als Ergebnis haben wir folgende Aufzeichnung erhalten:

$$

$$g (x) = max _ {\ zeta \ in Q} f (x, \ zeta) \ leq b_0 - a_0 ^ Tx$$

.

Der nächste Schritt besteht darin, eine explizite Funktion zu schreiben $$$g (x)$ . Dazu reicht es aus, das Optimierungsproblem durch zu lösen $$$\ zeta$ und ersetzen Sie das Optimum $$$\ zeta *$ ::

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx - b_i) ^ 2}$$

was zu Ungleichheit führt:

$$

$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

Beachten Sie, dass die resultierende Ungleichung konvex und beliebig ist $$$x$ Ihn zu befriedigen befriedigt das Original $$$a ^ Tx \ leq b$ für jede Implementierung $$$(a, b) \ in U$ ...

Einschränkung $$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ wird die robuste Version der Einschränkung genannt $$$a ^ Tx \ leq b \ quad \ forall (a, b) \ in U$ .

Dies ist eines der Hauptarbeitspferde bei der robusten Optimierung - die Approximation von Wahrscheinlichkeitsbeschränkungen durch eine endliche Menge konvexer Beschränkungen.

Was tun mit komplexeren (nichtlinearen) Einschränkungen?

Erstellen robuster Versionen von Einschränkungen mithilfe der konischen Dualität

Viele nichtlineare Standardbedingungen können in einer konischen Form (d. H. In der Form) dargestellt werden $$$Axe + b \ in K$ wo $$$K$ ist ein geschlossener konvexer Kegel):

• Nicht-Negativität $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ in R ^ n _ +$
• Normbeschränkungen $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ begin {pmatrix} x \\ p \ end {pmatrix} \ in K_p ^ n = \ left \ {(x, t) \ in R ^ n \ times R_ + | \ quad \ | x \ | _p \ leq t \ right \}$
• Einschränkungen für die positive Bestimmtheit der Matrix $$$x_1F_1 + \ dots x_nF_n + G \ succeq 0$

Zurück zu robusten Einschränkungen.

Angenommen, das Optimierungsproblem in Bezug auf $$$\ zeta$ schaffte es, auf eine konische Form reduziert zu werden

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) \\ s.t \\ C \ zeta + d \ in K$$

Wir konstruieren ein Dual für dieses Problem.

Vor einiger Zeit habe ich einen Beitrag über konische Dualität veröffentlicht , um der Technik in diesem Beitrag etwas weniger Aufmerksamkeit zu widmen.

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k \\ \ lambda \ in K ^ *$$

Jetzt liegt es an der kleinen Sache - dem schwachen Dualitätssatz:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ in K]} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ {\ lambda \ in G} \ lambda ^ Td \\ wobei \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ in K ^ * \ right \}$$

Daher als robuste Annäherung an die Anfangsbedingung $$$a ^ Tx \ leq b, \ quad (a, b) \ in U$ Einschränkung kann verwendet werden

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ in K ^ * \ right \}$$

wo $$$\ lambda$ gleiche Variable wie $$$x$ .

Deshalb haben wir eine robuste Einschränkung für die ursprüngliche Ungleichung erstellt.

Fazit

Wir untersuchten die Technik der Approximation schlechter (stochastischer) Einschränkungen durch eine Reihe guter konvexer. Dies kann beispielsweise nützlich sein, wenn:

• Sie möchten keine Algorithmen selbst schreiben, aber der von Ihnen verwendete Solver weiß nicht, wie er mit Wahrscheinlichkeitsbeschränkungen arbeiten soll.
• Es gibt ein Problem mit stochastischen Parametern, während das Optimum sehr empfindlich auf Schwankungen in den Daten reagiert.
• Und natürlich Aufgaben mit Unsicherheit, bei denen alle Einschränkungen streng sind (der Preis des Fehlers ist zu hoch).