"Nichtlineare Optimierung 001.ps.gz" - читать интересную книгу автора

Manuskript zur Vorlesung

Nichtlineare Optimierung

SS 1993

Uwe Zimmermann Abteilung Mathematische Optimierung

Institut f"ur Angewandte Mathematik

Technische Universit"at Braunschweig

3. Juli 1996

2 Inhaltsverzeichnis 1 Einf"uhrung und "Ubersicht 5

1.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Allgemeine Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Bezeichnungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Nichtlineare Optimierung ohne Restriktionen 11

2.1 Abstiegsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Das Prinzip des hinreichenden Abstiegs . . . . . . . . . . . . . . . . . 11 2.1.2 Die Goldstein-Armijo-Suche . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.3 Asymptotisch exakte Schrittweiten . . . . . . . . . . . . . . . . . . . . 15 2.1.4 Streng gradientenbezogene Richtungen . . . . . . . . . . . . . . . . . . 15 2.1.5 Regularisierung nach Levenberg-Marquardt . . . . . . . . . . . . . . . 23 2.2 Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Quasi-Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.1 Das BFGS-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3.2 Cholesky-Update von Ak beim BFGS-Verfahren . . . . . . . . . . . . 32 2.3.3 Die Restart-Version des BFGS-Verfahrens . . . . . . . . . . . . . . . . 33 2.4 Minimierung von Quadratsummen . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4.1 Lineare Ausgleichsrechnung . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.2 Das Gauss-Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 36 2.4.3 Das Verfahren von Levenberg, Marquardt und Mor'e . . . . . . . . . . 38

3 Nichtlineare Optimierung mit Restriktionen 45

3.1 Optimalit"atsbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.1.1 Tangentialkegel und die Guignard-Bedingung . . . . . . . . . . . . . . 45 3.1.2 Restriktionsqualifikationen 2. Ordnung . . . . . . . . . . . . . . . . . . 51 3.1.3 Strikte Komplementarit"at . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1.4 Sattelpunkte und die Lagrangefunktion . . . . . . . . . . . . . . . . . 53 3.1.5 Konvexe Optimierungsaufgaben . . . . . . . . . . . . . . . . . . . . . . 56 3.2 Quadratische Optimierungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . 61

3.2.1 Das PQP-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3