Grundlagen und Algorithmen

Optimierung in C++

Claus Richter

le-texDateianlage9783527800797.jpg

Claus Richter

Optimierung in C++

Claus Richter

Optimierung in C++

Grundlagen und Algorithmen

Autor

Claus RichterGerhart-Hauptmann-Str. 101219 DresdenDeutschland

Alle Bücher von Wiley-VCH werden sorgfältigerarbeitet. Dennoch übernehmen Autoren,Herausgeber und Verlag in keinem Fall,einschließlich des vorliegenden Werkes, für dieRichtigkeit von Angaben, Hinweisen undRatschlägen sowie für eventuelle Druckfehlerirgendeine Haftung.

Bibliografische Information derDeutschen NationalbibliothekDie Deutsche Nationalbibliothek verzeichnetdiese Publikation in der Deutschen Nationalbi-bliografie; detaillierte bibliografische Daten sindim Internet über http://dnb.d-nb.de abrufbar.

© 2017WILEY-VCHVerlagGmbH&Co. KGaA,Boschstr. 12, 69469 Weinheim, Germany

Alle Rechte, insbesondere die der Überset-zung in andere Sprachen, vorbehalten. KeinTeil dieses Buches darf ohne schriftliche Ge-nehmigung des Verlages in irgendeiner Form– durch Photokopie, Mikroverfilmung oderirgendein anderes Verfahren – reproduziertoder in eine vonMaschinen, insbesondere vonDatenverarbeitungsmaschinen, verwendbareSprache übertragen oder übersetzt werden.Die Wiedergabe von Warenbezeichnungen,Handelsnamen oder sonstigen Kennzeichen indiesem Buch berechtigt nicht zu der Annahme,dass diese von jedermann frei benutzt werdendürfen. Vielmehr kann es sich auch dann umeingetragene Warenzeichen oder sonstige ge-setzlich geschützte Kennzeichen handeln, wennsie nicht eigens als solche markiert sind.

Umschlaggestaltung Formgeber, Mannheim,DeutschlandSatz le-tex publishing services GmbH, Leipzig,Deutschland

Print ISBN 978-3-527-34107-8ePDF ISBN 978-3-527-80079-7ePub ISBN 978-3-527-80080-3Mobi ISBN 978-3-527-80081-0

Gedruckt auf säurefreiem Papier.

V

Für meine liebe Frau Hannelore

VII

Inhaltsverzeichnis

Vorwort XIII

1 Einleitung 11.1 Das lineare und das nichtlineare Optimierungsproblem 11.2 Definitionen und Bezeichnungen 11.3 Spezialfälle linearer und nichtlinearer Optimierungsaufgaben 21.4 Anwendungen 41.4.1 Strukturoptimierung 41.4.2 Das Least-Squares-Problem 51.4.3 Optimale Steuerung 6

2 Grundlagen 92.1 Regularitätsbedingungen 92.1.1 Slater-Bedingung 92.1.2 Abadie-Bedingung 92.1.3 Bedingung der linearen Unabhängigkeit – LICQ 102.1.4 Constraint Qualification 102.1.5 Bemerkungen 102.2 Optimalitätsbedingungen 102.2.1 Optimalitätskriterium mittels zulässiger Richtungen 112.2.2 Karush-Kuhn-Tucker-Bedingung 112.2.3 Bezeichnungen 112.2.4 Notwendige Bedingungen 2. Ordnung 122.2.5 Hinreichende Bedingungen 2. Ordnung 122.2.6 Strenge hinreichende Bedingungen 2. Ordnung 132.3 Optimalitätskriterien für spezielle Optimierungsaufgaben 132.4 Wünschenswerte Eigenschaften von Optimierungsverfahren 142.4.1 Theoretische Richtung 152.4.2 Empirische Richtung 172.5 Vom C++-Programm zum nutzerfreundlichen Softwaresystem 18

VIII Inhaltsverzeichnis

3 Mathematische Hilfsmittel 213.1 Das Austauschverfahren 223.2 Lösung von Gleichungssystemen mit der QR-Zerlegung 263.2.1 Aufbau des Algorithmus 283.3 Cholesky-Zerlegung 293.3.1 Grundlagen des Verfahrens 293.3.2 Aufbau des Algorithmus 303.3.3 Weiterführende Bemerkungen 313.4 Fibonacci-Verfahren 313.4.1 Grundlagen des Verfahrens 313.4.2 Aufbau des Algorithmus 333.5 Das Verfahren des Goldenen Schnitts 343.5.1 Grundlagen des Verfahrens 343.5.2 Aufbau das Algorithmus 353.6 Newton-Verfahren 363.6.1 Grundlagen des Verfahrens 363.6.2 Aufbau des Algorithmus 363.7 Runge-Kutta-Verfahren zur Lösung von Differenzialgleichungen 373.7.1 Weiterführende Bemerkungen 40

4 Probleme und Algorithmen als C++-Klassen 434.1 Die Programmiersprache C++ 434.2 Der Weg zur objektorientierten Programmierung 444.3 Begriffe der objektorientierten Programmierung 454.4 Lösungsverfahren und Probleme als Klassen 46

5 Lineare Optimierung 555.1 Das Simplexverfahren 565.1.1 Grundlagen des Verfahrens 565.1.2 Aufbau des Algorithmus 595.1.3 Konstruktion eines ersten Simplextableaus 615.2 Das revidierte Simplexverfahren 635.2.1 Grundlagen des Verfahrens 635.2.2 Aufbau des Algorithmus 665.3 Weiterführende Bemerkungen 675.4 Das Ellipsoidverfahren 675.4.1 Grundlagen des Verfahrens 675.4.2 Aufbau des Algorithmus 705.5 Weiterführende Bemerkungen 71

6 Quadratische Optimierung 736.1 Das Relaxationsverfahren 746.1.1 Grundlagen des Verfahrens 746.1.2 Aufbau des Algorithmus 746.1.3 Weiterführende Bemerkungen 76

IXInhaltsverzeichnis

6.2 Methode der aktiven Restriktionen von Fletcher 766.2.1 Grundlagen des Verfahrens 766.2.2 Der Algorithmus 776.2.3 Weiterführende Bemerkungen 78

7 Unbeschränkte nichtlineare Optimierung 797.1 Das Verfahren der stochastischen Suche 807.1.1 Grundlagen des Verfahrens 807.1.2 Aufbau des Algorithmus 807.1.3 Weiterführende Bemerkungen 817.2 Das Verfahren der koordinatenweisen Suche 827.2.1 Grundlagen des Verfahrens 827.2.2 Aufbau des Algorithmus 827.3 Das einfache Polytopverfahren 837.3.1 Grundlagen des Verfahrens 837.3.2 Aufbau des Algorithmus 857.3.3 Weiterführende Bemerkungen 867.4 Das Verfahren des steilsten Abstiegs 877.4.1 Grundlagen des Verfahrens 877.4.2 Aufbau des Algorithmus 887.4.3 Weiterführende Bemerkungen 897.5 Das Verfahren der konjugierten Gradienten 897.5.1 Grundlagen des Verfahrens 897.5.2 Aufbau des Algorithmus 917.5.3 Weiterführende Bemerkungen 917.6 Das Newton-Verfahren 927.6.1 Grundlagen des Verfahrens 927.6.2 Aufbau des Algorithmus 937.6.3 Weiterführende Bemerkungen 947.7 Das Newton-Verfahren mit konsistenter Approximation

der Hesse-Matrix 957.7.1 Grundlagen des Verfahrens 957.7.2 Aufbau des Algorithmus 967.7.3 Weiterführende Bemerkungen 977.8 Das Verfahren der variablen Metrik (Quasi-Newton-Verfahren) 977.8.1 Grundlagen des Verfahrens 977.8.2 Aufbau des Algorithmus 997.8.3 Weiterführende Bemerkungen 100

8 Beschränkte nichtlineare Optimierung 1018.1 Die adaptive Zufallssuche 1028.1.1 Grundlagen des Verfahrens 1028.1.2 Aufbau des Algorithmus 1038.1.3 Weiterführende Bemerkungen 1048.2 Das erweiterte Polytopverfahren 104

X Inhaltsverzeichnis

8.2.1 Grundlagen des Verfahrens 1048.2.2 Algorithmus 1068.2.3 Weiterführende Bemerkungen 1088.3 Das Schnittebenenverfahren 1098.3.1 Grundlagen des Verfahrens 1098.3.2 Aufbau des Algorithmus 1108.3.3 Weiterführende Bemerkungen 1118.4 Das SQP-Verfahren 1128.4.1 Grundlagen des Verfahrens 1128.4.2 Aufbau des Algorithmus 1138.4.3 Weiterführende Bemerkungen 1148.5 Das erweiterte Newton-Verfahren 1148.5.1 Grundlagen des Verfahrens 1148.5.2 Aufbau des Algorithmus 1168.5.3 Weiterführende Bemerkungen 1178.6 Verfahren mit Straf- und Barrierefunktionen 1178.6.1 Grundlagen des Verfahrens 1178.6.2 Der Algorithmus 1198.6.3 Weiterführende Bemerkungen 120

9 Globalisierung 1239.1 Dämpfungs- und Regularisierungsmethoden 1239.2 Hybride Methoden 1279.3 Einbettungsmethoden 128

10 Innere-Punkte-Methoden 13110.1 Das Projektionsverfahren 13110.1.1 Grundlagen des Verfahrens 13110.1.2 Aufbau des Algorithmus 13310.1.3 Weiterführende Bemerkungen 13610.2 Kurzschrittverfahren 13610.2.1 Herleitung des Verfahrens 13610.2.2 Beschreibung des Algorithmus 13810.2.3 Weiterführende Bemerkungen 139

11 Parameteridentifikation 14111.1 Parameterschätzung auf der Grundlage linearer

Quadratmittelprobleme 14211.2 Nichtlineare Parameterschätzung und nichtlineare

Optimierungsverfahren 14511.3 Das Gauß-Newton-Prinzip und ein darauf beruhendes Verfahren 14611.3.1 Aufbau des Algorithmus 14711.4 Parameterschätzung und SQP-Verfahren 14911.5 Parameteridentifikation in Differenzialgleichungen 15011.5.1 Grundlagen 150

XIInhaltsverzeichnis

11.5.2 Weiterführende Bemerkungen 152

12 Optimale Steuerung 15512.1 Einführung 15512.2 Umwandlung in eine nichtlineare Optimierungsaufgabe 15512.3 Aufbau des Algorithmus 15612.4 Implementierte numerische Methoden 157

13 Form- und Strukturoptimierung 16113.1 Zusammenhang zwischen Bemessungsvariablen und

Zustandsvariablen 16113.2 Lösung von Strukturoptimierungsproblemen mit SQP-Verfahren 16313.3 Ein weiteres Beispiel 166

14 Optisoft – Ein C++-Softwaresystem zur Optimierung 16714.1 Einführung 16714.2 Allgemeine Informationen über Optisoft 16814.3 Handhabung von Optisoft 17014.3.1 Formulierung eines Problems 17114.3.2 Auswahl des Algorithmus 18214.4 Übersicht über Softwarepakete 184

Anhang A Referenzmanual 187

Anhang B Liste der Beispiele 193

Literatur 195

Stichwortverzeichnis 199

XIII

Vorwort

Bücher zur Implementierung numerischer Verfahren der Optimierung sind seitvielen Jahren gefragt. Die Behandlung mathematisch-naturwissenschaftlicher,technischer und ökonomischer Fragestellungen erfordert in wachsendem Um-fang die Lösung linearer oder nichtlinearer Optimierungsaufgaben. Gegenüberden ersten Bemühungen in den 40er- und 50er-Jahren haben sich hierfür dieVoraussetzungen auf dem Gebiet der Informatik wesentlich verbessert. Nichtnur Rechenzeit und Speicherplatz haben eine andere Bewertung erfahren, auchProgrammierparadigmen und die Nutzung von Dialogmöglichkeiten haben sichgeändert. Dieser Entwicklung folgend, werden im vorliegenden Buch Problemeund Lösungsverfahren als Klassen der objektorientierten Programmierung aufge-fasst. Die Formulierung der zu lösenden Optimierungsaufgabe und die Auswahlder Lösungsmethode erfolgt im Dialog, die Ergebnisse der Berechnung werdenautomatisch gespeichert. Im Unterschied zu komplexen Systemen, wie Matlabsind die einzelnen Routinen modifizierbar und separat nutzbar. Seit den Arbei-ten von Kantorovich [1] und Dantzig [2] zum Simplexverfahren hat auch dieEntwicklung effektiver numerischer Verfahren der Optimierung eine stürmi-sche Entwicklung genommen. Ihre theoretische Begründung und sachgerechteImplementierung stellt inzwischen einen eigenständigen Problemkreis dar, wel-cher als Numerik der Optimierung (in englischer Sprache als „ComputationalMathematical Programming“, in russischer Sprache als „Vycislitelnye metodyprogrammirovanija“) bezeichnet wird. Die Aneignung der auf diesem Gebietvorhandenen Erkenntnisse, noch mehr aber das Erleben des Zusammenhangsvon beschriebenem Algorithmus, umgesetztem Programm und bereitgestellterNutzeroberfläche werden zum Bedürfnis des an der Optimierung interessiertenPraktikers. Gegenstand des Buches sind deshalb nicht in erster Linie theoreti-sche Grundlagen, sondern Fragen der praktischen Realisierung der Verfahrenmit modernen Mitteln der Informatik. Es soll einen Einstieg in die Behandlungvon Optimierungsaufgaben auf Computern ermöglichen.

Für praktische Hilfeleistungen beim Zustandekommen des Buches bin ichKlaus Schönefeld zu Dank verpflichtet. In gleicher Weise danke ich Thomas Cas-sebaum für die Möglichkeit, die von ihm bereitgestellte Entwicklungsumgebung„SmallCpp“ nutzen zu können und in C++-Fragen in ihm jederzeit einen gutenGesprächspartner gefunden zu haben. Ermutigende Worte und gute Ratschläge

XIV Vorwort

vieler Kollegen, insbesondere von Diethard Pallaschke, Oleg Burdakov, ManfredGrauer und Gerd Langensiepen, haben den Entstehungsprozess befördert. DemWiley-Verlag danke ich für die Möglichkeit, die Ergebnisse meiner Überlegungenzu publizieren. Schließlich möchte ich meiner Frau Hannelore für das Verständ-nis danken, mit dem sie die Belastung mitgetragen hat, welche dem Autor ausdem Schreiben eines Buches erwächst. Die Publikation von Algorithmen undProgrammen schließt zu erwartende Kritiken und Hinweise von vornherein ein.Sie werden von mir sorgfältig berücksichtigt und in die Aufbereitung weitererProgrammversionen eingearbeitet.

Claus Richter

1

1Einleitung

1.1Das lineare und das nichtlineare Optimierungsproblem

Im vorliegenden Buch werden Optimierungsaufgaben betrachtet, die dadurchcharakterisiert sind, dass eine lineare oder nichtlineare Zielfunktion f unter li-nearen oder nichtlinearen Ungleichungsnebenbedingungen minimiert wird, d. h.

f (x) = min! bei x ∈ G = {x : gi(x) ≤ 0 i ∈ I} , (1.1)wobei I

I = {i : i = 1, … , m}

die Indexmenge der Ungeichungsrestriktionen bezeichnet. Gleichungsrestriktio-nen werden der Übersichtlichkeit halber zunächst weggelassen. An geeignetenStellen werden sie zusätzlich berücksichtigt.

1.2Definitionen 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: Rn+,∙ Euklidische Norm: ∥ x ∥2= (xTx)1∕2,∙ Betragssummennorm: ∥ x ∥1=

∑mi=1 |xi|,

∙ (m, n)-Matrix A: rechteckiges Zahlenschema A = (ai, j) von m ∗ n Zahlen, an-geordnet 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,

Optimierung in C++, 1. Auflage. Claus Richter.©2017WILEY-VCHVerlagGmbH&Co.KGaA.Published2017byWILEY-VCHVerlagGmbH&Co.KGaA.

2 1 Einleitung

∙ positiv definite Matrix A: quadratische Matrix A mit xTAx > 0 für alle x ≠ 0,∙ symmetrische Matrix A: quadratische Matrix A mit ai j = a ji,∙ transponierte Matrix AT zu A: Matrix AT mit AT = (a ji),∙ 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

∇ f (x) :=(

𝜕

𝜕x1f (x), …, 𝜕

𝜕xnf (x)

)T,

∙ Hesse-Matrix einer Funktion f : Rn → R

∇2 f (x)i j :=𝜕2

𝜕xi𝜕x jf (x) i, j = 1, …, n ,

∙ Lagrange-Funktion für die Aufgabe (1.1)

L(x , u) = f (x) +m∑i=1

uigi(x) ,

∙ Ableitung der Lagrange-Funktion nach den Komponenten des 1. Arguments

∇1L(x , u) = ∇ f (x) +m∑i=1

ui∇gi(x) ,

∙ zweite Ableitung der Lagrange-Funktion nach den Komponenten des 1. Argu-ments

∇11L(x , u) = ∇11 f (x) +m∑i=1

ui∇11gi(x) ,

∙ Indexmenge I(x) der in x aktiven Restriktionen

I(x) = {i : gi(x) = 0, i ∈ {1, … , m}} ,

∙ 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.3Spezialfälle linearer und nichtlinearer Optimierungsaufgaben

Besitzen Zielfunktion f und der zulässige Bereich G bzw. Nebenbedingungen giund g j eine spezielle Gestalt, so können zur Lösung von (1.1) spezielle Ver-fahren herangezogen werden. Für die Zielfunktion f sind folgende Strukturen

31.3 Spezialfälle linearer und nichtlinearer Optimierungsaufgaben

interessant:

1. Allgemeine nichtlineare Zielfunktion f (x).2. Lineare Zielfunktion f (x) = cTx.3. Quadratische Zielfunktion f (x) = 1

2xTCx + dTx.

4. Quadratsumme (Regression)

f (x) =m∑i=1

(yi − f (x , ti ))2 , yi – Messwerte zum Messpunkt ti .

5. Maximum von Funktionen f (x) = max f j(x) ( j = 1, …, l).

In Bezug auf die Nebenbedingungen N sind folgende Situationen typisch:

1. Allgemeine nichtlineare Nebenbedingungen.2. Lineare Nebenbedingungen gi(x) = aTi x + bi (i = 1, …, m).3. Keine Nebenbedingungen G = Rn .

In den folgenden Kapiteln werden spezielle Kombinationen von Zielfunktion undNebenbedingungen 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 imple-mentierten Beispiele im Programmsystem „Optisoft“ verwendet. Über die dar-gestellten Kombinationen von Zielfunktion und Nebenbedingungen hinaus spie-len Aufgaben der nichtglatten Optimierung eine besondere Rolle. Diese findenim vorliegenden Buch keine Beachtung. Gleiches gilt auch für Optimierungsauf-gaben mit sehr vielen Variablen: n > 100, sofern sie nicht als Teilprobleme zurLösung von (1.1) auftreten.

Obwohl die spezifische Gestalt von Zielfunktion und Nebenbedingungen inter-essant ist, wie etwa in der geometrischen Optimierung

f (x) =r∑

k=1ck(o)

n∏i=1

xia0ik

g j(x) =r∑

k=1ck( j)

n∏i=1

xiai j ( j = 1, …, m) ,

wird diese nicht explizit berücksichtigt.In der Betrachtung von Optimierungsverfahren gehen wir von dem Grundmo-

dell (1.1) aus. Für Least-Square-Probleme in Differenzialgleichungsmodellen undbei Strukturoptimierungsproblemen liegen spezielle Aufgaben zugrunde. Diesewerden in den folgenden Kapiteln näher erläutert.

4 1 Einleitung

1.4Anwendungen

Nichtlineare Optimierungsprobleme spielen in vielen Anwendungsbereichen ei-ne 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 Mc-Cormick [3] oder Beightler und Phillips [4]. Einige mathematische Fragestellun-gen, welche bei der Lösung praktischer Probleme auf Optimierungsverfahren zu-rückgreifen, werden im Buch näher betrachtet:

1.4.1Strukturoptimierung

Die Strukturoptimierung wird schon seit einigen Jahren in der computergestütz-ten Konstruktion eingesetzt. In der zugrundeliegenden Aufgabenstellung wird da-bei zwischen Querschnitts-, Form-, und Topologieoptimierung (der eigentlichenStrukturoptimierung) unterschieden. Grundlegende Fragestellung ist dabei, dieStruktur und die Abmessungen von Konstruktionen derart zu wählen, dass zumeinen die mechanischen Randbedingungen erfüllt und zum anderen der Materi-aleinsatz und damit die Kosten möglichst gering sind.

Obwohl die Berücksichtigung der Nebenbedingungen oft die Koppelung mitkomplizierten Berechnungsvorschriften – z. B. FEM-Solvern – erfordert, soll dasGrundprinzip an folgendem Beispiel erläutert werden:

Beispiel 1.1 Ziel ist die Erstellung von Bemessungstafeln für geschweißte I-Trägermit Querschnitten minimalen Gewichts (Abb. 1.1).Da das Gewicht eines Trägers mit vorgegebener Länge proportional zum Quer-schnitt ist, lautet die Zielfunktion

f (x) = (x1 − 2x4)x2 + 2x3x4 .

51.4 Anwendungen

Tragsicherheitsnachweise (g1 , g2), Beulsicherheitsnachweise (g3, g4) und kon-struktive Restriktionen (g5 − g10) führen zu den Nebenbedingungen gi ≤ 0:

g1(x) =

{Mpl(x) −Mv für |Nv|∕ f (x) < 0.1σFMpl(x)(1.1 − |Nv|∕( f (x)σF )) − Mv sonst

g2(x) = 0.8 f (x)σF − Nv

g3(x) = 17 −x3x4

g4(x) =

{43 − x1∕x2 für |Nv|∕ f (x) < 0.27σF70(1.1 − 1.4|Nv|∕( f (x)σF )) − x1∕x2 sonst

g5(x) = 1000 − x1g6(x) = 60 − x2g7(x) = 60 − x4g8(x) = x2 − 5g9(x) = x4 − 5

g10(x) =x14

− x3

wobei Mpl(x) := σF ((x1 − x4)x3x4 + (x1 − 2x4)2x2∕4).Die Größen Mv , Nv und σF sind konstante Parameter. Die Anzahl der Variablenist 4, und es liegen 10 Ungleichheitsrestriktionen vor.

Abb. 1.1 Stahlträger.

1.4.2Das Least-Squares-Problem

Spezielle nichtlineare Optimierungsaufgaben treten bei der Parameterbestim-mung von Modellen auf, die einen in Natur- oder Technikwissenschaften vor-liegenden Zusammenhang qualitativ beschreiben. Sind über diesen Zusammen-hang Resultate von Experimenten bekannt, kann man die Methode der kleinsten

6 1 Einleitung

Quadrate anwenden, um die Koeffizienten näherungsweise zu bestimmen. Daszugehörige Optimierungsproblem lautet:

f (z) = ∥z∥ = min!

bei

zi = hi(x) = yi − y(x , ti ) (i = 1, …, l) ,g j(x) = 0 ( j = 1, …, m1)g j(x) ≤ 0 ( j = m1 + 1, …, m)

a ≤ x ≤ b . (1.2)

Hierbei sind

y(x , t) – die gewählte Modellfunktion,x – der Parametervektor, dessen Komponentenwerte zu bestimmen sindti – der i-te Wert der (u. U. vektorwertigen) unabhängigen Veränderli-

chen,yi – die i-te Beobachtung der (u. U. vektorwertigen) unabhängigen Verän-

derlichen,a , b – Schrankenvektoren für den Vektor x.

Entsprechend der Wahl der Norm haben wir es mit einer linearen oder quadra-tischen Zielfunktion zu tun. Die vorliegende Formulierung gestattet die Berück-sichtigung zusätzlicher Nebenbedingungen. Beim Vorliegen von Differenzialglei-chungen wird die Aufgabe wie folgt modifiziert:

f (z) = ∥z∥ = min!

bei

zi = yi j − y(x , t j)g j(x) = 0g j(x) ≤ 0

ẏ = φ(x , y, t)

a ≤ x ≤ b . (1.3)

Eventuell treten zusätzlich Anfangsbedingungen der Form

y(to) = yo (1.4)

auf.Diese können gegebenenfalls in die Least-Square-Formulierung einbezogen

werden.

1.4.3Optimale Steuerung

Das Problem der optimalen Steuerung besteht darin, eine Funktion unter Dif-ferenzialgleichungsnebenbedingungen sowie Anfangs- und Endbedingungen zu