Vincent Zoonekynds Blog Viele Probleme in der Statistik oder maschinelles Lernen sind von der Form finden Sie die Werte der Parameter, die ein Minimum an Fehler zu minimieren. In einigen Fällen werden aber auch Einschränkungen auf die Parameter angewendet: zum Beispiel, dass sie zu 1 zusammenfassen oder dass höchstens zehn von ihnen ungleich Null sein sollten - dies fügt dem Problem eine kombinatorische Ebene hinzu, die es macht Viel schwerer zu lösen. In dieser Anmerkung werde ich einen Leitfaden für (einige der) Optimierungspakete in R geben und erklären (einige der Algorithmen dahinter). Die Löser, die aus R zugänglich sind, haben einige Einschränkungen, wie die Unfähigkeit, mit binären oder integralen Einschränkungen (bei nichtlinearen Problemen) umzugehen: Wir werden sehen, wie solche Probleme zu lösen sind. Wenn du anfängst, Optimierungssoftware zu verwenden, kämpfst du, das Problem in die Form zu lösen, die von der Software erwartet wird (du mußt es häufig neu formulieren, um es linear oder quadratisch zu bilden und es dann in Matrixform zu schreiben). Dies ist nicht sehr benutzerfreundlich. Wir werden sehen, dass es möglich ist, Optimierungsprobleme in einer perfekt lesbaren Weise zu spezifizieren. Viele Beispiele werden aus der Finanzierung und Portfoliooptimierung entnommen. Einleitung Optimierung bezieht sich auf das Problem der Suche nach dem Minimum oder dem Maximum einer Funktion, vorbehaltlich einiger Einschränkungen. Optimierungsprobleme (manchmal genannt Optimierungsprogramme - das Wort kommt aus einer Ära ohne Computer und keine Computerprogramme) werden oft geschrieben, wenn x ein Vektor und f, g, h beliebige Funktionen ist. Lassen Sie uns zuerst beschreiben einige der Komplikationen, die auftreten können, wenn Sie mit einem Optimierungsproblem konfrontiert sind. Lokale Extrema Da viele Optimierungsalgorithmen nur lokale Informationen verwenden, können sie in einem lokalen Extremum stecken bleiben. Im folgenden Beispiel gibt es viele Täler: der Computer wird eine von ihnen finden, aber nicht unbedingt die niedrigste. (In diesem Beispiel könnten Sie einen robusteren Optimierungsalgorithmus, wie z. B. DEoptim, verwenden oder besser die Wellen und das lokale Extrema durch Ausweitung des Sinus beseitigen.) Reparametrisierung, um Zwangsbedingungen zu entfernen Die Situation wird oft komplizierter durch die Anwesenheit Der Zwänge. Glücklicherweise können sie häufig durch Neuformulierung des Problems entfernt werden: Wenn Sie eine Gleichheitsbeschränkung haben, können Sie oft eine der Unbekannten als eine Funktion der anderen ausdrücken, wenn Sie eine Ungleichungsbeschränkung der Form x0 haben, können Sie x durch exp ersetzen (Y) oder y2 oder log (1exp (y)), wobei y ein neues Unbekanntes ist. Zum Beispiel betrachten wir eine eingeschränkte Regression: Das Problem kann wie folgt reparametriert werden. Leider funktioniert dieser Ansatz nicht immer. Betrachten Sie das folgende Problem. Angenommen n Zahlen a1. An, wollen wir x1 finden. Xn, so nah wie möglich von der ai, aber in zunehmender Reihenfolge. Wenn wir die Summe der quadratischen Distanzen verwenden, um die Nähe zu messen, kann das Optimierungsproblem geschrieben werden, anstatt nach x1, x2 zu suchen. Xn, können wir suchen Das Problem wird Die Einschränkung ist einfacher, aber wir haben nicht vollständig loszuwerden. Aber wir können schreiben y exp (z): das wird sicherstellen, dass es positiv bleibt. Die Zwänge sind jetzt völlig verschwunden: Wir haben eine sehr schlechte Lösung. Eines der Probleme ist, dass die Lösung an der Grenze ist, aber die Grenze ist nicht mehr erreichbar nach unserer Reparametrierung. In diesem Fall ist die quadratische Programmierung ein besserer Ansatz. Harte und weiche Strafen In einigen Fällen sind die Einschränkungen zu unregelmäßig oder zu zahlreich: Wir können sie nicht entfernen. Stattdessen können wir eine Strafe für Zwangsverletzungen hinzufügen und schrittweise erhöhen die Strafe. Optimierung in R Die Funktionen zur Lösung von Optimierungsproblemen werden in vielen Paketen gestreut, die jeweils auf (oder optimierte) Probleme eines bestimmten Typs beschränkt sind. Um die Dinge zu komplizieren, sind die Schnittstellen unterschiedlich. Hier sind einige davon. Es gab einige Versuche, alle diese Pakete zu vereinheitlichen, z. B. Die ROI - und optimx-Pakete (sie erlauben es, zuerst das Optimierungsproblem zu beschreiben, immer in der gleichen Weise, unabhängig vom Typ des Problems und nur dann den zu verwendenden Löser auszuwählen, ROI für die mathematische Programmierung, optimx für die Optimierung ohne oder Box-Einschränkungen), aber sie sind noch unvollständig und fehlende Dokumentation. Es gibt eine erschöpfendere Liste in der Ansicht der Optimierungsaufgabe. Wenn Sie mit ihnen nicht vertraut sind, schlage ich vor, sie in der folgenden Reihenfolge zu überprüfen. Optim wird für die meisten Ihrer Optimierungsanforderungen ausreichen, aber Sie können auf DEoptim für Probleme mit vielen lokalen Extrema zurückgreifen möchten. Für nichtlineare Probleme mit Nicht-Box-Einschränkungen (d. H. Einschränkungen, die durch mehrere Funktionen mit Gleichungen oder Ungleichungen anstelle von oberen und unteren Schranken spezifiziert werden), verwenden Sie Rsolnp. Wenn das Problem groß und linear oder quadratisch ist, sollten Sie Rglpk oder quadprog ausprobieren: Sie werden viel schneller sein, aber es kann schwierig sein, das Problem in Matrixform zu schreiben. Einige dieser Löser haben Einschränkungen. Zum Beispiel, lpSolve erzwingt, dass alle Variablen nicht-negativ (es ist in der Dokumentation, mit einem Ausrufezeichen, aber es ist einfach zu übersehen - Rglpk als das gleiche Standard-Verhalten, aber es kann geändert werden) quadprog funktioniert nur für Streng konvexe Probleme (die quadratische Form muss positiv definit sein, aber wenn Sie schlaffe Variablen hinzufügen müssen, um einige der Einschränkungen zu transformieren, erhalten Sie eine positive halbdefinite Matrix und es funktioniert nicht mehr - das ist eine ernsthafte Einschränkung) Integrationsbeschränkungen können nur auf einige der linearen Solver auferlegt werden. Mit Ausnahme der nichtlinearen Löser (und Rglpk, auf die Sie eine Textdatei geben können) ist es nicht möglich, die Probleme menschenlesbar zu definieren: nur Matrizen. Wenn Ihr Problem nicht linear ist, sondern leicht in ein lineares Problem umgewandelt werden kann, müssen Sie die Transformation selbst durchführen. Einige der Transformationen (z. B. die Trennung des positiven und negativen Wertes einer Zahl, um ihren absoluten Wert auszudrücken) sind einfach, aber andere sind komplexer, zeitraubender und fehleranfällig (zB Umwandlung des erwarteten Fehlbetrags in eine lineare Größe oder Umwandlung von quadratischen Einschränkungen in halbdefinitive Einschränkungen). Beispiel: Regression Lineare Regression ist ein Optimierungsproblem: Wir suchen nach dem Wert von b, der die restliche Summe von Quadraten minimiert. Vergleichen wir das Optimierungsproblem mit der Regression. Beispiel: Constrained Regression Die Neuformulierung des Regressionsproblems als Optimierungsproblem erlaubt Ihnen, einfache lineare Einschränkungen hinzuzufügen. Beispielsweise können die Koeffizienten der Regression bis zu 1 zusammengefasst werden. Beispiel: Quantilregression Das Problem, den Median eines Satzes von Zahlen x1 zu finden. Xn kann als nichtlineares Optimierungsproblem formuliert werden: Es kann als lineares Problem umformuliert werden, indem die Absolutwerte durch die Summe ihrer positiven und negativen Teile ersetzt werden. Lassen Sie uns ein Beispiel überprüfen. Dies kann auf andere Quantile verallgemeinert werden: Anstelle der Verwendung der symmetrischen gestrichelten Linie abs (x-mu) als Verlustfunktion können wir eine asymmetrische gestrichelte Linie mit der Steigung tau, wenn x-mu0 und 1-tau ansonsten mit tau verwenden In 0,1. Der Median wird für tau12 erhalten. Wir können diese asymmetrische Strichlinie auch als Verlustfunktion bei der Berechnung einer Regression verwenden: Wenn tau12 (Median), ist dies die L1-Regression und wird im allgemeinen als Quantilregression bezeichnet. (Ein Wort der Vorsicht: Sie sollten nicht lpSolve genau auf diese Weise verwenden. Es setzt voraus, dass alle Variablen positiv, einschließlich der Quantile. Unsere Beispiele funktioniert nur, weil die Quantile sind positiv.) Algorithmen Gradient descent Das Problem der Suche nach dem Minimum von Kann eine Funktion f (x) geometrisch wie folgt interpretiert werden: Wenn f die Höhe in einer Landschaft darstellt, minimiert f die Suche nach dem tiefsten Tal. Ein einfacher Algorithmus kommt in den Sinn: einfach bergab gehen. Formalerweise beginnen Sie mit einer anfänglichen Schätzung x der Lösung berechnen die Ableitung (auch als Gradient) von f, um die Richtung der steilsten (Abwärts) Slope zu finden, und einen Schritt in diese Richtung stoppen, wenn Sie nicht mehr finden können, nach unten Richtung. Sie müssen die Schrittgröße im Voraus zu wählen, aber Sie können es auf die Norm der Steigung abhängen wollen. Nelder-Mead Wenn Sie die Ableitung der Funktion nicht kennen (oder nicht differenzierbar), können Sie den Gradientenabstiegsalgorithmus wie folgt ändern. Beginnen Sie mit einer anfänglichen Vermutung x. Wählen Sie eine zufällige Richtung unter den n Koordinaten, schritt vorwärts und rückwärts in diese Richtung und vergleichen Sie die Werte von f: f (x), f (xh), f (x-h). Wenn einer der neuen Werte besser ist als der aktuelle, gehen Sie zu diesem Punkt, ansonsten bewegen Sie sich nicht. Iterieren bis zur Konvergenz. Der Algorithmus kann verbessert werden, indem man die Schrittweite ändert: Erhöhe ihn (wenn du dich nicht bewegen kannst, wenn du dich nicht bewegen kannst, wenn du dich nicht bewegen kannst, , Und stoppen, wenn die Schrittgröße zu klein ist. Sie können eine andere Schrittweite für jede Koordinate verwenden, um Probleme zu vermeiden, wenn ihre Skalen unterschiedlich sind. Die Punkte xh, xh, um x in alle Richtungen, bilden eine Art (quadratische) Kugel: der Algorithmus lässt den Ball nur bergab rollen und benutzt eine kleinere Kugel für eine bessere Präzision, wenn er über ein zu kleines Tal steckenbleibt Es zu erforschen. In der Dimension n hat diese quadratische Kugel 2n Punkte (die Hyperwürfel hat 2n Ecken, aber wir verwenden nur die Punkte in der Mitte der Facetten). Der Nelder-Mead-Algorithmus verwendet eine ähnliche Idee, aber mit einem etwas ökonomischeren dreieckigen (tetraedrischen) Ball: er hat nur n1 Punkte. Stochastischer Gradient Oft ist die zu minimierende Funktion eine Summe mit einem Ausdruck für jede Beobachtung. In diesem Fall können Sie die Beobachtungen nacheinander verarbeiten (Online-Algorithmus): Berechnen Sie den Gradienten des Begriffs entsprechend der aktuellen Beobachtung, bewegen Sie sich in seine Richtung (verwenden Sie eine kleinere Schrittweite als Sie für den vollen Gradienten) und fahren Sie fort Mit dem nächsten Begriff. Conjugate gradient Sie können feststellen, dass Gradientenabstieg manchmal um die Lösung oszilliert, oder bewegt sich im Zickzack vor dem Erreichen des Optimums. Dies kann behoben werden, indem man sich nicht in Richtung des Gradienten bewegt, sondern in Richtung einer gewissen Linearkombination des Gradienten und der vorherigen Richtung. Dies kann als eine Art Trägheit interpretiert werden: Wir drehen teilweise, aber nicht vollständig, in Richtung des Gradienten, Der Hessische und seine Approximationen Der Gradientenabstiegsalgorithmus verwendete nur die erste Ableitung (dh angenähert die Funktion, um durch eine gerade Linie zu minimieren ). Stattdessen können wir die Funktion durch ihre zweite Taylor-Expansion approximieren: Die Approximation ist eine quadratische Funktion und (sofern sie positiv definiert ist), sie hat ein Extremum. Dies erfordert die zweite Ableitung (Hessische Matrix) und funktioniert bei niedrigen Abmessungen recht gut. Es ist eigentlich Newton-Methode, verwendet, um f (x) 0 zu lösen. Aber es gibt ein großes Problem mit dem Hessen: seine Größe. Wenn es n Parameter zur Schätzung gibt, ist der Hessian eine nn Matrix - wenn n groß ist, ist dies nicht zu bewältigen. Wir müssen eine Approximation dieser Matrix finden, die keine Berechnung und Speicherung von n2 Werten erfordert. Wenn die zu minimierende Funktion eine Summe von Quadraten ist, können die Berechnungen durch Annäherung des Hessischen (Gauss-Newton) vereinfacht werden: Der Schritt h wird so gewählt, dass S (bh) 0: Um Probleme beim Invertieren der Matrix zu vermeiden, Der Marquardt-Algorithmus schrumpft sie auf die Identität zu (dies entspricht der Kammregression): Wenn Lambda groß ist, ist dies tatsächlich ein Schritt in Richtung des Gradienten: Es ist eine Mischung aus Gradientenabstieg und Gauss-Newton. Im allgemeinen Fall, um eine Berechnung, Speicherung und Invertierung des Hessischen zu vermeiden, wollen wir eine Matrix B, so daß es viele mögliche Entscheidungen gibt. Man beginnt typischerweise mit einer anfänglichen Extinktion (zB B0I) und aktualisiert eine Schätzung des Hessischen, wenn der Algorithmus in Richtung Extremum fortschreitet, indem eine einfach zu berechnende Matrix hinzugefügt wird, z. B. Eine Matrix von Rang 1 (Matrizen von Rang 1 können als Produkt von zwei Vektoren ab geschrieben werden). Zum Beispiel verwendet der BFGS-Algorithmus zwei Matrizen von Rang 1: Es ist möglich, gleichzeitig eine Annäherung der Inverse von B zu verfolgen. Der L-BFGS (low-memory BFGS) Algorithmus hält nur die letzten L-Updates: es gibt nur 2L-Vektoren zu speichern. Beschränkte Optimierung: Lagrange Multiplikatoren Das beschränkte Optimierungsproblem kann (meistens) durch die Bedingung erster Ordnung ersetzt werden, dh wir wollen (x, lambda) so finden, dass dies wie folgt implementiert werden kann Minimum: Es könnte ein lokales Minimum sein oder, da es nur eine Bedingung erster Ordnung, ein Maximum oder ein Sattelpunkt ist. Das Betrachten der Bedingungen zweiter Ordnung würde mehr Information geben, zumindest wenn der Hessian invertierbar ist. KarushKuhnTucker-Bedingungen Lagrange-Multiplikatoren befassen sich mit Gleichstellungszwängen. Wenn wir auch Ungleichheitsbeschränkungen haben, werden die Dinge komplizierter. Die notwendige Bedingung für ein Extremum ist Die letzte Bedingung ist problematisch: sie sagt, daß für jede Ungleichungsbedingung hi (x) 0 entweder hi (x) 0 und die Bedingung bindend ist und hi in der ersten Gleichung oder hi (x ) 0, und die Einschränkung ist nicht bindend, verschwindet mui0 und hi aus der ersten Gleichung. Die Bestimmung, welche Bedingung verbindlich ist, ist ein kombinatorisches Problem, das am besten durch kombinatorische Algorithmen wie den Simplexalgorithmus angegangen wird. Lineare Programmierung, geometrische Interpretation und Simplexalgorithmus Das Optimierungsproblem (x, b, c sind Vektoren, A ist eine Matrix) kann wie folgt interpretiert werden. Die Beschränkungen definieren einen Schnitt von Halbräumen und bilden ein Polyeder. Die Ebenenkurven (Hypersurfaces) der Zielfunktion sind eigentlich gerade Linien (Hyperebenen), parallel zueinander wollen wir denjenigen mit dem höchsten Wert finden, der das Polyeder schneidet: das wird auf einem Scheitel des Polyeders geschehen. Dies ist ein kombinatorisches Problem: Es gibt eine endliche (aber oft sehr große) Anzahl von Ecken, und wir müssen das eine finden, das das Ziel maximiert. Der Simplex-Algorithmus wird wie folgt vorgehen: Beginnen Sie mit einem Scheitel des Polyeders, finden Sie eine Kante, in deren Richtung das Objektiv zunimmt, folgen Sie dieser Kante bis zum nächsten Scheitelpunkt und fahren Sie fort, bis Sie eine solche Kante nicht mehr finden können. Dazu benötigen wir einen Weg, um Ecken und Kanten zu beschreiben, die zwei Ecken miteinander verbinden. Das Optimierungsproblem kann wie folgt mit schlaffen Variablen umgeschrieben werden (wir ersetzen A x lt b durch A x xS b, xS 0). (Die Ungleichungsbeschränkungen sind eher ärgerlich, aber xS 0 ist absolut notwendig: sie stellt sicher, daß die Punkte innerhalb des Polyeders liegen, nicht ousid.) Sei (B, N) eine Teilung der Matrix (A, I), so daß B invertierbar ist . Lösungen mit xN0 entsprechen den Scheiteln und sind leicht zu beschreiben: Das Ziel ist auch sehr einfach: Der Algorithmus ist dann folgendermaßen: Beginnen Sie mit einer Partition (B, N) (zB könnte B den von uns hinzugefügten Slack-Variablen entsprechen) Ein Scheitel auf dem Polyeder) versuchen, eine Spalte zwischen B und N zu schalten, um das Objektiv zu vergrößern (dies entspricht dem Bewegen entlang einer Kante des Polyeders), bis Sie nicht mehr können. (Tatsächlich müssen Sie nicht alle Paare untersuchen: für jede Variable in N versuchen Sie es so weit wie möglich einzubeziehen, ohne die Einschränkungen zu verletzen: von () wird eine der Variablen in B dann 0 sein - das heißt Die man entfernen kann.) Lineare Programmierung und Dualität Sei x eine Lösung von Wir können eine untere Schranke auf dem Objektiv cx finden, indem wir eine lineare Kombination der Nebenbedingungen yb für einige y betrachten. Aber y b y A x und y A x lt c x mit y A lt c (da x 0, bleibt die Richtung der Ungleichung erhalten). Mit anderen Worten, jede mögliche Lösung von ist eine untere Schranke. Das ursprüngliche Problem wird als das ursprüngliche Problem, und das neue, das duale Problem. Es stellt sich heraus, dass es nicht nur eine untere Schranke ist: für die optimalen Lösungen ist der Wert des Objektivs dasselbe. Dies ist eine einfache Möglichkeit, zu überprüfen, ob eine praktikable Lösung eines linearen Optimierungsproblems die optimale Lösung ist: Wenn wir die möglichen Lösungen x und y der Ur - und Doppelprobleme mit den gleichen objektiven Werten cxby finden, dann sind sie beide optimale Lösungen . Wenn das Dual ist einfacher zu lösen, können Sie zuerst lösen, und verwenden Sie die Lösung, um das ursprüngliche Problem lösen. Einige Algorithmen versuchen, die Ur-und Dual-Probleme zur gleichen Zeit lösen, jeder hilft das andere lösen. Der Begriff der Dualität kann auf arbitratistische Optimierungsprobleme verallgemeinert werden, aber die Tatsache, dass die Ziele bei den optimalen Lösungen die gleichen sind, ist (oft aber) nicht immer wahr. Generalisierte reduzierte Gradienten Gradient-basierte Methoden können verwendet werden, um allgemeine Optimierungsprobleme mit Gleichheitsbeschränkungen wie folgt zu lösen. Linearisieren Sie die Einschränkungen verwenden sie, um einige der Unbekannten als eine Funktion der anderen (nur ein lineares System zu lösen) zum Lösen der resultierenden unbeschränkten Problem mit dem Gradientenalgorithmus iterieren bis Konvergenz auszudrücken. Wenn es auch Ungleichheitsbeschränkungen gibt, werden die Dinge komplizierter, aber wir können den Simplexalgorithmus anpassen. Um das Problem zu vereinfachen, verwenden Sie schlaffe Variablen, um die Ungleichungsbeschränkungen durch niedrigere oder obere Schrankenbeschränkungen zu ersetzen. Bei jedem Schritt des Algorithmus können wir die Gleichheitsbeschränkungen linearisieren und die Anzahl der Variablen reduzieren: Die resultierenden Probleme haben eine nichtlineare objektive, aber lineare Einschränkung. Ausgehend von einer realisierbaren Lösung können wir eine Methode mit Gradienten verwenden, um auf die Lösung zuzugehen und stoppen, wenn wir in die Grenze stoßen. Da wir an der Grenze sind, sind einige der Ungleichungsbeschränkungen aktiv (oder bindend), d. H. Gleichheiten. Wie bei der Simplexmethode können wir versuchen, die Ungleichungen zu finden, um die Zielfunktion aktiv oder nicht zu verbessern. Interne Punktmethoden Der Simplex-Algorithmus funktioniert gut, er erforscht aber die Oberfläche des Polyeders, die durch die Einschränkungen definiert ist - in hoher Dimension kann die Oberfläche sehr groß sein, verglichen mit dem Inneren des Polyeders (dies ist der sogenannte Fluch von Dimension). Innere Punktmethoden nehmen einen Kurzschnitt innerhalb des Polyeders. Für das Optimierungsproblem sind die Bedingungen erster Ordnung (Kuhn-Tucker) Wir könnten versuchen, sie zu lösen, indem wir dem Gradienten folgen, der einen Weg von einer praktikablen Lösung zum Extremum oder einen Punkt auf der Grenze definiert - aber wenn wir in die Grenze der Domäne, ist dieser Punkt nicht das gewünschte Extremum: Der Job ist noch nicht fertig. Stattdessen können wir einem anderen Weg folgen, zum Beispiel die Lösungen von progressiv kleineren Werten von tau0. Wir brauchen nicht die genaue Lösung von jedem dieser Zwischenprobleme: eine Approximationslösung reicht oft aus. Sequentielle quadratische Programmierung (SQP) Wir können unseren eigenen nichtlinearen, beschränkten Optimierer rollen. Es klingt wie eine hohe Ordnung, aber es ist eigentlich ziemlich einfach. Wir wollen das Problem lösen, bei dem f, g und h reibungslose Funktionen sind. Wenn wir in der Dimension 1 waren, um f (x) ohne Einschränkungen zu minimieren, würden wir mit einer anfänglichen Schätzung x beginnen, die durch ihre Taylor-Erweiterung zweiter Ordnung f angenähert, minimiert und wieder mit dem neuen Wert für x beginnt Konvergenz. In der Dimension n mit Einschränkungen können wir dasselbe tun: mit einer anfänglichen Vermutung x beginnen, das Ziel f durch seine Taylor-Erweiterung ersetzen, die Beschränkungen g und h durch die erste Taylor-Erweiterung ersetzen und das resultierende quadratische Programm lösen , Wieder mit dem neuen Wert für x beginnen und bis zur Konvergenz fortfahren. Dies wird als sequentielle quadratische Programmierung bezeichnet. Wir verwenden diese Funktion, um das folgende maximale Entropieproblem zu lösen. Hier ist ein weiteres Beispiel. Wir haben eine nn-Matrix, wir kennen die Summe der Zeilen, die Summe der Spalten, wir kennen einige ihrer Elemente. Füllen Sie die fehlenden Werte so einheitlich wie möglich aus, d. h. füllen Sie die fehlenden Werte aus, um die Entropie zu maximieren - äquivalent, um die Kullback-Leibler-Divergenz mit der gleichmäßigen Verteilung zu minimieren. SQP arbeitet gut für konvexe Probleme (streng konvexe Probleme, für diese Implementierung, da wir uns auf quadprog verlassen). Sie können Rsolnp bevorzugen, die auch reasobaly gut auf vielen nicht-konvexen Problemen funktionieren. Stochastische Algorithmen Die bisherigen Algorithmen beschränken sich auf gut erarbeitete Probleme: Sie funktionieren gut für konvexe Probleme, für die es keine lokalen Extrema gibt, uns zu täuschen. Hier sind ein paar Optimierungsalgorithmen robuster gegenüber lokalen Extrema. Da sie nicht mit Einschränkungen umgehen können, können Sie sie in Sanktionen umwandeln (Soft Constraints). Das simulierte Glühen erforscht den realisierbaren Raum, nach dem Zufallsprinzip, nicht unähnlich zum Gradientenabfall, aber nicht immer bergab: um lokale Extrema zu vermeiden, akzeptiert er manchmal Lösungen, die schlechter sind als die aktuelle. Die Wahrscheinlichkeit, eine Lösung schlechter zu akzeptieren als die aktuelle, hängt davon ab, wie schlecht diese Lösung ist und die Wahrscheinlichkeit schrittweise abnimmt, während der Algorithmus fortschreitet. Es kann sehr langsam sein. Die Schwellenwertsuche ist ähnlich, aber die Entscheidung, eine Lösung schlechter als die aktuelle zu akzeptieren, ist deterministisch, basierend auf einer Schwelle, die mit dem Fortschreiten des Algorithmus abnimmt. Differential Evolution ist ein Populations-basierter Algorithmus: Wir verfolgen eine Population potenzieller Lösungen und mischen sie bei jedem Schritt zur nächsten Generation. Wenn x1, x2, x3 Elemente der aktuellen Population sind, haben die Nachkommen die Form Particle Swarm-Optimierung ist ein weiterer populationsbasierter Algorithmus, bei dem sich die Lösungen sowohl in Richtung des Gradienten als auch aufeinander zu bewegen. Genetische Algorithmen können auch verwendet werden, aber die Art, wie sie kombinieren Lösungen (Crossover) funktioniert besser, wenn die Koordinaten unabhängig oder in einer sinnvollen Reihenfolge sind. Sie können durch Hinzufügen einer lokalen Suche nach jedem Schritt verbessert werden. Auf dem Weg zu einer benutzerfreundlicheren Schnittstelle Um ein Optimierungsproblem in ein quadratisches Problem umzuwandeln (zum Beispiel die Absolutwerte zu löschen, wie in unserem Beispiel für die Quantilregression), ist das Schreiben der entsprechenden Matrizen einfach, aber äußerst umständlich. Die Situation ist nicht anders als die von Regressionsmodellen: archaische Software nicht in der Lage, mit qualitativen Variablen befassen den Benutzer, um die Modell-Matrix, mit Dummy-Variablen, von Hand zu schaffen. Matlab-Benutzer können bereits Optimierungsprobleme benutzerfreundlich angeben. Könnten wir etwas Ähnliches für R haben, wollen wir Optimierungsprobleme angeben, z. B. wie folgt. Es ist nicht so schwierig wie es scheint. (Der unten stehende Code ist nur ein Beweis für das Konzept: es wurde nicht stark getestet, ist bekannt, in einigen Fällen scheitern, ist auf einige Arten von Problemen beschränkt, und es ist sehr langsam.) Die Unbekannten sind nur Strings, mit einem Spezifische Klasse, so dass wir die Funktionen und Operatoren, die wir benötigen, überladen können. Die Funktionen - sum bilden zunehmend komplexere Ausdrücke als Strings. Die Maximierungs - und Minimierungsfunktionen und die lt-Operatoren nehmen einen Ausdruck (einen String) auf, analysieren ihn (unter Verwendung von yacas), extrahieren die linearen und quadratischen Teile (im Falle eines linearen oder quadratischen Problems) und speichern sie in globalen Variablen, Die schließlich von der Lösungsfunktion verwendet werden. Funktionen wie abs oder CVaR fügen neue Variablen hinzu und werden durch lineare Ausdrücke ersetzt. Dies ist gültig, solange das Problem konvex bleibt, aber ich überprüfe nicht, dass es der Fall ist. Der heikle Teil ist die Umwandlung der Ausdrücke haben wir (als Zeichenfolgen) in die Matrizen von Quadprog oder Rglpk erwartet. Ich verlasse mich auf Maxima für diese Aufgabe (Sie müssen es zuerst installieren) und kommunizieren mit ihm über Named Pipes (Sie benötigen ein Betriebssystem, das Named Pipes). Beispiele für die Portfoliooptimierung Für die Beispiele verwenden wir die wöchentlichen Renditen für eine Handvoll Aktien. Um zu überprüfen, wie die Dinge skalieren, wenn das Universum ist größer, hier ist ein realistischer Datensatz. Gleichgewichtet Das Portfolio-Optimierungsproblem ist das Problem, die optimalen Gewichte eines Portfolios zu finden, d. h. wie viel Sie in jedes Vermögen investieren sollten, um eine gewisse Menge zu maximieren (oftmals ein Maß für eine risikoadjustierte Rendite). Wenn Sie keine Informationen über die Vermögenswerte (oder realistischerweise alle zuverlässigen Informationen) haben, können Sie jedem Vermögenswert das gleiche Gewicht zuordnen: Dies maximiert die Entropie (ein Maß für die Diversität) der Gewichte. Mittelwert-Varianz Die Mittel-Varianz-Portfolien maximieren die risikoadjustierten erwarteten Erträge des Portfolios. Die Risikoanpassung richtet sich nach der Risikoaversion des Anlegers (informell, dies entspricht lambda, in der Formel). Als ein Maß für das Risiko, können wir die Varianz der Portfolio-Renditen, aber es gibt viele andere Möglichkeiten. Minimale Abweichung Anstatt die risikoadjustierten Renditen zu betrachten, können wir nur auf das Risiko schauen - es ist viel einfacher, zukünftiges Risiko als zukünftige Renditen vorherzusagen. Effiziente Grenzen Es gibt mehrere Möglichkeiten, die Portfolios auf der effizienten Grenze zu identifizieren: Sie entsprechen der Minimierung des Risikos für eine festgelegte erwartete Rendite, die Maximierung der Renditen für ein festes Risikobudget und die Maximierung der risikoadjustierten Renditen. Leider, wie Sie mehr Einschränkungen hinzufügen (vollständig investiert, keine Leerverkäufe, Gewichtsgrenzen für jeden Sektor, Gewichtsgrenzen für jeden Vermögenswert, Begrenzung der Anzahl der Vermögenswerte, Losgrößen, etc.), die Form der machbaren Region ändert sich und muss Nicht konvex bleiben: diese Probleme sind nicht mehr gleichwertig. Zufällige Portfolios Eine sehr naive Methode, ein (nahezu) optimales Portfolio zu finden, für eine willkürliche Zielfunktion wäre, viele Portfolios zufällig zu nehmen und das beste zu halten. Zuerst scheint es eine sehr schlechte Idee: Wir scheinen anscheinend nur aus Portfolios rund um das gleichgewichtete Portfolio zu sampeln. Aber es gibt viele Dinge, die wir falsch machen. Erstens, wenn wir gleichmäßig verteilte Zahlen nehmen und sie durch ihre Summe dividieren, haben wir nicht gleichmäßig verteilte Zahlen in der Simplexsumme (w) 1: es gibt eine Vorspannung zur Mitte des Simplex. Sie verschwindet, wenn wir stattdessen eine exponentielle Verteilung verwenden: Wir sind jetzt viel näher an der effizienten Grenze. Wir wollen nicht wirklich gleichmäßig aus dem Simplex probieren: optimale Portfolios neigen dazu, irgendwo an der Grenze zu liegen. Eine gewisse Kraft der Gewichte wird die Daten gegen die Ecken und Kanten vorspannen. (Der Wert ist ein wenig zu hoch, so dass wir auf der Handlung sehen können, was tatsächlich passiert.) Wir könnten die Dinge weiter verbessern, indem wir niederdiskrepierende Sequenzen verwenden. Mit mehr Aktien, möchten Sie vielleicht den Exponenten zu erhöhen, aber nicht zu viel, sonst sind die meisten Portfolien auf einer einzigen Aktie konzentriert. Long-Short-Constraints Das unbeschränkte Long-Short-Portfolio hat einen übermäßigen Hebel. Wir können die Hebelwirkung in der gleichen Weise steuern, wie wir die Quantilregression implementiert haben: Schreiben Sie die Portfoliogewichte als wi ai-bi mit a und b positiv. Transaktionskosten Transaktionskosten können als Strafe der Zielfunktion hinzugefügt werden. Am leichtesten zu lösen ist eine L2-Strafe: das Problem bleibt quadratisch. Aber eine lineare Strafe ist realistischer. Wir können den absoluten Wert wie gewöhnlich loswerden, indem wir sein Argument als Differenz zweier Zahlen schreiben. Tangentiales Portfolio (Maximum Sharpe Ratio) Wir konnten zunächst alle Portfolios auf der effizienten Grenze berechnen und dann die Tangenten unter ihnen finden. Aber das ist eine Menge von Berechnungen, wenn Sie nur ein Portfolio wollen (um so mehr, wenn es viele Vermögenswerte). Alternativ können wir einen nicht-linearen Optimierer (auf den ersten Blick, Maximierung der Sharpe-Verhältnis sieht nicht wie ein quadratisches Problem). Aber es ist kein konvexes Problem: Es gibt keine Garantie, dass die Lösung, die wir erhalten, ein globales Maximum ist. Es stellt sich heraus, dass das Problem, das tangentiale Portfolio zu finden, als quadratisches Problem wie folgt umformuliert werden kann. Das Tangentenportfolio ist auch das maximale Sharpe-Ratio-Portfolio, bei dem die Sharpe-Ratio w mu sqrt (w V w) unter den vollständig investierten Portfolios liegt (die Gewichte sollten sich auf 1 belaufen). Lassen Sie uns die Einschränkung, dass die Gewichte bis zu 1. Es gibt nicht mehr eine eindeutige Lösung für das Problem: da das Verhältnis Anteil unverändert, wenn wir die Gewichte mit einer ungleichen Zahl multiplizieren (es ist homogen von Grad 0) Die maximalen Sharpe-Ratio-Portfolios bilden eine Linie - sobald wir ein Portfolio kennen, können wir die anderen durch Multiplikation mit einem Skalar erhalten. Um eine einzige Lösung zu haben, können wir eine Bedingung auf die Gewichte auferlegen. Zum Beispiel können wir bitten, dass der Zähler der Anteilsverteilung 1 ist. Dann müssen wir 1sqrt (w V w) maximieren, d. h. w v w minimieren: das ist ein quadratisches Problem. Szenario-basierte Optimierung: Minimum CVaR Der Bedingte Value at Risk (CVaR), auch als erwarteter Fehlbetrag (ES) bezeichnet, ist der erwartete Verlust, da der Verlust über einem gewissen Schwellenwert liegt. Die Schwelle ist gewöhnlich ein Quantil der Verteilung der Rückkehr, z. B. Das 5-Quantil oder das 1-Quantil. Wir können den erwarteten Fehlbetrag als ein Maß für das Risiko verwenden. Wenn wir die Verteilung der Renditen wüssten, wäre das einfach ein nichtlineares Optimierungsproblem. Rückgabewerte sind jedoch nicht gaußsch. (Wir könnten andere parametrische Verteilungen verwenden.) Anstelle einer parametrischen Verteilung können wir die empirische Verteilung der Retouren verwenden. Zunächst müssen wir den (sample) erwarteten Fehlbetrag als Optimierungsproblem ausdrücken. Es ist das Minimum, über u, Das Optimierungsproblem wird ein bisschen chaotisch (wenn Sie irgendwo einen Fehler machen, z. B. mit dem Vorzeichen der schlaffen Variablen, ist der Bug extrem zeitaufwendig, um aufzuspüren). Um sicherzustellen, dass wir tatsächlich den erwarteten Fehlbetrag minimieren, vergleichen wir mit einer direk - ten Optimierung. In ähnlicher Weise könnten wir dem CVaR eine Einschränkung hinzufügen. Szenario-basierte Optimierung: VaR Der Value at Risk (VaR) ist nur ein Quantil der Renditeverteilung - er wird jedoch als Verlust ausgedrückt, so dass das Vorzeichen unterschiedlich ist. Es kann folgendermaßen ausgedrückt werden: Da es sich um ein Minimum handelt, kann es in der objektiven Funktion eines Optimierungsproblems verwendet werden, wie wir es für den CVaR getan haben. Unglücklicherweise machen die Indikatorfunktionen (die mit binären Variablen codiert werden können) das Optimierungsproblem (nicht konvex und) ziemlich schwer zu lösen. Wir können einen robusten Optimierer verwenden, z. B. DEoptim. Branch-and-bound: Binäre Variablen und Kardinalitätseinschränkungen Das Hinzufügen der Einschränkung, dass einige der Variablen binär sind, d. h. nur zwei Werte, 0 oder 1 nehmen können, macht das Problem noch kombinatorischer. Wenn es n solche binären Variablen gibt, können wir die 2n Probleme lösen, die allen ihren möglichen Werten entsprechen. Das ist natürlich zu viel, aber wir können die Anzahl der zu lösenden Probleme reduzieren, indem wir sie in einem Baum anordnen, eine Bindung an den Wert jedes Teilbaums finden und alle Teilbäume wie folgt beschneiden. Die Wurzel des Baums entspricht dem unbeschränkten Problem: Die binären Variablen sind nur auf 0,1 begrenzt, aber sie müssen keine Ganzzahlen sein. Es gibt zwei Kinderknoten, die jeweils eine Einschränkung für die erste binäre Variable hinzufügen: sie ist entweder 0 oder 1 (die anderen Variablen bleiben in 0,1). Die nächste Schicht des Baums (4 Knoten) fügt Zwangsbedingungen für die zweite Variable hinzu, und so weiter. Wir suchen das Blatt mit der besten Lösung. Da die Knoten weniger strenge Beschränkungen haben als die Blätter, ist ihre Lösung besser, aber niemals schlechter, dass die Blätter darunter: Wenn der Wert eines Knotens schlechter ist als die beste Blattlösung, die bisher gefunden wurde, besteht keine Notwendigkeit, Teilbaum, und es kann beschnitten werden. Im folgenden Beispiel betrachten wir das Problem, das Minimum-Varianz-Long-Only-Portfolio mit maximal 5 Assets zu finden. The problem can be written as Let us first write functions to add constraints and solve the problem (so that the code can be reused with other solvers). Branch-and-bound: Integer variables and lot sizes The same idea can be used to handle integrality constants: at each node, we split the tree into 3 subtrees, corresponding to the constraints xiv (where v is some integer value, e. g. the integer closest to the solution of the unconstrained problem), xi v1 and xi lt v-1. The tree can be much larger than in the binary case: only when we add an equality constraint does the number of variables to decide on decrease. (In most cases, the xi are bounded, so that the tree is finite.) The algorithm can be improved: you can split the nodes in 2 rather than 3, you can carefully choose the variable to split on, you can use better heuristics to find a good upper bound on the minimum, you can add constraints to shrink the set of feasible solutions (branch-and-cut). Equal contribution to risk The risk of a portfolio, is homogeneous of degree 1, and can therefore be decomposed as where the marginal contribution to risk (MCTR) of asset i can be computed as Let us check on an example: It is easy to find portfolios with equal marginal contribution to risk. It is not really an optimization problem, but just a system of equations to solve. If r is the vector of desired marginal contributions to risk (up to a multiplicative constant), we want w (and lambda) such that In a risk parity portfolio, the assets have the same contribution to risk (the contribution to risk is wMCTR). They are a special case of risk budgeting portfolios, where the contribution to risk of each asset is imposed. It is still a system of equations to solve, but it is not linear: if ri is the desired contribution to risk of asset i, we want to find w so that where the risk is the sum of the contributions to risk. This can be written as where. is the elementwise product. (It is a quadratic equation: no easy solution.) We can use a non-linear solver. Since the problem is not convex, you may want to try other optimizers (e. g. DEoptim). Conclusion What we talked about We have presented the algorithms behind commonly-used optimization routines. They fall into three broad categories: gradient-like methods, that try to find a direction in which the objective function is better (with many variants, some eschewing the gradient (Nelder-Mead), some using a biased gradient (conjugate gradient), some using the hessian, some approximating the hessian (L-BGFS), some using the specific form of the objective function to simplify the computations (Gauss-Newton, Levenberg-Marquardt)) combinatorial methods, that explore on the frontier of the feasible set, from vertex to vertex (or from facet to facet), to improve the objective function (simplex, generalized reduced gradient) interior point methods, that regularize the Kuhn-Tucker conditions g lambda 0 into g lambda tau, and let the regularization parameter tau decrease. We have presented some code to add binary or integral constraints to an arbitrary optimization problem and code to allow us to enter optimization problems in a human-readable form. We have given a few portfolio optimization examples: minimum variance, mean-variance, CVaR, VaR, prescribed contribution to risk, using a variety of optimization algorithms, including random portfolios. We saw that, for real-world problems, different optimizers may give different results: it is safer to use several optimizers (some lack robustness, some lack speed, some are user-unfriendly and their use is therefore bug-prone), check that the constraints are satisfied (especially if you have to transform the problem by hand to give it to the optimizer) and compare with some base-line algorithm (e. g. random portfolios). What we did not talk about I focused on the algorithms, without stressing how careful one should be when using them in a financial context. You need to check if the purportedly optimal portfolios are indeed close to optimal, out-of-sample -- and you need to clearly define what you mean by optimal. This will not only depend on the optimization problems, but also on the estimators of variance and returns used. You should check how sensitive those optimization problems are to their inputs. You should also carry out a complete backtest, to check how consistent the resulting portfolios are over time: is their out-of-sample performance independent of the market regime do they generate an excessive turnover I did not mention the use of copulas, volatility models, (semi-)parametric estimators of VaR and CVaR, spectral risk measures, drawdown. I intended to but did not mention second order cone programming and semi-definite programming, which generalize quadratic programming, and can be used for quadratic constraints and robust optimization (i. e. situations where you do not have a single number for the variances and expected returns, but intervals). There is an Rcsdp package, but the documentation is scarce (only one example), the error messages cryptic, and the licence non-standard.
No comments:
Post a Comment