Florian Jarre, Josef Stoer

Optimierung

• Broschiertes Buch

Produktbeschreibung

Dieses Buch gibt eine Einführung in die Theorie und Methoden der stetigen Optimierung mit einigen Anwendungen auch im Bereich der diskreten Optimierung. Bei der linearen Optimierung werden zunächst die klassische Simplexmethode und die neueren Innere Punkte Methoden vorgestellt. Es werden dann konvexe und glatte nichtlineare Probleme sowie semidefinite lineare Programme betrachtet, wobei stets das Verständnis der Optimalitätsbedingungen benutzt wird, um die Lösungsverfahren, darunter auch Innere-Punkte-Methoden, vorzustellen. Zu einigen praktischen Anwendungen werden ausführliche Beispiele beschrieben.

Produktdetails

• Springer-Lehrbuch
• Verlag: Springer, Berlin
• Seitenzahl: 476
• Deutsch
• Abmessung: 235mm x 155mm x 25mm
• Gewicht: 730g
• ISBN-13: 9783540435754
• ISBN-10: 3540435751
• Artikelnr.: 12072244

Autorenporträt

Florian Jarre, Heinrich-Heine-Universität Düsseldorf / Josef Stoer, Universität Würzburg

Inhaltsangabe

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ü