Optimierung in C++
Description
Praxisbezogen führt Claus Richter in die Algorithmen der Optimierung ein. Einsteiger und Fortgeschrittene werden gleichermaßen auf den heutigen Stand der Dinge gebracht. In klaren Schritten umreißt der Autor die Grundlagen dieses Gebietes, beginnend mit Definitionen und Optimalitätsbedingungen, um sich dann direkt an den C++-Programmierer zu wenden. Der nötige mathematische Apparat, die verwendete Programmiersprache C++ und ihre Klassen werden vorgestellt. Damit stellt der Autor ein einheitliches Niveau her und wird so einer breiten Leserschaft gerecht. Im Folgenden werden 20 Verfahren der linearen, quadratischen und nichtlinearen Optimierung behandelt und dem Anwender nähergebracht. Jeder Algorithmus wird im Aufbau erläutert und an einem konkreten Beispiel demonstriert. Fünf weitere Kapitel widmen sich anwendungsbezogenen Sachverhalten, u.a. der Parameteridentifikation, optimalen Steuerung und Strukturoptimierung. Durch die Bereitstellung der diskutierten Algorithmen und Beispiele als C++-Klassen gewährleistet das Buch einen optimalen Einstieg in die Optimierung.
Mit C++-Programmen zum Download unter www.wiley-vch.de/publish/dt/books/ISBN3-527-34107-2.
More details
Other editions
Additional editions
Person
Content
1.1 Das lineare und das nichtlineare Optimierungsproblem
1.2 Spezialfälle
1.3 Beispiele
2 GRUNDLAGEN
2.1 Definitionen und Bezeichnungen
2.2 Regularitätsbedingungen
2.3 Optimalitätsbedingungen
2.4 Optimale Kriterien für spezielle Optimierungsaufgaben
2.5 Wünschenswerte Eigenschaften von Optimierungsverfahren
2.6 Vom C++-Programm zum Expertensystem
3 MATHEMATISCHE HILFSMITTEL
3.1 Lösung von Gleichungssystemen mit der QR-Zerlegung
3.2 Cholesky-Zerlegung
3.3 Eindimensionale Suche
3.4 Fibonacci-Verfahren
3.5 Das Verfahren des Goldenen Schnitts
3.6 Newton-Verfahren
4 PROBLEME UND ALGORITHMEN ALS C++- KLASSEN
4.1 Die Programmiersprache C++
5 LINEARE OPTIMIERUNG
5.1 Das Simplexverfahren
5.2 Das revidierte Simplexverfahren
5.3 Das Ellipsoidverfahren
5.4 Weiterführende Bemerkungen
6 QUADRATISCHE OPTIMIERUNG
6.1 Das Relaxationsverfahre
6.2 Methode der Aktiven Restriktionen von FLETCHER
6.3 Das Verfahren der aktiven Restriktionen von GOLDFARB und IDNANI
7 UNBESCHRÄNKTE NICHTLINEARE OPTIMIERUNG
7.1 Die stochastische Suche
7.2 Das Verfahren der koordinatenweisen Suche
7.3 Das einfache Polytopverfahren
7.4 Das Verfahren des steilsten Abstiegs
7.5 Das Verfahren der konjugierten Gradienten
7.6 Das Newton-Verfahren
7.7 Das Newton-Verfahren mit konsistenter Approximation der Hesse-Matrix
7.8 Das Verfahren der variablen Metrik
8 BESCHRÄNKTE NICHTLINEARE OPTIMIERUNG
8.1 Die adaptive Zufallssuche
8.2 Das erweiterte Polytopverfahren
8.3 Schnittebenenverfahren
8.4 Das Verfahren der Sequentiellen Quadratischen Approximation
8.5 Erweitertes Newton-Verfahren
8.6 Verfahren mit Straffunktionen
9 GLOBALISIERUNG
9.1 Dämpfungs- und Regularisierungsmethoden
9.2 Hybride Methoden
9.3 Einbettungsverfahren
10 INNERE-PUNKTE-METHODEN
10.1 Das Projektionsverfahren
10.2 Primal-duale Einbettungstechnik
11 PARAMETERIDENTIFIKATION
11.1 Das Gauÿ-Newton-Prinzip und ein darauf beruhendes SQP-Verfahre
11.2 Beispiele
11.3 Parameteridentifikation in Differentialgleichungen
12 OPTIMALE STEUERUNG
12.1 Einführung
12.2 Implementierte numerische Methoden
12.3 Beispiele
13 STRUKTUROPTIMIERUNG
13.1 Zusammenhang zwischen Bemessungsvariablen und Zustandsvariablen
13.2 Lösung von Strukturoptimierungsproblemen mit SQP-Verfahren
14 OPTISOFT - EIN C++-SOFTWARE-SYSTEM ZUR OPTIMIERUNG
14.1 Einführung
14.2 Allgemeine Informationen über Optisoft
14.3 Handhabung von Optisoft
14.4 Übersicht über Softwarepakete
15 REFERENZMANUAL
15.1 Aufbau eines C++ -Programms
15.2 Datentypen
15.3 Schlüsselworte
15.4 Operatoren
15.5 Verzweigungen
15.6 Schleifen
15.7 Klassen
16 LITERATUR
1
Einleitung
1.1 Das lineare und das nichtlineare Optimierungsproblem
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.
(1.1)wobei I
die Indexmenge der Ungeichungsrestriktionen bezeichnet. Gleichungsrestriktionen werden der Übersichtlichkeit halber zunächst weggelassen. An geeigneten Stellen werden sie zusätzlich berücksichtigt.
1.2 Definitionen und Bezeichnungen
Für die weiteren Überlegungen benötigen wir folgende Bezeichnungen:
- n-dimensionaler Euklidischer Raum: Rn,
- Menge der reellen Zahlen: R,
- nichtnegativer Orthant des n-dimensionalen Euklidischen Raumes: ,
- Euklidische Norm:
- Betragssummennorm:
- (m, n)-Matrix A: rechteckiges Zahlenschema A = (ai,j) von m * n Zahlen, angeordnet in m Zeilen und n Spalten,
- quadratische Matrix: (m, n)-Matrix A mit m = n,
- Diagonalmatrix A: quadratische Matrix A mit ai j = 0 für i ? j und aii ? 0,
- Einheitsmatrix I: Diagonalmatrix A mit aii = 1,
- obere Dreiecksmatrix A: quadratische Matrix A mit ai j = 0, i > j,
- untere Dreiecksmatrix A: quadratische Matrix A mit ai j = 0, i < j,
- positiv definite Matrix A: quadratische Matrix A mit xTAx > 0 für alle x ? 0,
- symmetrische Matrix A: quadratische Matrix A mit ai j = aji,
- transponierte Matrix AT zu A: Matrix AT mit AT = (aji),
- inverse Matrix A-1 zur Matrix A: Matrix mit der Eigenschaft A * A-1 = I,
- nichtsinguläre Matrix A: die inverse Matrix A-1 zu A existiert,
- orthogonale Matrix A: Matrix mit der Eigenschaft AT = A-1,
- transponierter Vektor: xT = (x1, ., xn),
- Gradient einer Funktion f : Rn R
- Hesse-Matrix einer Funktion f : Rn R
- Lagrange-Funktion für die Aufgabe (1.1)
- Ableitung der Lagrange-Funktion nach den Komponenten des 1. Arguments
- zweite Ableitung der Lagrange-Funktion nach den Komponenten des 1. Arguments
- Indexmenge I(x) der in x aktiven Restriktionen
- Vektor, dessen Komponenten alle gleich 1 sind: e = (1, ., 1)T,
- i-ter Einheitsvektor: ei = (0, ., 0, 1, 0, ., 0)T,
- die Menge G0 := {x : gi(x) < 0, i = 1, ., m}.
1.3 Spezialfälle linearer und nichtlinearer Optimierungsaufgaben
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:
- Allgemeine nichtlineare Zielfunktion f (x).
- Lineare Zielfunktion f (x) = cTx.
- Quadratische Zielfunktion
- Quadratsumme (Regression)
- Maximum von Funktionen f (x) = max fj(x) (j = 1, ., l).
In Bezug auf die Nebenbedingungen N sind folgende Situationen typisch:
- Allgemeine nichtlineare Nebenbedingungen.
- Lineare Nebenbedingungen .
- Keine Nebenbedingungen G = Rn.
In den folgenden Kapiteln werden spezielle Kombinationen von Zielfunktion und Nebenbedingungen eine besondere Rolle spielen:
- lineare Optimierung (L): f 2 + N2,
- quadratische Optimierung (Q): f 3 + N2,
- allgemeine nichtlineare Optimierungsaufgabe (C): f 1 + N1,
- unbeschränkte Minimierung (U): f 1 + N3,
- Regressionsprobleme (P): f 4 + N3, f 4 + N1.
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.
1.4 Anwendungen
Nichtlineare Optimierungsprobleme spielen in vielen Anwendungsbereichen eine wichtige Rolle, z. B. in der
- Luft- und Raumfahrt (Steuerung, Konstruktion),
- Mechanik (Optimierung mechanischer Strukturen, z. B. von Tragwerken),
- Elektrotechnik (Transformatorkonstruktion),
- Chemie (Gleichgewichtsprobleme),
- Medizin, Soziologie (Statistische Probleme),
- Betriebswirtschaft (Planungsmodelle),
- Physik (Kernforschung),
- Energiewesen (Energieverteilung).
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:
1.4.1 Strukturoptimierung
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:
Beispiel 1.1 Ziel ist die Erstellung von Bemessungstafeln für geschweißte I-Träger mit Querschnitten minimalen Gewichts (Abb. 1.1).
Da das Gewicht eines Trägers mit vorgegebener Länge proportional zum Querschnitt ist, lautet die Zielfunktion
Tragsicherheitsnachweise (g1, g2), Beulsicherheitsnachweise (g3, g4) und konstruktive Restriktionen (g5 - g10) führen zu den Nebenbedingungen gi = 0:
wobei Mpl(x) := sF((x1 - x4)x3x4 + (x1 - 2x4)2x2/4).
Die Größen Mv, Nv und sF sind konstante Parameter. Die Anzahl der Variablen ist 4, und es liegen 10 Ungleichheitsrestriktionen vor.
Abb. 1.1 Stahlträger.
1.4.2 Das Least-Squares-Problem
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
(1.2)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...
