Numerische Verfahren der nichtlinearen Optimierung

1 Einführung.- 1.1 Auftreten von Optimierungsproblemen in der Praxis.- 1.2 Das Modell des allgemeinen NLO-Problems.- 1.3 Geometrische Veranschaulichung einfacher Opt imierungsprobleme.- 2 Theorie.- 2.1 Extremalkriterien für differenzierbare Probleme.- (*) Anhang 1 zu 2.1: Alternativsätze für Systeme linearer Ungleichungen.- (*) Anhang 2 zu 2.1: Alternative Herleitung der Multiplikator-Regel.- 2.2 Lagrange-Dualität I.- 2.3 Konvexe Optimierungsaufgaben.- 2.4 Lagrange-Dualität II.- 2.5 (*) Sensitivitäts- und Stabilitätsbetrachtungen.- 3 Verfahren.- 3.0 Übersicht.- 3.1 Verfahren der unrestringierten Minimierung.- 3.1.1 Schrittweitenverfahren.- 3.1.2 Verfahren zur Richtungsbestimmung.- 3.1.2.1 (*) Die Methode des koordinatenweisen Abstiegs. Das SOR-Newton-Verfahren.- 3.1.2.2 Verfahren mit gradientenbezogenen Richtungen.- 3.1.2.3 Newton- und Newton-ähnliche Verfahren.- 3.1.2.4 Quasi-Newton-Verfahren, insbesondere das BFGS-Verfahren.- 3.1.2.5 Verfahren konjugierter Richtungen. Das cg-Verfahren.- 3.1.2.6 (*) Weitere Quasi-Newton-Verfahren.- 3.1.2.7 (*) Verfahren, die die notwendigen Bedingungen zweiter Ordnung erfüllen.- 3.1.3 (*) Die Methode der Vertrauensbereiche.- 3.1.4 Spezielle Verfahren für Ausgleichsprobleme.- 3.1.4.1 Lineare Ausgleichsrechnung.- 3.1.4.2 Das Gauß-Newton-Verfahren.- 3.1.4.3 Schrittweitenverfahren für Ausgleichsaufgaben.- 3.1.4.4 (*) Das Verfahren von Levenberg und Marquardt in der Implementierung von J.J. Moré.- 3.1.4.5 (*) Ein spezielles Verfahren für die Ausgleichung mittels rationaler Funktionen.- 3.1.4.6 (*) Verfahren für Ausgleichsprobleme mit separierbaren Variablen.- 3.1.4.7 (*) Orthogonale Regression.- 3.1.5 Ergänzungen.- 3.1.5.1 Konvergenztheorie.- 3.1.5.2 Das Problem der Skalierung.- 3.1.5.3 Numerische Differentiation.- 3.1.5.4 Grenzgenauigkeit und Abbruchkriterien.- 3.2 Verfahren zur linearen Optimierung.- 3.2.1 Normalform einer LO-Aufgabe und Transformation auf Normalform.- 3.2.2 Struktur der zulässigen Menge und der Lösungsmenge der LO-Aufgabe.- 3.2.3 Das Simplexverfahren.- 3.2.4 Ermittlung einer zulässigen Ausgangsecke.- 3.2.5 Simplex-Verfahren mit LR-Zerlegung.- 3.2.6 Einiges über duale lineare Programme und Anwendungen.- 3.2.7 Die algebraische Berechnungskomplexität der LO-Aufgabe. Die Verfahren von Barnes, Khachiyan und Karmarkar.- 3.3 Verfahren zur quadratischen Optimierung.- 3.3.1 Ein primales Verfahren vom Projektionstyp.- 3.3.2 Das duale Verfahren von Goldfarb und Idnani zur Lösung streng konvexer quadratischer Optimierungsaufgaben.- 3.3.3 (*) Ein Verfahren für lineare Ausgleichsaufgaben mit linearen Restriktionen.- 3.3.4 (*) Verfahren zur Lösung quadratischer Optimierungsprobleme mit Mehrfachinaktivierung.- 3.3.5 (*) Weitere Verfahren zur Lösung von konvexen QP-Problemen.- 3.3.6 (*) Ein polynomiales Verfahren für konvexe quadratische Optimierungsprobleme.- 3.3.7 (*) Das indefinite quadratische Optimierungsproblem.- 3.4 Projektions-und Reduktionsverfahren für NLO.- 3.4.1 Allgemeine Konvergenztheorie eines primalen Abstiegsverfahrens.- 3.4.2 Konstruktion eines zulässigen Kurvenbogens.- 3.4.3 Ein Schrittweitenverfahren für (nichtlinear) restringierte Optimierungsprobleme.- 3.4.4 Q-superlinear konvergente Varianten von GGPRV.- 3.4.5 Verfahren vom Typ der reduzierten Gradienten.- 3.4.6 (*) Ein Reduktionsverfahren mit Mehrfachinaktivierung.- 3.4.7 (*) Das Projektionsverfahren von Bertsekas.- 3.4.8 Ergänzende Bemerkungen.- 3.5 Penalty- und Multiplikator-Verfahren.- 3.5.1 Klassische Penalty-Verfahren.- 3.5.2 Die Multiplikator-Methode von Hestenes und Powell für gleichungsrestringierte Probleme.- 3.5.3 Die Multiplikator-Methode von Rockafellar.- 3.5.4 (*) Exakte differenzierbare Penalty-Funktionen.- 3.5.5 Weitere Hinweise und Bemerkungen.- 3.6 Die Methode der sequentiellen quadratischen Minimierung.- 3.6.1 (*) Exakte nichtdifferenzierbare Penalty-Funktionen.- 3.6.2 Die Methode der sequentiellen quadratischen Optimierung.- 3.6.2.1 Allgemeine Vorüberlegungen.- 3.6.2.2 Die SQP-Methode für konvexe Optimierungsaufgaben.- 3.6.2.3 Die SQP-Methode für nichtkonvexe NLO-Probleme. Regularisierungstechniken für inkompatible QP-Probleme.- 3.6.2.4 (*) Die Konstruktion der Matrizenfolge {Ak}.- 3.6.2.5 (*) Der Maratos-Effekt.- 3.6.2.6 (*) Zur Schrittweitenbestimmung.- 3.6.2.7 (*) Zur Konvergenzgeschwindigkeit der SQP-Methode.- 3.6.2.8 Weitere Hinweise und Bemerkungen.- 3.7 Hinweise zur Praxis von NLO.- 3.7.1 Problemformulierung.- 3.7.2 Skalierung.- 3.7.3 Numerische Differentiation.- 3.7.4 Grenzgenauigkeit und Abbruchkriterien.- Anhang 1: Übersicht über verfügbare Software.- Anhang 2: Übersicht über themenspezifische Zeitschriften und Buchreihen.- Anhang 3: Notationen.