Numerische Verfahren Der Nichtlinearen Optimierung

ISBN-13: 9783034872157 / Niemiecki / Miękka / 2012 / 558 str.

Peter Spellucci

Opis

Dieses Lehrbuch bietet eine umfassende Darstellung derjenigen Verfahren zur Losung nichtlinearer Optimierungsprobleme, die nach dem gegen- wartigen Wissensstand als zuverlassig und effizient gelten. Es fuhrt den Leser von den theoretischen Grundlagen bis auf den Stand der gegen- wartigen Forschung. Dabei werden nur mathematische Vorkenntnisse vorausgesetzt, wie sie das Grundstudium sowohl fur Mathematiker als auch fur mathematisch orientierte Anwender ublicherweise bereitstellt. Neben einer sorgfaltigen Erarbeitung der Konvergenzeigenschaften der Verfahren werden auch wichtige Details der Implementierung diskutiert. Das Buch enthalt zahlreiche durchgerechnete Beispiele und Illustrationen, die dem Leser eine bessere Vorstellung uber die Vorgehensweise und Leistungsfahigkeit der Verfahren vermitteln konnen. Zahlreiche Ubungs- aufgaben verschiedenen Schwierigkeitsgrades ermoglichen dem Leser die Kontrolle seines Verstandnisses. Das vorgelegte Werk geht sowohl in der Breite des behandelten Stoffes als auch in der Tiefe der mathematischen Analyse uber die bestehenden Lehrbucher hinaus. Fur die meisten Verfahren werden detailliert ausgearbeitete Konvergenzbeweise angegeben. Eine Fulle von Resultaten aus den letzten 10 Jahren erscheint hier zum ersten Mal in Buchform. Neben in Handrechnung nachvollziehbare einfache Beispiele treten ausgearbeitete Anwendungsbeispiele aus der Praxis.

Spis treści

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 .- 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.