Optimierung: Einführung in Mathematische Theorie Und Methoden

ISBN-13: 9783662588543 / Niemiecki / Miękka / 2019 / 520 str.

Florian Jarre; Josef Stoer

Opis

Dieses Buch führt in die Theorie und Methoden der stetigen Optimierung ein und zeigt darüber hinaus einige Anwendungen aus der diskreten Optimierung: Als gängige Verfahren für lineare Programme werden die Simplex- und Innere-Punkte-Methode vorgestellt. Im Bereich der nichtrestringierten Optimierung werden neben deterministischen Abstiegsverfahren und Trust-Region-Verfahren auch stochastische Abstiegsverfahren analysiert, die etwa beim maschinellen Lernen zum Einsatz kommen. Nach einer detaillierten Betrachtung der Optimalitätsbedingungen für nichtlineare Optimierungsprobleme mit Nebenbedingungen folgt eine Analyse von Verfahren der erweiterten Lagrangefunktion und ADMM sowie von SQP-Verfahren. Der Hauptteil schließt mit einer Betrachtung von semidefiniten Programmen und deren Anwendungen.Für die zweite Auflage wurden zahlreiche Passagen überarbeitet und mehrere neue Abschnitte zu aktuellen Verfahren und Anwendungen ergänzt.Das Buch basiert auf einer zweisemestrigen Lehrveranstaltung der Autoren und enthält zahlreiche Übungsaufgaben. Es richtet sich an Leser, die Grundkenntnisse in Analysis, linearer Algebra und numerischer Mathematik mitbringen.

Spis treści

1 Einleitung.- 1.1 Modellbildung, mathematische Formulierung.- 1.2 Nichtlineare Programme.- 1.3 Einteilung von nichtlinearen Programmen.- 1.4 Ausblick.- 1.5 Zur Anwendung in der Praxis.- I Lineare Programmierung.- 2 Lineare Programme, Beispiele und Definitionen.- 2.1 Definition und Anwendungen.- 2.2 Das Diätproblem.- 2.3 Beispiel zum Flugplanentwurf.- 2.4 Die Standardform.- 2.5 Geometrische Grundlagen.- 3 Das Simplexverfahren.- 3.1 Lineare Gleichungssysteme und Basen.- 3.2 Das spezielle Simplexformat.- 3.3 Durchführung der Simplexmethode.- 3.3.1 Benachbarte Basen.- 3.3.2 Abbruchkriterien.- 3.3.3 Geometrische Interpretation.- 3.3.4 Simplexschritt.- 3.3.5 Allgemeine Simplexmet.- 3.4 Die lexikographische Simplexmethode.- 3.5 Ein Hilfsproblem für den Startpunkt.- 3.6 Zusammenfassung.- 3.7 Dualität bei linearen Programmen.- 3.7.1 Der Dualitätssatz.- 3.7.2 Duale Simplexmethode.- 3.8 Beispiel für eine Sensitivitätsanalyse.- 3.9 Übungsaufgaben.- 4 Innere - Punkte - Methoden für Lineare Programme.- 4.1 Exkurs: Newton-Verfahren, Konvergenzraten.- 4.1.1 Anwendung: Newton-Verfahren.- 4.1.2 Konvergenzgeschwindigkeiten, O- Notation.- 4.2 Der Innere — Punkte-Ansatz.- 4.2.1 Das primal — duale System.- 4.2.2 Der zentrale Pfad.- 4.2.3 Newton-Verfahren für das primal-duale System.- 4.2.4 Lösung der linearen Gleichungssysteme.- 4.3 Analyse des Newton — Schrittes.- 4.4 Ein Kurz — Schritt — Algorithmus.- 4.5 Konvergenz von Innere — Punkte-Verfahren.- 4.6 Zur Konvergenzrate des Kurz — Schritt-Verfahrens.- 4.7 Ein praktisches Innere — Punkte-Verfahren.- 4.8 Ein Trick zur Berechnung von Startpunkten.- 4.8.1 Selbstduale lineare Programme.- 4.8.2 Zusammenhang mit anderen linearen Programmen.- 4.9 Übungsaufgaben.- 5 Lineare Optimierung: Anwendungen, Netzwerke.- 5.1 Das Transportproblem.- 5.1.1 Problemstellung und Grundbegriffe der Graphentheorie.- 5.1.2 Simplexverfahren zur Lösung des Transportproblems.- 5.2 Das Transshipment — Problem.- 5.3 Bestimmung kürzester und längster Wege in einem Netzwerk.- 5.3.1 Reduktion auf ein Transshipment — Problem.- 5.3.2 Die Methode von Dantzig.- 5.3.3 Der Algorithmus von Dijkstra.- 5.3.4 Die Methode von Fulkerson.- 5.4 Übungsaufgaben.- II Nichtlineare Minimierung I.- 6 Minimierung ohne Nebenbedingungen.- 6.1 Minimierung skalarer Funktionen, direkte Suchverfahren.- 6.1.1 Das Verfahren des goldenen Schnitts zur Bestimmung des Minimums einer unimodalen Funktion.- 6.1.2 Verallgemeinerung auf stetiges f: [a, b] ? ?.- 6.2 Nichtrestringierte Minimierung, Abstiegsmethoden.- 6.2.1 Einfache Grundlagen.- 6.2.2 Einige negative Beispiele.- 6.2.3 Abstiegsverfahren.- 6.2.4 Steilster Abstieg für konvexe quadratische Funktionen.- 6.3 Konjugierte-Gradienten Verfahren (cg-Verfahren).- 6.3.1 Präkonditionierung.- 6.3.2 Das Verfahren von Polak-Ribière.- 6.4 Trust-Region Verfahren zur Minimierung ohne Nebenbedingungen.- 6.5 Das Newton-Verfahren.- 6.5.1 Der Satz von Newton — Kantorovich.- 6.5.2 Affine Invarianz.- 6.5.3 Interpretation des Newton-Verfahrens als Trust — Region Verfahren.- 6.6 Quasi — Newton -Verfahren.- 6.6.1 Nichtlineare Gleichungssysteme.- 6.6.2 Minimierung glatter Funktionen.- 6.7 Nichtlineare Ausgleichsprobleme.- 6.7.1 Gauß-Newton-Verfahren.- 6.7.2 Quasi-Newton Ansatz für Ausgleichsprobleme.- 6.8 Ein praktisches Anwendungsbeispiel.- 6.9 Übungsaufgaben.- 6.9.1 Allgemeine Aufgaben.- 6.9.2 Aufgaben zum Satz von Newton Kantorovich.- III Optimalitätsbedingungen.- 7 Konvexität und Trennungssätze.- 7.1 Allgemeine Grundlagen.- 7.2 Trennungssätze.- 7.2.1 Schwache Trennungssätze.- 7.2.2 Das relativ Innere einer konvexen Menge.- 7.2.3 Eigentliche Trennung.- 7.3 Polare Kegel und konvexe Funktionen.- 7.4 Übungsaufgaben.- 8 Optimalitätsbedingungen für konvexe Optimierungsprobleme.- 8.1 Konvexe Ungleichungssysteme.- 8.2 Die KKT-Bedingungen.- 8.3 Die Lagrangefunktion.- 8.4 Dualität bei konisch konvexen Programmen.- 8.5 Dualität bei semidefiniten Programmen.- 8.6 Übungsaufgaben.- 9 Optimalitätsbedingungen für allgemeine Optimierungsprobleme.- 9.1 Optimalitätsbedingungen erster Ordnung.- 9.1.1 Tangentialkegel und Regularität.- 9.1.2 Der Satz von Kuhn und Tucker.- 9.1.3 Beweis von Satz 9.1.14.- 9.2 Optimalitätsbedingungen zweiter Ordnung.- 9.3 Sensitivität der Lösungen.- 9.4 Übungsaufgaben.- IV Nichtlineare Minimierung II.- 10 Projektionsverfahren.- 10.1 Allgemeine Konvergenzeigenschaften.- 10.2 Der Spezialfall affiner Nebenbedingungen.- 10.3 Quadratische Optimierungsprobleme.- 10.4 Übungsaufgaben.- 11 Penalty-Funktionen und die erweiterte Lagrangefunktion.- 11.1 Straffunktionen und Penalty-Verfahren.- 11.2 Differenzierbare exakte Penalty — Funktionen.- 11.3 Übungsaufgaben.- 12 Barrieremethoden und primal-duale Verfahren.- 12.1 Klassische Barrieremethoden.- 12.1.1 Das Konzept der Barrieremethoden.- 12.1.2 Ein allgemeines Barriereverfahren.- 12.2 Ein Primal-Duales Innere — Punkte-Verfahren.- 12.3 Beziehungen zwischen beiden Verfahren.- 12.3.1 Vergleich der Newton — Schritte.- 12.3.2 Unterschiede bei beiden Verfahren.- 12.4 Übungsaufgaben.- 13 SQP-Verfahren.- 13.1 Der SQP-Ansatz.- 13.2 Quasi-Newton-Updates.- 13.3 Konvergenz.- 13.3.1 Modifikation zur globalen Konvergenz.- 13.3.2 Der Maratos — Effekt.- 13.3.3 Schlussbemerkung.- 13.4 Übungsaufgaben.- 14 Global konvergente Verfahren.- 14.1 Trust — Region — Methoden II.- 14.2 Filter — Verfahren.- 14.3 Übungsaufgaben.- 15 Innere-Punkte-Verfahren für konvexe Programme.- 15.1 Theoretische Grundlagen.- 15.1.1 Ein konvexes Programm und Voraussetzungen.- 15.1.2 Die Methode der Zentren.- 15.1.3 Selbstkonkordanz.- 15.1.4 Assoziierte Normen zu selbstkonkordanten Barrierefunktionen.- 15.1.5 Das Newton-Verfahren zur Minimierung selbstkonkordanter Funktionen.- 15.1.6 ? — selbstkonkordante Barrierefunktionen und äußere ellipsoidale Approximationen.- 15.1.7 Ein einfacher Modellalgorithmus.- 15.2 Ein implementierbares Verfahren.- 15.2.1 Probleme mit linearen Gleichungen als Nebenbedingungen.- 15.2.2 Die Berücksichtigung linearer Gleichungen im Newton-Verfahren.- 15.2.3 Berechnung eines strikt zulässigen Startpunktes.- 15.2.4 Ein primaler Prediktor — Korrektor — Algorithmus.- 15.2.5 Einige Anwendungen.- 15.3 Übungsaufgaben.- 16 Semidefinite Programme.- 16.1 Notation und einige Grundlagen.- 16.1.1 Ein semidefmites Programm und seine duale Form.- 16.1.2 Darstellung des zentralen Pfades.- 16.2 Ein primal — duales Verfahren.- 16.2.1 Bestimmung der Newtonrichtungen.- 16.2.2 Die Klasse MZ.- 16.2.3 Numerischer Aufwand zur Lösung der linearen Gleichungssysteme.- 16.2.4 Einige spezielle Suchrichtungen.- 16.2.5 Skalierungsinvarianz.- 16.2.6 Konvergenz eines Kurzschrittverfahrens.- 16.3 Anwendungen.- 16.3.1 Lyapunovungleichung.- 16.3.2 Strikte Matrixungleichungen.- 16.3.3 Eigenwertoptimierung.- 16.3.4 Das Schurkomplement.- 16.3.5 Ein Rezept zur Lagrangedualität.- 16.4 Anwendungen auf kombinatorische Probleme.- 16.4.1 Das Problem der maximalen stabilen Menge.- 16.4.2 Das Max-Cut Problem.- 16.4.3 Das Graphenpartitionierungsproblem.- 16.4.4 Lineare 0-1 — Programme.- 16.4.5 Nichtlineare semidefinite Programme.- 16.5 Übungsaufgaben.- 17 Direkte Suchverfahren bei mehreren Variablen.- 17.1 Die „Simplexmethode“ von Neider und Mead.- 17.2 Das Kriging-Verfahren.- 17.2.1 Modellbildung.- 17.2.2 Minimierungsschritt.- 17.3 Übungsaufgaben.

O autorze

Prof. Dr. Florian Jarre studierte an der Universität Würzburg sowie der University of Texas in Austin und wurde 1989 in Würzburg promoviert. Nach Forschungsaufenthalten an der Stanford University und dem Tokyo Institute of Technology trat er eine Associate Professur an der University of Notre Dame (Indiana) an. Seit 2000 leitet er den Lehrstuhl für Mathematische Optimierung an der Heinrich-Heine-Universität Düsseldorf.

Prof. Dr. Josef Stoer wurde 1961 an der Johannes Gutenberg-Universität Mainz promoviert und war – nach einem mehrjährigen Forschungsaufenthalt an der University of California San Diego – von 1969 bis zu seiner Emeritierung Lehrstuhlinhaber an der Universität Würzburg. Neben zahlreichen Forschungsarbeiten ist er für seine Lehrbücher bekannt, insbesondere für die beiden Bände „Numerische Mathematik“ mit Roland Bulirsch. Er ist Ehrendoktor der TU München sowie der Universität Augsburg und Mitglied der Bayerischen Akademie der Wissenschaften.

Blurb

Dieses Buch führt in die Theorie und Methoden der stetigen Optimierung ein und zeigt darüber hinaus einige Anwendungen aus der diskreten Optimierung: Als gängige Verfahren für lineare Programme werden die Simplex- und Innere-Punkte-Methode vorgestellt. Im Bereich der nichtrestringierten Optimierung werden neben deterministischen Abstiegsverfahren und Trust-Region-Verfahren auch stochastische Abstiegsverfahren analysiert, die etwa beim maschinellen Lernen zum Einsatz kommen. Nach einer detaillierten Betrachtung der Optimalitätsbedingungen für nichtlineare Optimierungsprobleme mit Nebenbedingungen folgt eine Analyse von Verfahren der erweiterten Lagrangefunktion und ADMM sowie von SQP-Verfahren. Der Hauptteil schließt mit einer Betrachtung von semidefiniten Programmen und deren Anwendungen.

Für die zweite Auflage wurden zahlreiche Passagen überarbeitet und mehrere neue Abschnitte zu aktuellen Verfahren und Anwendungen ergänzt.

Das Buch basiert auf einer zweisemestrigen Lehrveranstaltung der Autoren und enthält zahlreiche Übungsaufgaben. Es richtet sich an Leser, die Grundkenntnisse in Analysis, linearer Algebra und numerischer Mathematik mitbringen.

Die Autoren

Prof. Dr. Florian Jarre studierte an der Universität Würzburg sowie der University of Texas in Austin und wurde 1989 in Würzburg promoviert. Nach Forschungsaufenthalten an der Stanford University und dem Tokyo Institute of Technology trat er eine Associate Professur an der University of Notre Dame (Indiana) an. Seit 2000 leitet er den Lehrstuhl für Mathematische Optimierung an der Heinrich-Heine-Universität Düsseldorf.

Prof. Dr. Josef Stoer wurde 1961 an der Johannes Gutenberg-Universität Mainz promoviert und war – nach einem mehrjährigen Forschungsaufenthalt an der University of California San Diego – von 1969 bis zu seiner Emeritierung Lehrstuhlinhaber an der Universität Würzburg. Neben zahlreichen Forschungsarbeiten ist er für seine Lehrbücher bekannt, insbesondere für die beiden Bände „Numerische Mathematik“ mit Roland Bulirsch. Er ist Ehrendoktor der TU München sowie der Universität Augsburg und Mitglied der Bayerischen Akademie der Wissenschaften.