Dieses Buch beschäftigt sich mit numerischen Verfahren zur Lösung nichtlinearer Optimierungsaufgaben. Grundlagen mehrerer Verfahren werden zu Beginn der Studie theoretisch formuliert und anschließend auf Korrektheit und Effizienz untersucht. Das einleitende Kapitel stellt Definitionen und Sätze aus Optimierungstheorie, Linearer Algebra, Analysis und Numerik zusammen und erklärt Kriterien zur Konvergenzanalyse. Da sich die Lösung von drei der behandelten Verfahren auf die Lösung von sogenannten unrestringierten Problemen oder eines Gleichungssystems zurückführen lässt, wird zuerst ein Newton-artiges Verfahren vorgestellt. Dabei analysiert die Autorin wünschenswerte Eigenschaften, wie etwa globale Konvergenz und hohe Konvergenzordnung des Verfahrens. Im anschließenden Kapitel stellt die Studie die sogenannten Penalty-, Penalty-Lagrange-, Barriere- und Innere-Punkte-Verfahren anhand der Hilfs-Funktionen mit den Algorithmen für eine numerische Behandlung vor und untersucht mithilfe der erstellten Konvergenzkriterien die verschiedenen Konvergenzeigenschaften. Den Schlusspunkt des Buches setzen numerische Fallstudien, wobei die Effizienz der Verfahren geprüft wird.

Textprobe: Kapitel, Einleitung: Dieses Buch befasst sich mit der nichtlinearen Optimierung, die das Problem der Minimierung oder der Maximierung einer nichtlinearen Funktion unter Berücksichtigung einer endlichen Anzahl von Nebenbedingungen behandelt. Die Optimierung ist ein bedeutendes Anwendungsgebiet der Mathematik. Sie wird regelmäßig zur Unterstützung von Entscheidungsprozessen in Wirtschaft und Industrie verwendet. Wegen der wachsenden Leistungsfähigkeit moderner Rechner ist die Behandlung umfangreicher Optimierungsaufgaben aus der Praxis, die ohne diese technischen Werkzeuges unmöglich wäre, ein Anwendungsgebiet der Numerik geworden. Eine der bedeutenden Aufgaben der Numerik ist es, die Korrektheit von Algorithmen zu überprüfen, d.h. sicherzustellen, das unter gewissen Voraussetzungen an die Problemdaten tatsächlich die richtige Lösung bzw. eine Näherungslösung mit einer benötigten Lösungsgenauigkeit bestimmt wird. Diese Überprüfung soll mit mathematischen Techniken durchgeführt werden, d.h. am Ende steht ein formaler mathematischer Beweis, der den korrekten Ablauf eines Algorithmus sicherstellt. Hat man sich von der einwandfreien Funktion eines Algorithmus überzeugt, so stellt sich die Frage nach der Effizienz des Algorithmus, d.h. es muss der Rechenaufwand pro Näherungslösung und die Konvergenzgeschwindigkeit gegen die exakte Lösung untersucht werden. Die beiden Eigenschaften liefern Informationen darüber, wieviel Iterationen der Algorithmus benötigt, um eine Näherungslösung auf eine bestimmte Genauigkeit zu berechnen und wieviel Zeit jede Iteration der Berechnung in Anspruch nimmt. Dieses Buch beschäftigt sich mit numerischen Verfahren zur Lösung nichtlinearer Optimierungsaufgaben. Es werden theoretische Grundlagen von mehreren Verfahren unter den Gesichtspunkten der Korrektheit und der Effizienz ausgearbeitet und durch Beispiele und mit Matlab R2008a erzeugten Abbildungen aufgelockert. 2., Quasi-Newton-Verfahren zur Lösung von unrestringierten Optimierungsproblemen: Abgesehen von ihrer praktischen Bedeutung werden viele Verfahren zur Lösung von unrestringierten Problemen ferner als Ansatzpunkt zur Entwicklung von Verfahren zur restringierten Optimierung herangezogen. Außerdem kann die Lösung von restringierten Problemen auf die von unrestringierten Problemen zurückgeführt werden. Deswegen beschäftigt sich dieses Kapitel mit einem Newton-artigen Verfahren, das zur Lösung nichtlinearer Gleichungen, kleiner und mittelgroßer Gleichungssysteme und unrestringierter Optimierungsprobleme verwendet wird. Die Verfahrensklasse der unrestringierten Minimierung wird derzeit als eine der effizientesten und zuverlässigsten zur Lösung von Problemen nicht zu hoher Dimension angesehen. 2.1, Grundidee des Newton-Verfahrens: Um die Idee und die Herleitung von Quasi-Newton-und Innere-Punkte-Verfahren verständlich vorstellen zu können, betrachten wir die Grundidee und grundlegende Definitionen des (lokalen) Newton-Verfahrens zur Lösung nichtlinearer Gleichungssysteme und nichtlinearer unrestringierter Optimierungsprobleme. 6., Innere-Punkte-Verfahren: Dieses Kapitel gibt einen Einblick in die Grundlagen und wesentlichen Ideen der sogenannten Innere-Punkte-Methoden. Das Verfahren wurde als eine Alternative zum sogenannten Simplexverfahren im 1984 von Narendra Karmakar zur Lösung von linearen Problemen entwickelt. Der Ansatz mittels den sogenannten projektiven Verfahren (englisch-projective method) war deswegen bedeutend, weil er zum einen die beschränkte Anzahl der benötigten Operationen zur Berechnung einer Lösung in gewünschter Genauigkeit hat und der andererseits ein hervorragenderes Laufzeitverhalten in der Praxis aufzeigte. Diese Veröffentlichung [9] löste eine große Welle von Forschungsaktivitäten zu Innere-Punkte-Methoden aus. Eine Reihe von Arbeiten stellten fest, dass diese Verfahren nicht nur für die lineare Optimierung interessant sind, sondern auch auf allgemeine nichtlineare Optimierungsprobleme angewandt werden können. Insbesondere die enge Verknüpfung zu dem Barriere-Verfahren war von zentraler Bedeutung für die Anwendung des Verfahrenskonzeptes auf nichtlineare Probleme und wurde für den Nachweis der Konvergenz der Innere-Punkte-Verfahren herangezogen. Der Ansatz über logarithmische Barriere-Funktionen stammt von Frisch für lineare Optimierungsaufgaben und wurde von Fiacco und McCormick für nichtlineare Probleme erweitert. Das eigentliche Innere-Punkte-Verfahren besteht also aus einer äußeren Iteration, der Barriere-Iteration, und einer inneren Iteration, dem Newton- oder Newton-artigen Verfahren, das in jedem Barriere-Schritt zur Bestimmung einer Lösung des im äußeren Schritt aufgestellten Problems verwandt wird. Die Innere-Punkte-Verfahren unterscheiden sich hauptsächlich durch die Wahl der Barriere-Funktion sowie der Wahl einer Globalisierungsmethode. 6.3, Grundzüge der primal-dualen Innere-Punkte-Verfahren für nichtlineare Probleme: Wie es bereits erwähnt wurde, liegt die Stärke der Innere-Punkte-Verfahren in der Übertragbarkeit auf nichtlineare Programme. Deren Behandlung mittels der Innere- Punkte-Verfahren ist oft kaum schwerer als die Behandlung von linearen Problemen. Insbesondere lässt sich zeigen, dass die theoretische nachweisbare Mindestkonvergenzgeschwindigkeit in beiden Fällen gleich ist. Zwar nicht ohne weiteres, lässt sich das Konzept des Pfad-Verfolgungs-Verfahrens auf nichtlineare Optimierungsaufgaben übertragen. Die bereits vorgestellten allgemeinen zulässigen primal-dualen Innere-Punkte-Verfahren haben eher eine historische Bedeutung. Die unzulässigen primal-dualen Innere-Punkte-Verfahren haben sich in der Praxis durchgesetzt. Anderseits sind Konvergenzanalysen, die für nichtlineare Probleme im Allgemeinen komplexer sind, nach wie vor eher erfreulich, deswegen gehen wir auf die in Reichweite liegenden Konvergenzergebnisse der Innere-Punkte-Verfahren für allgemeine Optimierungsprobleme nicht ein. 6.4.3, Algorithmus mit Korrekturschritten: Nachdem die Grundlagen einer Schrittweitenbestimmungstrategie mit dem Filtereinsatz beschrieben wurden, wird der Algorithmus nun um einige Erweiterungen ergänzt. Die Motivation dafür ist eine gute Konvergenzgeschwindigkeit von Newton-artigen Verfahren in der Nähe eines Minimum, die man behalten möchte. Außer den bereits erwähnten Schwierigkeiten bei dem Einsatz von Penalty-Funktionen als Gütefunktionen in Schrittweitenstrategien kann noch ein Effekt auftreten, bei dem im ungünstigsten Fall die schnelle Konvergenz zerstört werden kann. Sind die Restriktionen nichtlinear, wird bei der Linearisierung der Restriktionen innerhalb des Newton-Verfahrens diese Krümmung nicht berücksichtigt. Dies führt dazu, dass Vollschritte, die eigentlich einen guten Fortschritt in Richtung der gesuchten Lösung bringen, zurückgewiesen werden, weil die Gütefunktion sich verschlechtert. Dadurch werden nur kleinere Schritte in dieselbe Richtung akzeptiert, d.h. wir machen immer nur Teilschritte statt Vollschritte, was die Konvergenzgeschwindigkeit beeinträchtigt. Das Problem wird als Maratos-Effekt bezeichnet.

• restringierte Optimierungsaufgabe

• unrestringiertes Optimierungsproblem

• Penalty-Verfahren

• Innere-Punkte-Verfahren

• Barriere-Verfahren

• Numerik

Nadeshda Dornes wurde 1984 in Russland geboren. Ihr Studium der Wirtschaftsmathematik an der Universität Ulm schloss die Autorin im Jahre 2013 mit dem akademischen Grad der Master of Science erfolgreich ab. Bereits während des Studiums sammelte die Autorin umfassende praktische Erfahrungen in der Finanzdienstleistungsbranche.