Numerik Der Optimierung

ISBN-13: 9783519020905 / Niemiecki / Miękka / 1993 / 353 str.

Christian Grossmann;Johannes Terno

Opis

Diesem Buch liegen verschiedene Grund-und Spezialvorlesungen zur Theorie und Numerik der Optimierung, welche die Autoren in den zuruckliegenden Jahren an der Technischen Universitat Dresden vorrangig fur Studenten der Mathematik ge halten haben, zugrunde. Ebenso sind Erfahrungen aus Gastlehrtatigkeiten an an deren Universitaten, insbesondere an der Universitat Kuwait, eingeflossen. Das vorliegende Manuskript entstand aus dem Bedurfnis heraus, den Studieren den, aber auch mathematisch interessierten Naturwissenschaftlern und Ingenieuren ein Lehrbuch zur Verfugung zu stellen, in dem gemeinsam wesentliche Grundprin zipien fur unterschiedliche Klassen von Optimierungsaufgaben behandelt werden. Dabei umfasst das Spektrum der einbezogenen Probleme optimierungstheoretische Fragen, wie Existenz und Charakterisierung von Optima, Hauptlinien der algorith mischen Behandlung stetiger und diskreter Optimierungsprobleme bis hin zu spe ziellen Fragen, wie z.B. Dekompositionstechniken zur Berucksichtigung problem spezifischer Strukturen. Das Buch widmet sich schwerpunktmassig endlichdimensionalen stetigen und diskreten Optimierungsproblemen, zeigt aber auch Verallgemeinerungen zu Auf gaben in Funktionenraumen auf. Dabei wird im Unterschied zu existierenden Lehrbuchern, bei denen endlichdimensionale Probleme als Spezialfall abstrakter Aufgaben mit skizziert werden, hier exemplarisch eine Sicht von den endlichdimen sionalen Problemen ausgehend auf die abstrakten Aufgaben angestrebt. Insbeson dere sollen damit auch Verbindungen der Numerik der Optimierung zu anderen mathematischen Spezialgebieten, wie z.B. zur Methode der Finiten Elemente und zur Diskretisierung von Variationsungleichungen aufgezeigt werde

Spis treści

1 Optimierungsaufgaben und Optimalitätskriterien.- 1.1 Globale und lokale Optima, Konvexität.- 1.2 Optimalitätsbedingungen.- 1.3 Semiinfinite Probleme.- 1.4 Ganzzahlige Probleme.- 1.5 Optimierung über Graphen.- 2 Dualität.- 2.1 Duale Probleme.- 2.2 Gestörte Optimierungsprobleme.- 2.3 Anwendungen der Dualität.- 2.3.1 Erzeugung von Schranken für den optimalen Wert.- 2.3.2 Lagrange-Relaxation.- 2.3.3 Vereinfachung der Aufgabe durch Übergang zum dualen Problem.- 2.3.4 Dualität in der linearen Optimierung.- 3 Minimierung ohne Restriktionen.- 3.1 Gradientenverfahren.- 3.2 Das Newton-Verfahren.- 3.2.1 Dämpfung und Regularisierung.- 3.2.2 Trust Region Technik.- 3.3 Quasi-Newton-Verfahren.- 3.4 CG-Verfahren.- 3.4.1 Quadratische Probleme.- 3.4.2 Allgemeine Probleme.- 3.5 Minimierung nichtglatter Funktionen.- 4 Linear restringierte Probleme.- 4.1 Polyedrische Mengen.- 4.2 Lineare Optimierung.- 4.2.1 Aufgabenstellung, Prinzip des Simplexverfahrens.- 4.2.2 Tableauform des Simplexverfahrens.- 4.2.3 Duales Simplexverfahren.- 4.2.4 Simultane Lösung primaler und dualer Aufgaben mit dem Simplexverfahren.- 4.2.5 Gewinnung eines ersten Simplexschemas.- 4.2.6 Behandlung oberer Schranken und freier Variabler.- 4.2.7 Das revidierte Simplexverfahren.- 4.2.8 Dualitätsaussagen.- 4.2.9 Das Transportproblem.- 4.3 Minimierung über Mannigfaltigkeiten.- 4.4 Probleme mit Ungleichungsrestriktionen.- 4.4.1 Aktive Mengen Strategie, Mannigfaltigkeits-Suboptimierung.- 4.4.2 Das Verfahren von Beale.- 5 Strafmethoden.- 5.1 Das Grundprinzip von Strafmethoden.- 5.2 Konvergenzabschätzungen.- 5.3 Modifizierte Lagrange-Funktionen.- 5.4 Strafmethoden und elliptische Randwertprobleme.- 6 Approximationsverfahren.- 6.1 Verfahren der zulässigen Richtungen.- 6.1.1 Standardverfahren.- 6.1.2 Ein Verfahren für nichtzulässige Startpunkte.- 6.2 Überlinear konvergente Verfahren.- 7 Komplexität.- 7.1 Definitionen, Polynomialität.- 7.2 Nichtdeterministisch polynomiale Algorithmen.- 7.3 Optimierungsprobleme und die Klasse NP-hart.- 7.4 Komplexität in der linearen Optimierung.- 8 Innere-Punkt- und Ellipsoid-Methoden.- 8.1 Konvexe Zielfunktion, Potentialfunktionen.- 8.2 Der Algorithmus von Karmarkar.- 8.2.1 Der Basisalgorithmus.- 8.2.2 Transformation in die Normalform.- 8.2.3 Vergleich der Potentialfunktionen.- 8.3 Die Ellipsoid-Methode.- 8.3.1 Der Basisalgorithmus.- 8.3.2 Komplexitätsuntersuchungen.- 8.4 Behandlung linearer Optimierungsaufgaben.- 8.4.1 Lineare Optimierungsprobleme als Ungleichungssysteme.- 8.4.2 Bisektion.- 8.4.3 Die Methode der gleitenden Zielfunktion.- 8.4.4 Komplexitätsaussagen.- 9 Aufgaben über Graphen.- 9.1 Definitionen.- 9.2 Graphen und lineare Optimierung.- 9.3 Aufdatierungen in Graphen.- 9.3.1 Kürzeste Wege.- 9.3.2 Netzplantechnik.- 9.3.3 Maximaler Fluß.- 9.4 Probleme aus der Klasse NP-vollständig.- 10 Die Methode branch and bound.- 10.1 Relaxation, Separation, Strategien.- 10.2 Branch and bound für GLO.- 10.3 Das Rundreiseproblem.- 10.3.1 Das unsymmetrische Rundreiseproblem.- 10.3.2 Das symmetrische Rundreiseproblem.- 11 Dekomposition.- 11.1 Dekompositionsprinzipien.- 11.1.1 Zerlegung durch Projektion.- 11.1.2 Dekomposition durch Sattelpunkttechniken.- 11.1.3 Zerlegung des zulässigen Bereiches.- 11.2 Dynamische Optimierung.- 11.2.1 Grundlagen, Separabilität.- 11.2.2 n-stufige Entscheidungsprozesse.- 11.2.3 Die Forward State Strategie.- 11.3 Ausgewählte Anwendungen.- 11.3.1 Lineare Optimierung mit blockangularen Nebenbedingungen.- 11.3.2 Der Algorithmus von Benders.- 11.3.3 Spaltengenerierung.- 11.3.4 Lineare Optimierung mit flexiblen Restriktionen.- 12 Strukturuntersuchungen.- 12.1 Ganzzahlige Polyeder.- 12.2 Gültige Ungleichungen.- 12.3 Matroide, Greedy-Algorithmus.