Mathematische Optimierung: Grundlagen Und Verfahren

ISBN-13: 9783642661570 / Niemiecki / Miękka / 2011 / 422 str.

E. Blum; W. Oettli

Opis

Die mathematische Optimierung - auch mathematische Programmierung genannt - befal3t sich mit dem Problem der Extremwertermittlung einer Funktion tiber einem zuiassigen Bereich, der wesentlich durch Gleichungs- und Unglei chungsrestriktionen beschrieben ist. Zahlreiche praktische und theoretische Fragestellungen lassen sich auf dieses Problem zurtickfUhren. 1m vorliegenden Band soli ein Oberblick tiber die mathematische Optimierung in endlich-dimen sionalen Raumen gegeben werden. Naturgemal3 steht dabei die nichtlineare Optimierung im Vordergrund, da die lineare Theorie weitgehend abgeschlossen und bereits in zahlreichen Lehrbtichem dargestellt ist. Immerhin findet sich auch die lineare Programmierung in einem eigenen Kapitel eingehend behandelt. 1m nichtlinearen Fall konzentrieren wir uns einerseits auf konvexe, andererseits auf ditTerenzierbare Probleme. Bei der Auswahl des Materials wurde den Grund lagen - darunter verstehen wir die Charakterisierungstheorie der Optimal losungen und die Dualitatstheorie - gleiches Gewicht beigemessen wie den eigentlichen Losungsverfahren. Die letzteren wurden nach Familien geordnet, wobei einige typische Vertreter aus jeder Familie vorgestellt werden. Wir haben grol3eren Wert darauf gelegt, den begriffiichen Ablauf eines Verfahrens klar zumachen, als darauf, computerfertige Rechenanweisungen zu liefem. Es wurde versucht, die Resultate der konvexen Analysis auch fUr die Verfahren nutzbar zu machen, indem beispielsweise bei konvexen Funktionen nach Moglichkeit auf DitTerenzierbarkeitsforderungen verzichtet und stattdessen die Theorie der Sub gradienten herangezogen wurde. Besondere Aufmerksamkeit wurde den Proble men mit unendlich vielen Nebenbedingungen gewidmet; solche Probleme treten etwa in der Approximationstheorie in ganz nattirlicher Weise auf. Einige ein gestreute Beispiele sind theoretischer Natur und sollen die Anwendungsmoglich keit der Optimierung auf andere Fachgebiete illustrieren."

Spis treści

1. Kapitel. Mathematische Programme.- 1. Problemstellung und Definitionen.- 2. Sonderfälle. Konvexe Programme.- 3. Umformungen von Programmen.- 2. Kapitel. Lineare Programmierung.- 1. Allgemeines.- 2. Die Dualitätstheorie der linearen Programmierung.- 3. Das Simplexverfahren.- 4. Die Tableaudarstellung des Simplexverfahrens.- 5. Die Bestimmung einer zulässigen Startbasis.- 6. Degenerierte Programme.- 7. Der primal-duale Algorithmus.- 8. Der Dekompositionsalgorithmus.- 9. Das „Max-Flow/Min-Cut“-Theorem.- 3. Kapitel. Optimalitätsbedingungen.- 1. Allgemeines.- 2. Optimalitätsbedingungen ohne Verwendung der Lagrange-Funktion.- 3. Optimalitätsbedingungen, die die Lagrange-Funktion verwenden: Grundlegende Begriffe.- 4. Optimalitätsbedingungen ohne Differenzierbarkeitsvoraussetzungen (unter Verwendung der Lagrange-Funktion).- 5. Optimalitätsbedingungen für Programme mit differenzierbaren Funktionen (unter Verwendung der Lagrange-Funktion).- 6. Optimalitätsbedingungen für Programme mit unendlich vielen Restriktionen.- 7. Anwendungsbeispiele zu den Optimalitätsbedingungen.- 8. Optimalitätsbedingungen für Programme mit linearen Restriktionen.- 4. Kapitel. Dualitätstheorie.- 1. Einleitung.- 2. Die Theorie von Dantzig, Eisenberg und Cottle.- 3. Die Dualitätstheorie von Stoer.- 4. Dualitätstheorie für homogene Programme.- 5. Die Dualitätstheorie von Fenchel und Rockafellar.- 6. Semi-infinite Programme.- 5. Kapitel. Optimierung ohne Restriktionen.- 1. Gradientenverfahren erster Ordnung.- 2. Die Verfahren der konjugierten Richtungen.- 3. Das Newton-Verfahren.- 4. Die Minimierung einer Funktion auf einem Intervall.- 6. Kapitel. Projektions- und Kontraktionsverfahren.- 1. Einleitung.- 2. Das Verfahren von Uzawa.- 3. Fejér-Kontraktionen.- 7. Kapitel. Einzelschrittverfahren.- 1. Das zyklische Einzelschrittverfahren.- 2. Einzelschrittverfahren mit beliebiger Ordnung.- 3. Anwendung auf duale Probleme.- 4. Der quadratische Fall.- 8. Kapitel. Schnittverfahren.- 1. Das allgemeine Modell.- 2. Das Schnittverfahren bei streng konvexer Zielfunktion.- 3. Der Austauschalgorithmus für lineare Programme mit unendlich vielen Restriktionen.- 4. Minimierung einer konvexen Funktion auf einem konvexen Grundbereich. Anwendung auf duale Probleme.- 9. Kapitel. Dekompositionsverfahren.- 1. Hilfsmittel.- 2. Das symmetrische Dekompositionsverfahren.- 3. Das primale Dekompositionsverfahren.- 4. Varianten des primalen Dekompositionsverfahrens.- 10. Kapitel. Strafkostenverfahren.- 1. Einleitung.- 2. Der allgemeine Fall.- 3. Der konvexe Fall.- 4. Das Verfahren SUMT (Sequential Unconstrained Minimization Technique).- 11. Kapitel. Verfahren der zulässigen Richtungen.- 1. Hilfsmittel.- 2. Das Verfahren I: Lineare Approximationen.- 3. Das Verfahren II: Konvexe Approximationen.- 12. Kapitel. Das Verfahren der projizierten Gradienten.- 1. Hilfsmittel.- 2. Das Verfahren.- 13. Kapitel. Die Verfahren von Zangwill und Dantzig-Cottle.- 1. Der konvexe Fall.- 2. Der quadratische Fall.- 14. Kapitel. Das Verfahren von Beale.- 1. Beschreibung des Verfahrens.- 2. Die Konvergenz des Verfahrens.- 3. Tableaudarstellung des Verfahrens.- Anhang. Bibliographie zur Nichtlinearen Programmierung.- Namen- und Sachverzeichnis.