Diskretisierung und numerische Optimierung - Exam

Aufgabe 1)

Kontext des Hauptproblems:Betrachte die Diskretisierung eines kontinuierlichen Problems auf dem Intervall \([a, b]\). Verwende eine gleichmäßige Knotenaufteilung mit den Knotenpunkten \(\textbf{X} = \{x_0, x_1, ..., x_n\}), wobei \(x_i = a + i \Delta x\) mit \(\Delta x = \frac{b-a}{n}\). Für eine Funktion \(f(x)\) definiere die diskrete Interpolation und diskreten Operatoren, um bestimmte Berechnungen durchzuführen.

• Knotenmengen: Wähle eine gleichmäßige Knotenteilung.
• Interpolation: Verwende lineare Interpolation zwischen den Knoten.
• Diskrete Operatoren: Diskretisiere die Ableitung über finite Differenzen.
• Fehleranalyse: Analysiere den Fehler der Diskretisierung der Ableitung.

a)

Teilaufgabe 1:(a) Stelle die lineare Interpolation \(L(x)\) für einen Funktionswert zwischen den Knoten \(x_i\) und \(x_{i+1}\) dar, wenn \(f(x_i) = f_i\) und \(f(x_{i+1}) = f_{i+1}\).(b) Bestimme allgemeine Formel für die lineare Interpolation für einen beliebigen Punkt \(x\) im Intervall \([a, b]\).Zeige alle notwendigen Schritte in Deiner Berechnung.

Lösung:

Teilaufgabe 1:(a) Stelle die lineare Interpolation \(L(x)\) für einen Funktionswert zwischen den Knoten \(x_i\) und \(x_{i+1}\) dar, wenn \(f(x_i) = f_i\) und \(f(x_{i+1}) = f_{i+1}\).Die lineare Interpolation basiert auf der Annahme, dass der Funktionswert zwischen zwei benachbarten Knotenpunkten linear variiert. Das bedeutet, dass wir eine Gerade finden, die durch die Punkte \((x_i, f_i)\) und \((x_{i+1}, f_{i+1})\) verläuft. Die Gleichung einer Linie (Geraden) in der allgemeinen Form ist gegeben durch:

L(x) = f_i + \frac{f_{i+1} - f_i}{x_{i+1} - x_i} (x - x_i)

(b) Bestimme eine allgemeine Formel für die lineare Interpolation für einen beliebigen Punkt \(x\) im Intervall \([a, b]\).Angenommen, \(x\) befindet sich zwischen den Knotenpunkten \(x_i\) und \(x_{i+1}\). Die allgemeine Gleichung für die lineare Interpolation kann dann aus der Formel im Teil (a) abgeleitet werden. Wir benutzen dabei die Definition von \(x_i\) und \(x_{i+1}\) als allgemeine Knotenpunkte, wobei gilt:

x_i = a + i \, \Delta x

x_{i+1} = a + (i+1) \, \Delta x

Setze diese Definitionen in die lineare Interpolationsformel ein:

L(x) = f_i + \frac{f_{i+1} - f_i}{\Delta x} (x - x_i)

Da \(\Delta x = \frac{b - a}{n}\), vereinfacht sich der Nenner zu \(\Delta x\), sodass wir erhalten:

L(x) = f_i + \frac{f_{i+1} - f_i}{\Delta x} (x - x_i)

Um dies allgemeiner auszudrücken, lassen sich die Werte \(x_i = a + i \, \Delta x\) und \(x\) durch folgende Gleichung beschreiben:

x = x_i + \lambda \, (x_{i+1} - x_i) = x_i + \lambda \, \Delta x

wobei \( 0 \leq \lambda \leq 1\). Dadurch ergibt sich:

L(x) = f_i + \lambda ( f_{i+1} - f_i )

Dies ist die allgemeine Formel für die lineare Interpolation zwischen zwei benachbarten Knotenpunkten \(x_i\) und \(x_{i+1}\) für einen beliebigen Punkt \(x\) im Intervall \([a, b]\).

b)

Teilaufgabe 2:(a) Diskretisiere die erste Ableitung von \(f(x)\) unter Verwendung der Vorwärtsdifferenz. Gib die Approximation der Ableitung an.(b) Führe eine Fehleranalyse für die diskrete Approximierung der ersten Ableitung durch. Bestimme den Fehlergrad \(\text{Fehler} = O(\Delta x)\) und erkläre den Ursprung dieses Fehlers.Mache deutlich, welche Annahmen Du bei der Fehleranalyse machst und zeige alle Schritte Deiner Berechnung.

Lösung:

Teilaufgabe 2:(a) Diskretisiere die erste Ableitung von \(f(x)\) unter Verwendung der Vorwärtsdifferenz. Gib die Approximation der Ableitung an.Die Vorwärtsdifferenz wird verwendet, um die Ableitung einer Funktion \(f(x)\) an einem Punkt \(x_i\) zu approximieren. Die Formel für die Vorwärtsdifferenz lautet:

f'(x_i) \approx \frac{f(x_{i+1}) - f(x_i)}{\Delta x}

Hierbei ist \(\Delta x = \frac{b - a}{n}\) die Breite des Intervalls zwischen den Knotenpunkten. Diese Approximation basiert auf der Annahme, dass der Unterschied zwischen den benachbarten Funktionwerten \(f(x_{i+1})\) und \(f(x_i)\) durch die Breite des Intervalls \(\Delta x\) geteilt wird.(b) Führe eine Fehleranalyse für die diskrete Approximierung der ersten Ableitung durch. Bestimme den Fehlergrad \(\text{Fehler} = O(\Delta x)\) und erkläre den Ursprung dieses Fehlers.Für die Fehleranalyse nehmen wir an, dass die Funktion \(f(x)\) genug differenzierbar ist und dass ihr Taylor-Reihe am Punkt \(x_i\) verwendet werden kann. Unter Verwendung der Taylor-Reihe ergibt sich:

f(x_{i+1}) = f(x_i + \Delta x) = f(x_i) + f'(x_i) \Delta x + \frac{f''(\xi)}{2} \Delta x^2

Hierbei ist \(\xi\) ein Punkt im Intervall \([x_i, x_{i+1}]\).Wir setzten diese Taylor-Reihe in die Vorwärtsdifferenzenformel ein:

\frac{f(x_{i+1}) - f(x_i)}{\Delta x} = \frac{f(x_i) + f'(x_i) \Delta x + \frac{f''(\xi)}{2} \Delta x^2 - f(x_i)}{\Delta x}

Das vereinfacht sich zu:

\frac{f(x_{i+1}) - f(x_i)}{\Delta x} = f'(x_i) + \frac{f''(\xi)}{2} \Delta x

Wir sehen, dass der Fehler der Vorwärtsdifferenzformel von der Größe \(\Delta x\) abhängt und proportional zu \(\Delta x\) ist. Daher ist der Fehlergrad:

\text{Fehler} = O(\Delta x)

Der Ursprung dieses Fehlers liegt in der Vernachlässigung der höheren Ordnungsanteile der Taylor-Reihe (in diesem Fall die Terme ab \(\Delta x^2\)). Diese Terme bestimmen den Fehler der Näherung.Zusammengefasst machen wir bei der Fehleranalyse folgende Annahmen:

• Die Funktion \(f(x)\) ist ausreichend differenzierbar, mindestens bis zur zweiten Ableitung.
• Die Taylor-Reihe der Funktion \(f(x)\) konvergiert am Punkt \(x_i\).

Alle Berechnungsschritte veranschaulichen, dass der Fehler bei der Verwendung der Vorwärtsdifferenz für die Diskretisierung der Ableitung proportional zu \(\Delta x\) ist, was diesen zu einer Methode erster Ordnung macht.

Aufgabe 2)

Betrachte die Funktion \(f(x) = \text{sin}(x)\) auf dem Intervall \([0, \frac{\text{π}}{2}]\). Du sollst die Approximation der ersten Ableitung von \(f\) bei \(x = \frac{\text{π}}{4}\) mithilfe von Vorwärtsdifferenzen, Rückwärtsdifferenzen und zentralen Differenzen untersuchen. Der Fehler soll analysiert und verglichen werden. Verwende dazu eine Schrittweite \(h\) von \(0.1\). Berechne die numerischen Näherungen und die Fehlerabschätzungen.

a)

Berechne die erste Ableitung von \(f(x) = \text{sin}(x)\) bei \(x = \frac{\text{π}}{4}\) mithilfe der Vorwärtsdifferenzenformel \(f'(x) \approx \frac{f(x+h) - f(x)}{h}\). Bestimme anschließend den absoluten Fehler dieser Methode.

Lösung:

Berechne die erste Ableitung von f(x) = sin(x) bei x = \( \frac{\pi}{4} \) mithilfe der Vorwärtsdifferenzenformel

• Gegeben ist die Funktion f(x) = sin(x).
• Die Ableitung f'(x) von f(x) = sin(x) ist bekanntlich f'(x) = cos(x).
• Der Wert x, den wir untersuchen, ist \( x = \frac{\pi}{4} \).
• Die Schrittweite h ist gegeben als h = 0.1.

Schritte zur Berechnung der Vorwärtsdifferenzen

• 1. Berechne f(x + h): \( f\left( \frac{\pi}{4} + 0.1 \right) = \sin\left( \frac{\pi}{4} + 0.1 \right) \)
• 2. Berechne f(x): \( f\left( \frac{\pi}{4} \right) = \sin\left( \frac{\pi}{4} \right) \)
• 3. Verwende die Vorwärtsdifferenzenformel: \( f'\left( \frac{\pi}{4} \right) \approx \frac{f\left( \frac{\pi}{4} + 0.1 \right) - f\left( \frac{\pi}{4} \right)}{0.1} \)
• 4. Der Wert von \( f\left( \frac{\pi}{4} + 0.1 \right) \) ist: \( \sin\left( 0.8854 \right) = 0.7742 \)
• 5. Der Wert von \( f\left( \frac{\pi}{4} \right) \) ist: \( \sin\left( 0.7854 \right) = 0.7071 \)
• 6. Der approximierte Wert von \( f'\left( \frac{\pi}{4} \right) \) ist: \( \frac{0.7742 - 0.7071}{0.1} = 0.671 \)

Berechnung des absoluten Fehlers:

• 1. Der exakte Wert der Ableitung von f(x) = sin(x) bei \( x = \frac{\pi}{4} \) ist f'(\left( \frac{\pi}{4} \right)) = \cos\left( \frac{\pi}{4} \). \( \cos\left( \frac{\pi}{4} \right) = \frac{1}{\sqrt{2}} = 0.7071 \)
• 2. Berechne den absoluten Fehler: \( \text{absoluter Fehler} = | \text{exakter Wert} - \text{approximierter Wert} | = | 0.7071 - 0.671 | = 0.0361 \)

b)

Berechne die erste Ableitung von \(f(x) = \text{sin}(x)\) bei \(x = \frac{\text{π}}{4}\) mithilfe der zentralen Differenzenformel \(f'(x) \approx \frac{f(x+h) - f(x-h)}{2h}\). Bestimme anschließend den absoluten Fehler dieser Methode.

Lösung:

Berechne die erste Ableitung von f(x) = sin(x) bei x = \( \frac{\pi}{4} \) mithilfe der zentralen Differenzenformel

• Gegeben ist die Funktion f(x) = sin(x).
• Die Ableitung f'(x) von f(x) = sin(x) ist bekanntlich f'(x) = cos(x).
• Der Wert x, den wir untersuchen, ist \( x = \frac{\pi}{4} \).
• Die Schrittweite h ist gegeben als h = 0.1.

Schritte zur Berechnung der zentralen Differenzen

• 1. Berechne f(x + h): \( f\left( \frac{\pi}{4} + 0.1 \right) = \sin\left( \frac{\pi}{4} + 0.1 \right) \)
• 2. Berechne f(x - h): \( f\left( \frac{\pi}{4} - 0.1 \right) = \sin\left( \frac{\pi}{4} - 0.1 \right) \)
• 3. Verwende die zentrale Differenzenformel: \( f'\left( \frac{\pi}{4} \right) \approx \frac{f\left( \frac{\pi}{4} + 0.1 \right) - f\left( \frac{\pi}{4} - 0.1 \right)}{2h} \)
• 4. Der Wert von \( f\left( \frac{\pi}{4} + 0.1 \right) \) ist: \( \sin\left( 0.8854 \right) = 0.7742 \)
• 5. Der Wert von \( f\left( \frac{\pi}{4} - 0.1 \right) \) ist: \( \sin\left( 0.6854 \right) = 0.6325 \)
• 6. Der approximierte Wert von \( f'\left( \frac{\pi}{4} \right) \) ist: \( \frac{0.7742 - 0.6325}{2 \times 0.1} = \frac{0.1417}{0.2} = 0.7085 \)

Berechnung des absoluten Fehlers:

• 1. Der exakte Wert der Ableitung von f(x) = sin(x) bei \( x = \frac{\pi}{4} \) ist f'(\left( \frac{\pi}{4} \right)) = \cos\left( \frac{\pi}{4} \). \( \cos\left( \frac{\pi}{4} \right) = \frac{1}{\sqrt{2}} = 0.7071 \)
• 2. Berechne den absoluten Fehler: \( \text{absoluter Fehler} = | \text{exakter Wert} - \text{approximierter Wert} | = | 0.7071 - 0.7085 | = 0.0014 \)

Aufgabe 4)

Eine Firma möchte die Parameter eines maschinellen Lernmodells mithilfe von Evolutionsstrategien (ES) optimieren. Die Optimierungsfunktion ist hochdimensional und nichtlinear. Es wird eine Population von 100 Lösungskandidaten initialisiert. Die Parametersuche erfolgt über 50 Generationen. Die Mutationsvarianz wird adaptiv angepasst. Der folgende Pseudocode zeigt den Kern des ES-Algorithmus, der verwendet wird:

• Initialisierung: Erzeugung der Anfangspopulation.
• Mutationsschritt: Berechnung der neuen Kandidaten.
• Rekombination: Kombination der Kandidatenlösungen.
• Selektion: Auswahl der besten Kandidaten.
• Anpassung der Mutationsvarianz.

population = initialize_population(100)for generation in range(50):    mutated_population = []    for candidate in population:        new_candidate = mutate(candidate)        mutated_population.append(new_candidate)    recombined_population = recombine(mutated_population)        selected_population = select_best(recombined_population)    population = adapt_variance(selected_population)

a)

Beschreibe den Adaptionsprozess der Mutationsvarianz anhand der Rechenregel \(\text{Neuer\_Wert} = \text{Alter\_Wert} * e^{\tau*Z} \). Erkläre dabei insbesondere die Bedeutung der Parameter \( \tau \) und \( Z \).

Lösung:

Der Adaptionsprozess der Mutationsvarianz ist ein entscheidender Aspekt bei der Optimierung von maschinellen Lernmodellen mittels Evolutionsstrategien (ES). Die Mutationsvarianz bestimmt die Größe der Veränderungen, die an den Kandidatenlösungen vorgenommen werden. Sie wird adaptiv angepasst, um die Suchleistung des Algorithmus zu optimieren. Die Anpassung erfolgt gemäß der Rechenregel:

\(\text{Neuer\textunderscore Wert} = \text{Alter\textunderscore Wert} \cdot e^{\tau \cdot Z}\)

• Der Alte Wert bezeichnet die aktuelle Mutationsvarianz.
• Der Neue Wert bezeichnet die angepasste Mutationsvarianz.
• Der Parameter \(\tau\) ist eine Konstante, die die Stärke der Anpassung bestimmt. Ein kleiner Wert von \(\tau\) führt zu geringeren Anpassungen, während ein größerer Wert zu stärkeren Anpassungen führt.
• Der Parameter \(Z\) ist eine Zufallsvariable, die gewöhnlich aus einer Standardnormalverteilung (\(\mathcal{N}(0,1)\)) gezogen wird. Dies gewährleistet, dass die Anpassung der Mutationsvarianz zufällig und vielfältig ist.

Die Multiplikation des alten Wertes der Mutationsvarianz mit dem Exponentialterm erzeugt eine neue Mutationsvarianz. Dieser Prozess führt dazu, dass die Mutationsvarianz entweder vergrößert oder verkleinert wird. Die Parameter \(\tau\) und \(Z\) sind dafür verantwortlich, das Ausmaß dieser Anpassungen zu steuern, wobei \(\tau\) die Skalierung und \(Z\) die Zufälligkeit bereitstellt. Diese adaptive Anpassung der Mutationsvarianz hilft dem Algorithmus, sich an die verschiedenen Phasen der Optimierung anzupassen – beispielsweise eine größere Varianz in den frühen Phasen, um den Suchraum breit zu erkunden, und eine kleinere Varianz in den späteren Phasen, um präzise Lösungen zu verfeinern.

c)

Erkläre die Bedeutung der Rekombination in Evolutionsstrategien und diskutiere einen Vorteil und einen Nachteil dieses Schritts im Kontext der Optimierung hochdimensionaler Probleme.

Lösung:

Bedeutung der Rekombination in Evolutionsstrategien (ES):

Die Rekombination ist ein entscheidender Schritt in Evolutionsstrategien (ES). Sie dient dazu, neue Kandidatenlösungen zu erzeugen, indem Informationen von mehreren Elternlösungen kombiniert werden. Dies geschieht in der Hoffnung, dass die neuen Lösungen bessere Eigenschaften aufweisen als ihre Eltern und somit eine höhere Fitness aufweisen.

Vorteil der Rekombination:

• Förderung der genetischen Vielfalt: Die Rekombination kombiniert Merkmale aus verschiedenen Elternlösungen und erzeugt dadurch neue, diverse Kandidatenlösungen. Dies hilft, den Suchraum effektiver zu durchsuchen und verhindert das vorzeitige Konvergieren des Algorithmus auf suboptimale Lösungen. Dies ist besonders wichtig bei der Optimierung hochdimensionaler Probleme, da eine breite Erkundung des Suchraums erforderlich ist, um die globale Optimallösung zu finden.

Nachteil der Rekombination:

• Erhöhte Rechenkomplexität: Die Rekombination erhöht die Rechenkomplexität des Algorithmus, da sie zusätzliche Schritte zur Erzeugung und Bewertung neuer Kandidaten vorsieht. Dies kann dazu führen, dass der Algorithmus mehr Zeit und Rechenressourcen benötigt, insbesondere bei hochdimensionalen Problemen oder großen Populationen. In solchen Fällen muss ein Gleichgewicht zwischen der Qualität der gefundenen Lösungen und der benötigten Rechenzeit gefunden werden.

d)

Welche Eigenschaften sollte die Selektion aufweisen, um eine effiziente und effektive Optimierung zu gewährleisten? Nenne und erläutere zwei solcher Eigenschaften.

Lösung:

Die Selektion ist ein entscheidender Schritt in Evolutionsstrategien (ES), um sicherzustellen, dass die besten Kandidatenlösungen in die nächste Generation überführt werden. Um eine effiziente und effektive Optimierung zu gewährleisten, sollte die Selektion bestimmte Eigenschaften aufweisen:

Eigenschaft 1: Selektive Druck

• Erklärung: Der selektive Druck bezeichnet die Intensität, mit der bessere Lösungen bevorzugt werden. Ein höherer selektiver Druck bedeutet, dass stärkere Selektion angewandt wird, sodass nur die besten Kandidaten überleben und sich fortpflanzen. Dies führt zu einer effizienteren Optimierung, da es wahrscheinlicher ist, dass die besten Eigenschaften in der Population erhalten und weiter verbessert werden.
• Bedeutung: Ein ausgewogener selektiver Druck ist entscheidend. Ein zu hoher selektiver Druck kann jedoch zur Verarmung der genetischen Vielfalt führen, was zu einer vorzeitigen Konvergenz auf suboptimale Lösungen führen könnte. Ein zu niedriger selektiver Druck kann hingegen die Optimierung verlangsamen, da auch schlechtere Lösungen überleben und Ressourcen verbrauchen.

Eigenschaft 2: Diversitätserhaltung

• Erklärung: Die Selektion sollte Mechanismen enthalten, die die genetische Vielfalt innerhalb der Population aufrechterhalten. Dies kann durch Techniken wie Fitness Sharing oder der Förderung von Diversität innerhalb der Population erreicht werden. Diese Mechanismen verhindern, dass die Population zu homogen wird und helfen, das Risiko der vorzeitigen Konvergenz zu minimieren.
• Bedeutung: Die Erhaltung der Vielfalt ist besonders wichtig bei der Optimierung hochdimensionaler und nichtlinearer Probleme, da sie sicherstellt, dass der Algorithmus ein breites Spektrum an Lösungsmöglichkeiten erkundet und nicht in lokalen Optima stecken bleibt.