Planung: Dr. Annika Denkert
Springer Spektrum ist Teil von Springer Nature
Die eingetragene Gesellschaft ist Springer-Verlag GmbH Deutschland
Die Anschrift der Gesellschaft ist: Heidelberger Platz 3, 14197 Berlin, Germany
Here we are now, entertain us.
(Marc-Uwe Kling)
Dieses Lehrbuch ist aus dem Skript zu meiner Vorlesung „Nichtlineare Optimierung I und II“ entstanden, die ich am Karlsruher Institut für Technologie seit 2006 jährlich halte. Die Adressaten dieser Vorlesung sind in erster Linie Studierende des Wirtschaftsingenieurwesens im Bachelor-Vertiefungsprogramm. Im vorliegenden Lehrbuch spiegelt sich dies darin wider, dass mathematische Sachverhalte zwar stringent behandelt, aber erheblich ausführlicher motiviert und illustriert werden als in einem Lehrbuch für einen rein mathematischen Studiengang. Das Buch richtet sich daher an Studierende, die mathematisch fundierte Verfahren in ihrem Studiengang verstehen und anwenden möchten, wie dies etwa in den Natur-, Ingenieur- und Wirtschaftswissenschaften der Fall ist. Da die ausführlichere Motivation naturgemäß auf Kosten des Stoffumfangs geht, beschränkt dieses Buch sich auf die Darstellung von Grundzügen der nichtlinearen Optimierung.
Gegenstand ist die Behandlung von Minimierungs- oder Maximierungsmodellen mit nichtlinearen Zielfunktionen unter nichtlinearen Nebenbedingungen, wie sie in Anwendungsdisziplinen sehr oft auftreten. Für solche Probleme leiten wir Optimalitätsbedingungen her und geben darauf basierende numerische Lösungsverfahren an.
Eine Gemeinsamkeit aller dieser Optimalitätsbedingungen besteht darin, dass sie auf der Auswertung von ersten bzw. zweiten Ableitungen der beteiligten Funktionen beruhen. Während dies die Optimalitätsbedingungen einerseits häufig leicht handhabbar macht, leiden sie andererseits unter dem grundsätzlichen Problem, dass Ableitungen die Gestalt von Funktionen nur lokal wiedergeben, aber nicht global. Entsprechend sind die auf diesen Optimalitätsbedingungen basierenden Lösungsverfahren lediglich in der Lage, lokale Optimalpunkte zu identifizieren. Nur in Ausnahmefällen sind diese auch globale Optimalpunkte.
Die Bestimmung globaler Minimalpunkte ist zwar ebenfalls oft algorithmisch möglich, der dazu nötige Aufwand ist üblicherweise aber um eine Vielfaches höher als derjenige zur Bestimmung lokaler Minimalpunkte. Ausnahme sind die sogenannten konvexen Optimierungsprobleme, bei denen jeder lokale Optimalpunkt automatisch auch globaler Optimalpunkt ist. Solche Optimierungsmodelle sowie Algorithmen zur Bestimmung globaler Optimalpunkte nichtkonvexer Probleme werden ausführlich in [33] besprochen.
Im vorliegenden Text stellen wir uns hingegen auf den Standpunkt, dass in Anwendungen häufig bereits die Kenntnis lokaler Optimalpunkte wertvoll ist, zumal, wenn sie sich verhältnismäßig schnell berechnen lassen. Die hier besprochenen Techniken sind außerdem nicht unabhängig von denen der globalen Optimierung zu sehen, sondern sie kommen dort häufig zum Einsatz, um etwa gewisse Hilfsprobleme zu lösen [33].
Bevor man sich mit der theoretischen und numerischen Identifizierung von lokalen Optimalpunkten befasst, ist es allerdings wichtig zu klären, ob ein Optimierungsproblem überhaupt Optimalpunkte besitzt. Das einführende Kap. 1 geht neben grundlegender Terminologie und Notation daher auf einige hinreichende Bedingungen für Lösbarkeit ein.
Kap. 2 konzentriert sich auf nichtlineare Optimierungsprobleme ohne Nebenbedingungen und leitet für sie zunächst Optimalitätsbedingungen her, die auf ersten und zweiten Ableitungen der Zielfunktion basieren. Die dabei entstehenden Vereinfachungen im Fall der Minimierung einer konvexen Zielfunktion werden kurz angerissen. Auf Grundlage der Optimalitätsbedingungen formulieren und diskutieren wir dann eine Reihe wichtiger numerischer Verfahren – von dem der Mitte des 19. Jahrhunderts entstammenden Gradientenverfahren bis hin zu den modernen Trust-Region-Verfahren.
Kap. 3 erweitert die betrachteten Optimierungsmodelle um nichtlineare Nebenbedingungen. Die Herleitung aussagekräftiger Optimalitätsbedingungen erfordert hier allerdings erheblich höheren Aufwand als im unrestringierten Fall aus Kap. 2 . Dies liegt darin begründet, dass die Lage von Optimalpunkten einerseits nur von der Geometrie der Menge zulässiger Punkte abhängt, verschiedene funktionale Beschreibungen dieser Menge durch Nebenbedingungen aber andererseits zu unangenehmen Effekten in den jeweiligen Optimalitätsbedingungen führen können. Kap. 3 diskutiert diese Problematik ausführlich und leitet die entsprechenden Optimalitätsbedingungen her, bevor wir wieder diverse darauf basierende numerische Verfahren besprechen.
Dieses Lehrbuch kann als Grundlage einer vierstündigen Vorlesung dienen. Es stützt sich teilweise auf Darstellungen der Autoren W. Alt [1], M.S. Bazaraa, H.D. Sherali und C.M. Shetty [2], A. Beck [3], U. Faigle, W. Kern und G. Still [7], O. Güler [16], H.Th. Jongen, K. Meer und E. Triesch [23] sowie J. Nocedal und S. Wright [25], die auch viele über dieses Buch hinausgehende Fragestellungen behandeln. Zu Grundlagen der konvexen und globalen Optimierung sei wie erwähnt auf [33] verwiesen, und zu allgemeinen Grundlagen der Optimierung auf [24].
An dieser Stelle möchte ich Frau Dr. Annika Denkert vom Springer-Verlag herzlich für die Einladung danken, dieses Buch zu publizieren. Frau Bianca Alton und Frau Regine Zimmerschied danke ich für die hilfreiche Zusammenarbeit bei der Gestaltung des Manuskripts und beim Copy Editing. Ein großer Dank gilt außerdem meinen Mitarbeitern Dr. Tomáš Bajbar, Peter Kirst, Robert Mohr, Christoph Neumann, Dr. Marcel Sinske, Dr. Paul Steuermann und Dr. Nathan Sudermann-Merx sowie zahlreichen Studierenden, die mich während der Entwicklung dieses Lehrmaterials auf inhaltliche und formale Verbesserungsmöglichkeiten aufmerksam gemacht haben. Der vorliegende Text wurde in LaTeX2e gesetzt. Die Abbildungen stammen aus Xfig .
In kleinerem Schrifttyp gesetzter Text bezeichnet Material, das zur Vollständigkeit angegeben ist, beim ersten Lesen aber übersprungen werden kann.