Optimierung

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.