Nichtlineare Optimierung erklärt
Ein zylindrischer Transportbehälter mit festem Volumen und einem Höhenlimit trägt die zweite Hälfte dieser Linie; die ersten drei Stücke laufen auf einer Quadratik mit regelbarer Konditionszahl und der Rosenbrock-Funktion. Gradientenabstieg ist die Wurzel: immer entlang des negativen Gradienten bergab. Newton nutzt zusätzlich die Krümmung (Hesse-Matrix), Quasi-Newton (BFGS/L-BFGS) schätzt sie nur noch aus Gradientendifferenzen. Ab Lagrange/KKT kommen Nebenbedingungen dazu: drei verschiedene Verfahren (Straf-/Barriere, SQP, Innere-Punkte) lösen danach dieselbe restringierte Aufgabe auf grundverschiedene Weise, jedes gegen dieselbe von Hand geprüfte Referenzlösung. Der zweite Ast direkt von der Wurzel behebt eine andere Ignoranz als der Newton-Ast: teure, verrauschte Gradienten: genau die Situation beim Training eines neuronalen Netzes, die Brücke zu Deep Learning und der Abschluss der Linie.
In short: Covers nonlinear optimization: gradient descent, Newton and quasi-Newton (BFGS) methods, Lagrange and KKT conditions, penalty and barrier methods, SQP, interior point and stochastic methods. Interactive demos report measured rather than claimed results.
Hintergrund zum Thema: Seefracht.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Gradientenabstieg verständlich erklärt
Warum man im Nebel immer dorthin geht, wo es am steilsten bergab geht, und warum die Länge der Schritte entscheidet, ob man ankommt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Formeln, Messwerten und Grenzen.
Die acht Stücke im Überblick
Die Linie hat eine Wurzel und zwei Äste. Gradientenabstieg ist die Wurzel; Newton behebt, dass er nur den Gradienten kennt, Quasi-Newton behebt, dass Newton die echte Hesse-Matrix braucht. Ab Lagrange/KKT (das nur charakterisiert, aber nicht selbst löst) verzweigt die Linie zu zwei Verfahren, die dasselbe restringierte Problem lösen: Straf-/Barriere über eine Folge unrestringierter Probleme, SQP direkt über eine Folge kleiner QP-Teilaufgaben. SQP führt weiter zu Innere-Punkte-Verfahren, die die je Iteration neu geratene aktive Menge durch ein gemeinsames Schlupf-System ersetzen.
Der zweite Ast zweigt direkt an der Wurzel ab: Stochastische Gradientenverfahren beheben nicht fehlende Krümmung, sondern teure, verrauschte Gradienten bei großem n: eine andere Ignoranz, keine Fortsetzung des ersten Astes.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
Straf-/Barriere und SQP haben denselben Vorgänger (Lagrange/KKT) und dieselbe Kantenbeschriftung, weil beide dieselbe Schwäche auf unterschiedliche Weise beheben. Keiner ist eine Vorstufe des anderen.
Verwandt in anderen Linien
- Neuronale Netze — Das Training eines neuronalen Netzes IST hochdimensionale, verrauschte, nichtkonvexe Optimierung: die MLP-Backprop-Demo der Neuronale-Netze-Linie fand auf XOR Adam vorn (9/10 gegen 7/10) und Momentum hinten (0/10). Die Stochastische-Gradientenverfahren-Demo hier prüft denselben Befund auf einer generischen Zielfunktion und findet ihn nur zur Hälfte bestätigt.
- Populations-Metaheuristiken — Diese Linie ist durchgehend ableitungsbasiert (Gradient, Hesse-Matrix); die Populations-Metaheuristiken-Linie löst verwandte Probleme ganz ohne Ableitungen. Wer Gradientenabstieg mit einem ableitungsfreien Gegenstück vergleichen will, findet in der Genetischer-Algorithmus-Demo die Wurzel der Populations-Metaheuristiken-Linie.
- Standortplanung — Gleicher Namensvetter, andere Technik: die Kapazitierte-Standortplanung-Demo der Standortplanung-Linie nutzt Lagrange-RELAXATION für diskrete Optimierung (eine duale Schranke über kombinatorische Teilprobleme), etwas anderes als die kontinuierliche Lagrange-Multiplikator-/KKT-Theorie der Lagrange/KKT-Demo hier.
- Ranking — Bradley-Terry löst die konkave Log-Likelihood der Paarvergleiche mit dem Newton-Verfahren.
- Kausale Diagramme und Adjustierung — NOTEARS der Linie Kausale Diagramme und Adjustierung lernt ein Diagramm als Optimierungsproblem mit einer Nebenbedingung, die nur azyklische Graphen zulässt, und löst es per erweitertem Lagrange-Verfahren: dem Multiplikator aus Lagrange/KKT und dem Strafterm der Straf-/Barriere-Verfahren in einem.
- Inverse Probleme und Regularisierung — In der Linie Inverse Probleme und Regularisierung löst die nichtlineare inverse Aufgabe (Anfangswert einer Wärmeleitung mit Reaktion) mit Gradientenabstieg, Gauss-Newton und Levenberg-Marquardt; der adjungierte Gradient kostet einen Vorwärtslauf statt eines je Parameter.
Gradientenabstieg: der erste Schritt bergab
Verfolgen Sie, wie der Gradientenabstieg immer entlang des steilsten Gefälles bergab geht, bis sich nichts mehr bessert. Die Demo variiert Konditionszahl (wie langgestreckt die Funktion ist) und Schrittweite, und eine zu große feste Schrittweite kippt in Divergenz. Der Haken: Die „sichere“ feste Schrittweite ist langsamer als Backtracking, und ab Konditionszahl 500 konvergiert im Budget nur noch Backtracking.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Newton-Verfahren: Krümmung nutzen
Verfolgen Sie, wie das Newton-Verfahren zusätzlich zur Steigung die Krümmung nutzt und eine Quadratik deshalb in genau einem Schritt löst, während der Gradientenabstieg hunderte braucht. Die Demo variiert den Startpunkt. Der Haken: Die Vermutung, Newton scheitere auf Rosenbrock fern vom Optimum, bestätigte sich nicht; die echte Divergenzschwelle zeigt erst die einfachere Funktion ln(1+x²).
Demo starten →Quasi-Newton (BFGS/L-BFGS): Krümmung schätzen
Sehen Sie, wie BFGS die Krümmung allein aus den Änderungen des Gradienten schätzt, statt die teure Hesse-Matrix zu berechnen, und L-BFGS sich dafür nur die letzten Schritte merkt. Die Demo vergleicht beide. Der Haken: Dass L-BFGS bei der Iterationszahl etwa BFGS entspricht, gilt nur bei niedriger Konditionszahl; bei Konditionszahl 500 braucht es mehr als das 25-Fache der Schritte.
Demo starten →Lagrange/KKT: Nebenbedingungen zum ersten Mal
Sehen Sie, wie die KKT-Bedingungen ein Optimum mit Nebenbedingungen als Gleichungssystem beschreiben, am Beispiel der Materialkosten eines zylindrischen Behälters bei festem Volumen und Höhenlimit. Ein Höhenlimit-Regler zeigt, wie der Multiplikator der Nebenbedingung exakt an der Grenzhöhe von null auf einen positiven Wert springt. Der Haken: SciPy meldet bei ungünstigem Startwert Erfolg, obwohl der Zielwert 1,86 % über dem Optimum liegt.
Demo starten →Straf-/Barriere-Verfahren
Verfolgen Sie, wie ein Straf-Verfahren mit wachsendem Strafgewicht und ein Barriere-Verfahren mit schrumpfender Barriere eine Aufgabe mit Nebenbedingungen als Folge unrestringierter Probleme lösen, bis beide die Referenzlösung der KKT-Rechnung treffen. Die Demo variiert das Strafgewicht. Der Haken: Die Konditionszahl wächst nicht immer unbeschränkt; sind beide Nebenbedingungen aktiv, bleibt sie endlich und erreicht 288,3.
Demo starten →SQP: Sequential Quadratic Programming
Sehen Sie, wie SQP an jedem Punkt eine kleine quadratische Näherung der Aufgabe löst und deren Lösung als nächsten Schritt nimmt. Die Demo vergleicht SQP mit den Straf- und Barriere-Verfahren: Im Standardfall braucht SQP 5 Iterationen bis Maschinengenauigkeit gegen 12 äußere Stufen bei gröberem Zielfehler. Der Haken: Von manchen Startpunkten konvergiert SQP zu einem gültigen, aber unsinnigen Punkt mit negativem Radius.
Demo starten →Innere-Punkte-Verfahren für NLP
Sehen Sie, wie ein Innere-Punkte-Verfahren Gleichungen, Ungleichungen und eine schrumpfende Barriere gemeinsam in einem Newton-System löst, statt die aktive Menge zu erraten. Die Demo vergleicht es mit dem Durchprobieren aller Fälle. Der Haken: Bei der realistischen Aufgabengröße ist das Durchprobieren nicht teurer; der Vorteil zeigt sich erst bei einer synthetisch erweiterten Zahl von Nebenbedingungen, bei 8 ist es 5,8-mal teurer.
Demo starten →Stochastische Gradientenverfahren: die Brücke zu Deep Learning
Verfolgen Sie, wie SGD, Momentum und Adam mit verrauschten Gradienten umgehen, wie beim Training eines neuronalen Netzes mit Mini-Batches. Die Demo variiert das Rauschen: Ohne Rauschen ist Momentum sogar schneller, bei starkem Rauschen verstärkt seine Geschwindigkeit das Rauschen und SGD gewinnt. Adam zeigt hier bei nur zwei Parametern keinen klaren Vorteil.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle acht Stücke, entlang der Frage, ob Nebenbedingungen vorliegen und wie teuer Gradient bzw. Krümmung sind. Alle Antworten stützen sich auf Messungen in den Demos.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: bei wenigen Ungleichungen (K≤3) ist die aktive-Menge-Enumeration in der Innere-Punkte-Demo selbst gemessen NICHT teurer als das Innere-Punkte-Verfahren. Der Baum folgt der klassischen Literatur-Einordnung nach Nebenbedingungszahl, nicht der hier gemessenen Kostenreihenfolge bei kleinen Instanzen.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.