Claus Richter
Gerhart-Hauptmann-Str. 1
01219 Dresden
Deutschland
Alle Bücher von Wiley-VCH werden sorgfältig erarbeitet. Dennoch übernehmen Autoren, Herausgeber und Verlag in keinem Fall, einschließlich des vorliegenden Werkes, für die Richtigkeit von Angaben, Hinweisen und Ratschlägen sowie für eventuelle Druckfehler irgendeine Haftung.
Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
© 2017 WILEY-VCH Verlag GmbH & Co. KGaA, Boschstr. 12, 69469 Weinheim, Germany
Alle Rechte, insbesondere die der Übersetzung in andere Sprachen, vorbehalten. Kein Teil dieses Buches darf ohne schriftliche Genehmigung des Verlages in irgendeiner Form – durch Photokopie, Mikroverfilmung oder irgendein anderes Verfahren – reproduziert oder in eine von Maschinen, insbesondere von Datenverarbeitungsmaschinen, verwendbare Sprache übertragen oder übersetzt werden. Die Wiedergabe von Warenbezeichnungen, Handelsnamen oder sonstigen Kennzeichen in diesem Buch berechtigt nicht zu der Annahme, dass diese von jedermann frei benutzt werden dürfen. Vielmehr kann es sich auch dann um eingetragene Warenzeichen oder sonstige gesetzlich geschützte Kennzeichen handeln, wenn sie nicht eigens als solche markiert sind.
Print ISBN 978-3-527-34107-8
ePDF ISBN 978-3-527-80079-7
ePub ISBN 978-3-527-80080-3
Mobi ISBN 978-3-527-80081-0
Für meine liebe Frau Hannelore
Bücher zur Implementierung numerischer Verfahren der Optimierung sind seit vielen Jahren gefragt. Die Behandlung mathematisch-naturwissenschaftlicher, technischer und ökonomischer Fragestellungen erfordert in wachsendem Umfang die Lösung linearer oder nichtlinearer Optimierungsaufgaben. Gegenüber den ersten Bemühungen in den 40er- und 50er-Jahren haben sich hierfür die Voraussetzungen auf dem Gebiet der Informatik wesentlich verbessert. Nicht nur Rechenzeit und Speicherplatz haben eine andere Bewertung erfahren, auch Programmierparadigmen und die Nutzung von Dialogmöglichkeiten haben sich geändert. Dieser Entwicklung folgend, werden im vorliegenden Buch Probleme und Lösungsverfahren als Klassen der objektorientierten Programmierung aufgefasst. Die Formulierung der zu lösenden Optimierungsaufgabe und die Auswahl der Lösungsmethode erfolgt im Dialog, die Ergebnisse der Berechnung werden automatisch gespeichert. Im Unterschied zu komplexen Systemen, wie Matlab sind die einzelnen Routinen modifizierbar und separat nutzbar. Seit den Arbeiten von Kantorovich [1] und Dantzig [2] zum Simplexverfahren hat auch die Entwicklung effektiver numerischer Verfahren der Optimierung eine stürmische Entwicklung genommen. Ihre theoretische Begründung und sachgerechte Implementierung stellt inzwischen einen eigenständigen Problemkreis dar, welcher als Numerik der Optimierung (in englischer Sprache als „Computational Mathematical Programming“, in russischer Sprache als „Vycislitelnye metody programmirovanija“) bezeichnet wird. Die Aneignung der auf diesem Gebiet vorhandenen Erkenntnisse, noch mehr aber das Erleben des Zusammenhangs von beschriebenem Algorithmus, umgesetztem Programm und bereitgestellter Nutzeroberfläche werden zum Bedürfnis des an der Optimierung interessierten Praktikers. Gegenstand des Buches sind deshalb nicht in erster Linie theoretische Grundlagen, sondern Fragen der praktischen Realisierung der Verfahren mit modernen Mitteln der Informatik. Es soll einen Einstieg in die Behandlung von Optimierungsaufgaben auf Computern ermöglichen.
Für praktische Hilfeleistungen beim Zustandekommen des Buches bin ich Klaus Schönefeld zu Dank verpflichtet. In gleicher Weise danke ich Thomas Cassebaum für die Möglichkeit, die von ihm bereitgestellte Entwicklungsumgebung „SmallCpp“ nutzen zu können und in C++-Fragen in ihm jederzeit einen guten Gesprächspartner gefunden zu haben. Ermutigende Worte und gute Ratschläge vieler Kollegen, insbesondere von Diethard Pallaschke, Oleg Burdakov, Manfred Grauer und Gerd Langensiepen, haben den Entstehungsprozess befördert. Dem Wiley-Verlag danke ich für die Möglichkeit, die Ergebnisse meiner Überlegungen zu publizieren. Schließlich möchte ich meiner Frau Hannelore für das Verständnis danken, mit dem sie die Belastung mitgetragen hat, welche dem Autor aus dem Schreiben eines Buches erwächst. Die Publikation von Algorithmen und Programmen schließt zu erwartende Kritiken und Hinweise von vornherein ein. Sie werden von mir sorgfältig berücksichtigt und in die Aufbereitung weiterer Programmversionen eingearbeitet.
Claus Richter
Im vorliegenden Buch werden Optimierungsaufgaben betrachtet, die dadurch charakterisiert sind, dass eine lineare oder nichtlineare Zielfunktion f unter linearen oder nichtlinearen Ungleichungsnebenbedingungen minimiert wird, d. h.
wobei I
die Indexmenge der Ungeichungsrestriktionen bezeichnet. Gleichungsrestriktionen werden der Übersichtlichkeit halber zunächst weggelassen. An geeigneten Stellen werden sie zusätzlich berücksichtigt.
Für die weiteren Überlegungen benötigen wir folgende Bezeichnungen:
Besitzen Zielfunktion f und der zulässige Bereich G bzw. Nebenbedingungen gi und gj eine spezielle Gestalt, so können zur Lösung von (1.1) spezielle Verfahren herangezogen werden. Für die Zielfunktion f sind folgende Strukturen interessant:
In Bezug auf die Nebenbedingungen N sind folgende Situationen typisch:
In den folgenden Kapiteln werden spezielle Kombinationen von Zielfunktion und Nebenbedingungen eine besondere Rolle spielen:
Die Spezifikationen L, Q, C, U und P werden in der Charakterisierung der implementierten Beispiele im Programmsystem „Optisoft“ verwendet. Über die dargestellten Kombinationen von Zielfunktion und Nebenbedingungen hinaus spielen Aufgaben der nichtglatten Optimierung eine besondere Rolle. Diese finden im vorliegenden Buch keine Beachtung. Gleiches gilt auch für Optimierungsaufgaben mit sehr vielen Variablen: n > 100, sofern sie nicht als Teilprobleme zur Lösung von (1.1) auftreten.
Obwohl die spezifische Gestalt von Zielfunktion und Nebenbedingungen interessant ist, wie etwa in der geometrischen Optimierung
wird diese nicht explizit berücksichtigt.
In der Betrachtung von Optimierungsverfahren gehen wir von dem Grundmodell (1.1) aus. Für Least-Square-Probleme in Differenzialgleichungsmodellen und bei Strukturoptimierungsproblemen liegen spezielle Aufgaben zugrunde. Diese werden in den folgenden Kapiteln näher erläutert.
Nichtlineare Optimierungsprobleme spielen in vielen Anwendungsbereichen eine wichtige Rolle, z. B. in der
Typische Anwendungsbeispiele finden sich in den Büchern von Bracken und McCormick [3] oder Beightler und Phillips [4]. Einige mathematische Fragestellungen, welche bei der Lösung praktischer Probleme auf Optimierungsverfahren zurückgreifen, werden im Buch näher betrachtet:
Die Strukturoptimierung wird schon seit einigen Jahren in der computergestützten Konstruktion eingesetzt. In der zugrundeliegenden Aufgabenstellung wird dabei zwischen Querschnitts-, Form-, und Topologieoptimierung (der eigentlichen Strukturoptimierung) unterschieden. Grundlegende Fragestellung ist dabei, die Struktur und die Abmessungen von Konstruktionen derart zu wählen, dass zum einen die mechanischen Randbedingungen erfüllt und zum anderen der Materialeinsatz und damit die Kosten möglichst gering sind.
Obwohl die Berücksichtigung der Nebenbedingungen oft die Koppelung mit komplizierten Berechnungsvorschriften – z. B. FEM-Solvern – erfordert, soll das Grundprinzip an folgendem Beispiel erläutert werden:
Spezielle nichtlineare Optimierungsaufgaben treten bei der Parameterbestimmung von Modellen auf, die einen in Natur- oder Technikwissenschaften vorliegenden Zusammenhang qualitativ beschreiben. Sind über diesen Zusammenhang Resultate von Experimenten bekannt, kann man die Methode der kleinsten Quadrate anwenden, um die Koeffizienten näherungsweise zu bestimmen. Das zugehörige Optimierungsproblem lautet:
bei
Hierbei sind
y(x, t) – die gewählte Modellfunktion,
x – der Parametervektor, dessen Komponentenwerte zu bestimmen sind
ti – der
i-te Wert der (u. U. vektorwertigen) unabhängigen Veränderlichen,
yi – die i-te Beobachtung der (u. U. vektorwertigen) unabhängigen Veränderlichen,
a, b – Schrankenvektoren für den Vektor x.
Entsprechend der Wahl der Norm haben wir es mit einer linearen oder quadratischen Zielfunktion zu tun. Die vorliegende Formulierung gestattet die Berücksichtigung zusätzlicher Nebenbedingungen. Beim Vorliegen von Differenzialgleichungen wird die Aufgabe wie folgt modifiziert:
bei
Eventuell treten zusätzlich Anfangsbedingungen der Form
auf.
Diese können gegebenenfalls in die Least-Square-Formulierung einbezogen werden.
Das Problem der optimalen Steuerung besteht darin, eine Funktion unter Differenzialgleichungsnebenbedingungen sowie Anfangs- und Endbedingungen zu minimieren: bei
bei
Durch Spline-Approximation der Steuerungsfunktion und Anwendung von Lösungsmethoden für Differenzialgleichungssysteme ist es möglich, das Problem der optimalen Steuerung in eine nichtlineare Optimierungsaufgabe zu transformieren. Hierzu wird die Kopplung einer Mehrfachschießmethode mit einer SQP-Methode betrachtet.
Diese Kopplung ist sehr effektiv und eine Alternative zur Verwendung von Straf-Barriere-Verfahren, welche von Kraft publiziert wurde [5].