- Ein Lehrbuch, das die Prinzipien der mathematischen Optimierung und das gesamte Spektrum der Algorithmen systematisch behandelt und sowohl kontinuierliche als auch diskrete Probleme abdeckt
- Erläutert schrittweise verschiedene Ansätze, von ableitungsbasierten Verfahren bis hin zu stochastischen und evolutionären Methoden
- Enthält mathematische Strukturen, die für praktische Anwendungen wichtig sind, darunter Nebenbedingungen, Dualität sowie lineare und quadratische Programmierung
- Jedes Kapitel bietet Zusammenfassungen und Übungsaufgaben, sodass Lernen und Praxis parallel möglich sind
- Veröffentlicht unter der Open License von MIT Press (CC BY-NC-ND)
Vorwort und Überblick
- Dieses Buch ist ein Lehrwerk über Theorie und Implementierung von Algorithmen zur Lösung von Optimierungsproblemen und erscheint in der 2. Auflage
- Die Autoren sind Mykel J. Kochenderfer und Tim A. Wheeler
- Erschienen bei MIT Press und veröffentlicht unter einer Creative-Commons-Lizenz für nichtkommerzielle Nutzung ohne Bearbeitungen
- Nach Vorwort und Danksagung ist das Buch in 13 Kapitel gegliedert
- Jedes Kapitel folgt einer lernorientierten Struktur aus Kernkonzepten, Zusammenfassung und Übungsaufgaben
Kapitel 1. Einführung
- Stellt Geschichte, Ablauf, mathematische Formulierung und Anwendungsgebiete der Optimierung vor
- Erklärt Extremwerte (minima) und Optimalitätsbedingungen (optimality conditions)
- Enthält Überblick, Zusammenfassung und Übungsaufgaben für das gesamte Buch
Kapitel 2. Ableitungen und Gradienten
- Erläutert Definition und Berechnung von Ableitungen für eine und mehrere Variablen
- Beinhaltet Verfahren der numerischen Differentiation (numerical differentiation) und der automatischen Differentiation (automatic differentiation)
- Behandelt Regressionsgradienten und stochastische Approximationsverfahren (SPSA)
Kapitel 3. Bracketing
- Erklärt das Konzept der Unimodalität (unimodality) und das Verfahren zum Finden eines Anfangsintervalls
- Enthält intervallbasierte Algorithmen wie Fibonacci-Suche, Goldener-Schnitt-Suche und quadratische Approximationssuche
- Einschließlich Shubert-Piyavskii- und Bisektionsverfahren (bisection)
Kapitel 4. Lokaler Abstieg (Local Descent)
- Erläutert die Konzepte Iteration in Abstiegsrichtung (descent direction iteration) und Schrittweite (step factor)
- Beinhaltet Line Search und approximative Line-Search-Verfahren
- Behandelt Trust-Region-Ansätze und Abbruchbedingungen
Kapitel 5. Verfahren erster Ordnung (First-Order Methods)
- Enthält wichtige Verfahren wie Gradient Descent, konjugierte Gradienten, Momentum und Nesterov-Momentum
- Umfasst moderne Optimierungsalgorithmen wie AdaGrad, RMSProp, Adadelta, Adam und Hypergradient Descent
- Bietet Eigenschaften und vergleichende Zusammenfassungen der einzelnen Methoden
Kapitel 6. Verfahren zweiter Ordnung (Second-Order Methods)
- Erläutert Newton’s Method und die Sekantenmethode (Secant Method)
- Beinhaltet den Levenberg-Marquardt-Algorithmus sowie Quasi-Newton-Verfahren
- Schließt mit Zusammenfassung und Übungsaufgaben
Kapitel 7. Direkte Methoden (Direct Methods)
- Stellt Koordinatensuche, Powell, Hooke-Jeeves, Pattern Search und die Nelder-Mead-Simplex-Methode vor
- Enthält das Verfahren Divided Rectangles
- Schwerpunkt auf Optimierungsansätzen ohne Ableitungen
Kapitel 8. Stochastische Methoden (Stochastic Methods)
- Behandelt stochastische Ansätze wie Noisy Descent, Mesh Adaptive Search und derivative-free optimization
- Umfasst Simulated Annealing, Cross-Entropy, Natural Evolution Strategies und Covariance Matrix Adaptation (CMA)
- Hebt die Effizienz wahrscheinlichkeitsbasierter Suche hervor
Kapitel 9. Populationsbasierte Methoden (Population Methods)
- Erläutert Verfahren der populationsbasierten Suche wie genetische Algorithmen, Differential Evolution und Particle Swarm Optimization (PSO)
- Enthält Firefly, Cuckoo Search und hybride Methoden
- Löst Probleme über eine Struktur der Populationsiteration (population iteration)
Kapitel 10. Nebenbedingungen (Constraints)
- Erläutert Grundkonzepte der constrained optimization und verschiedene Arten von Nebenbedingungen
- Beinhaltet Lagrange-Multiplikatoren, Slack-Variablen sowie Penalty- und Interior-Point-Methoden
- Behandelt Transformationen zur Eliminierung von Nebenbedingungen und die Method of Multipliers
Kapitel 11. Dualität (Duality)
- Erläutert das duale Problem (dual problem) und Primal-Dual-Methoden
- Beinhaltet Dual Ascent und ADMM (Alternating Direction Method of Multipliers)
- Behandelt Anwendungen in der verteilten Optimierung (distributed methods)
Kapitel 12. Lineare Programmierung (Linear Programming)
- Erläutert Problemformulierung, den Simplex-Algorithmus (Simplex Algorithm) und duale Zertifikate (dual certificates)
- Stellt die Struktur der Optimierung unter linearen Nebenbedingungen systematisch dar
Kapitel 13. Quadratische Programmierung (Quadratic Programming)
- Problemformulierung mit quadratischer Zielfunktion und linearen Nebenbedingungen
- Behandelt Least-Squares-Probleme und lineare Ungleichungsnebenbedingungen
- Enthält Least Distance Programming
Anhang und weitere Informationen
- Am Ende jedes Kapitels finden sich Zusammenfassung und Übungsaufgaben
- Veröffentlicht von MIT Press als Ausgabe 2025, nichtkommerzielle Weitergabe erlaubt (CC BY-NC-ND)
- LaTeX-basierter Satz, Kontakt über bugs@algorithmsbook.com
4 Kommentare
Im Moment ist es nicht zugänglich T_T
https://algorithmsbook.com/optimization/#download
Anscheinend hat sich der Link inzwischen etwas geändert; hier kann man sich das PDF ansehen oder herunterladen.
Vielen Dank!!
Hacker-News-Kommentare
Es ist schön zu sehen, dass das Thema Optimierung (optimization) es auf die HN-Startseite geschafft hat.
Ich möchte meine LP-Visualisierungsseite vorstellen. Dort kann man visuell sehen, wie Algorithmen der linearen Programmierung auf Änderungen bei Nebenbedingungen oder der Zielfunktion reagieren.
Auf der Demo-Seite wird automatisch ein Polygon gezeichnet, und man kann die Iterationen des Algorithmus beobachten, während man Ecken oder Nebenbedingungslinien verschiebt.
Es ist noch nicht besonders ausgereift, aber für Leute, die visuelles Lernen mögen, dürfte es Spaß machen. Feedback ist willkommen.
Ich möchte einige Materialien zu Metaheuristiken (metaheuristics) teilen.
Bei Timefold, wo ich arbeite, nutzen wir Algorithmen aus diesen Büchern wie Tabu Search und Simulated Annealing, um schnell näherungsweise optimale Lösungen zu finden.
Sehenswert ist auch das Diagramm zu lokalen Suchalgorithmen in der Timefold-Dokumentation.
Das ist ein Optimierungslehrbuch mit CC-Lizenz auf 521 Seiten, und es sieht wirklich hervorragend aus.
Am Anfang behandelt es moderne gradient-based Algorithmen auf Basis automatischer Differenzierung, etwa Adam, und im späteren Teil (Kapitel 12) lineare Optimierung wie das Simplex-Verfahren.
Es gibt auch viele Übungsaufgaben, und es ist genau die Art von Buch, auf die ich lange gewartet habe.
Ich denke, Optimierungsalgorithmen lösen nicht einfach nur Probleme, sondern sind ein Versuch in Richtung eines „allgemeinen Problemlösers“. Das Programm findet die Antwort nicht direkt, sondern man definiert, wie eine Lösung aussehen soll, und wendet darauf Optimierung an.
Auch heutige KI basiert auf diesem Ansatz.
Dieses Buch von Kochenderfer und sein früheres Werk Decision Making Under Uncertainty(PDF) gehören zu meinen liebsten Fachbüchern.
Die Erklärungen sind klar, die Visualisierungen hervorragend, und es behandelt verschiedene Denkweisen zur Optimierung jenseits von gradient descent.
Der Code ist zwar in Julia geschrieben, lässt sich aber nicht schwer in andere Sprachen übertragen. Man sollte sich nicht an der Sprache festbeißen, sondern auf die Konzepte konzentrieren.
Optimierung ist nicht nur eine Technik, sondern eine Denkweise zum Lösen schwieriger Probleme.
Dieses Buch ist eine seltene Quelle, die CMA-ES, surrogate model, Gaussian process und Ähnliches in einem einzigen Band behandelt.
In meiner Zeit als Forschungsstudent hätte mir so ein Buch sehr geholfen. Früher war dieses Wissen über viele Papers und Bücher verstreut.
Während meiner Promotion habe ich dieses Buch mehrfach gründlich gelesen. Ich habe zu neuronalen Netzen und numerischer Analysis geforscht, und das Verhältnis von Tiefe und Breite ist hier sehr gut ausbalanciert.
Ich nutze es auch heute noch oft als Nachschlagewerk.
Ich war überrascht zu sehen, dass das Buch Metaheuristiken wie Firefly und Cuckoo Search enthält.
Diese Algorithmen genießen in der Wissenschaft kein Vertrauen und wurden auch im ITOR-Paper kritisiert.
Es gibt kleine Communities, die nur auf diese Ansätze fokussiert sind, sich gegenseitig zitieren und dabei eine Art Blase bilden. Auch auf Konferenzen sorgt das gelegentlich für Kontroversen.
Das Kapitel zu Mehrzieloptimierung (multiobjective optimization) war hervorragend.
Ich frage mich, ob es andere Bücher oder Materialien gibt, die sich speziell auf dieses Thema konzentrieren.
Ich würde gern einen Vergleich zwischen diesem Buch und Nocedal & Wrights Numerical Optimization sehen.