Nichtlineare Optimierung - Exam

Aufgabe 2)

Angenommen, Du hast die Funktion f gegeben durch:

• f(x, y) = x^2 + y^2 + 10xy + 25

Untersuche nun die folgenden Eigenschaften der Funktion im Hinblick auf Gradienten, Laplacians und Jacobians.

b)

Bestimme den Laplace-Operator der Funktion f. Zeige die vollständige Berechnung der zweiten partiellen Ableitungen und die Summe dieser Ableitungen. (Hinweis: Der Laplace-Operator ist die Summe der zweiten partiellen Ableitungen)

Lösung:

Um den Laplace-Operator der Funktion f zu berechnen, folge diesen Schritten:

• Gegeben ist die Funktion: f(x, y) = x^2 + y^2 + 10xy + 25

Der Laplace-Operator (oder Laplacian) einer Funktion f ist die Summe der zweiten partiellen Ableitungen. Diesen notieren wir häufig als ∆f. Für eine Funktion mit zwei Variablen, x und y, sieht der Laplace-Operator wie folgt aus:

• ∆f = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2}

Lasst uns die zweiten partiellen Ableitungen berechnen:

Zweite partielle Ableitung von f bezüglich x:

• f(x, y) = x^2 + y^2 + 10xy + 25
• Erste Ableitung nach x ist: \frac{\partial f}{\partial x} = 2x + 10y
• Zweite Ableitung nach x ist: \frac{\partial^2 f}{\partial x^2} = \frac{\partial}{\partial x}(2x + 10y) = 2

Zweite partielle Ableitung von f bezüglich y:

• f(x, y) = x^2 + y^2 + 10xy + 25
• Erste Ableitung nach y ist: \frac{\partial f}{\partial y} = 2y + 10x
• Zweite Ableitung nach y ist: \frac{\partial^2 f}{\partial y^2} = \frac{\partial}{\partial y}(2y + 10x) = 2

Somit ergibt sich der Laplace-Operator:

• ∆f = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2} = 2 + 2 = 4

Der Laplace-Operator der Funktion f lautet also:

• ∆f = 4

Aufgabe 3)

In dieser Aufgabe wirst Du Evolutionsstrategien und genetische Algorithmen anwenden, um ein globales Optimum in einem komplexen, nichtlinearen Suchraum zu finden. Du sollst auf die Mechanismen dieser Verfahren eingehen, konkrete Beispiele ausarbeiten und mathematische Berechnungen durchführen.

a)

Erkläre den grundlegenden Unterschied zwischen Evolutionsstrategien und genetischen Algorithmen. Gehe dabei auf die Mechanismen der Mutation, Selektion und Rekombination ein und skizziere, wie diese in beiden Methoden eingesetzt werden.

Lösung:

Evolutionsstrategien vs. Genetische Algorithmen

Der grundlegende Unterschied zwischen Evolutionsstrategien und genetischen Algorithmen liegt in den detaillierten Mechanismen, die zur Lösung von Optimierungsproblemen verwendet werden. Im Folgenden sind die Hauptaspekte Mutation, Selektion und Rekombination für beide Verfahren dargestellt:

• Mutation:
  • Evolutionsstrategien (ES): Bei Evolutionsstrategien wird die Mutation als wichtigster Mechanismus betrachtet. Die Mutationen werden typischerweise durch Hinzufügen von Zufallswerten zu den Parameterwerten erzeugt. Diese Zufallswerte stammen gewöhnlich aus einer Normalverteilung. Die Mutation zielt darauf ab, einen lokalen Suchraum gründlich zu erkunden und wird oft durch selbstadaptive Mechanismen gesteuert, bei denen die Mutationsschritte dynamisch angepasst werden.
  • Genetische Algorithmen (GA): Bei genetischen Algorithmen spielt die Mutation eine unterstützende Rolle und dient dazu, genetische Vielfalt zu bewahren und neue Lösungen zu generieren. Die Mutation erfolgt durch Ändern eines oder mehrerer Gene innerhalb eines Chromosoms (Lösungskandidaten). Die Mutationsrate ist oft niedrig, um die Stabilität des Algorithmus zu gewährleisten.
• Selektion:
  • Evolutionsstrategien (ES): Die Selektion bei Evolutionsstrategien basiert auf einem (μ, λ)- oder (μ + λ)-Prinzip, wobei μ die Anzahl der Eltern ist und λ die Anzahl der Nachkommen. Im (μ, λ)-Schema werden nur die besten λ Nachkommen zur nächsten Generation ausgewählt. Im (μ + λ)-Schema konkurrieren sowohl die Eltern als auch die Nachkommen um die Platzierung in der nächsten Generation.
  • Genetische Algorithmen (GA): Genetische Algorithmen verwenden vielfältige Selektionsmethoden wie Roulette-Rad-Selektion, Turnierselektion oder Rangbasierte Selektion. Ziel ist es, diejenigen Individuen auszuwählen, die die besten Eigenschaften besitzen, um ihre Gene an die nächste Generation weiterzugeben. Dies fördert das Überleben der am besten angepassten Individuen.
• Rekombination (Crossover):
  • Evolutionsstrategien (ES): Bei Evolutionsstrategien ist die Rekombination weniger dominant und wird oft optional eingesetzt. Wenn verwendet, werden Rekombinationsmethoden wie intermediäre Rekombination (Mittelwertbildung) oder diskrete Rekombination (Austausch von Genen zwischen zwei Eltern) eingesetzt.
  • Genetische Algorithmen (GA): Im Gegensatz dazu spielt die Rekombination bei genetischen Algorithmen eine zentrale Rolle. Die Crossover-Operatoren wie Einpunkt-, Zweipunkt- oder Uniform-Crossover kombinieren Gene zweier Eltern, um neue Nachkommen zu erzeugen. Dies ermöglicht die Exploration neuer Lösungen durch Mixen vorhandener Gene und trägt erheblich zur Vielfalt bei.

Zusammenfassend lässt sich sagen, dass Evolutionsstrategien bei der Mutation stärkeren Fokus auf die lokale Suche und selbstadaptive Mechanismen legen, während genetische Algorithmen auf vielseitige Selektions- und Rekombinationsmethoden setzen, um die genetische Vielfalt und Exploitation der Lösungen zu fördern.

b)

Gegeben sei die Fitness-Funktion \( f(x,y) = -((x-3)^2 + (y-2)^2) + 10 \) in einem zweidimensionalen Suchraum. Implementiere in Python einen genetischen Algorithmus, der versucht, das globale Maximum dieser Funktion zu finden. Dokumentiere die einzelnen Schritte des Algorithmus, einschließlich Initialisierung, Selektion, Kreuzung und Mutation.

Lösung:

Implementierung eines genetischen Algorithmus zur Maximierung der Fitness-Funktion

Um das globale Maximum der Fitness-Funktion \(f(x, y) = -((x-3)^2 + (y-2)^2) + 10\) zu finden, werden wir die Mechanismen des genetischen Algorithmus implementieren. Die Schritte umfassen Initialisierung, Selektion, Kreuzung und Mutation. Im Folgenden ist der Python-Code zur Lösung der Aufgabe zu finden, gefolgt von einer Schritt-für-Schritt-Dokumentation:

import numpy as npimport matplotlib.pyplot as plt# Definieren der Fitness-Funktiondef fitness_function(x, y):    return -((x - 3)**2 + (y - 2)**2) + 10# Initialisierung der Populationdef initialize_population(pop_size, x_bounds, y_bounds):    population = np.zeros((pop_size, 2))    population[:, 0] = np.random.uniform(x_bounds[0], x_bounds[1], pop_size)    population[:, 1] = np.random.uniform(y_bounds[0], y_bounds[1], pop_size)    return population# Selektion (Turnierauswahl)def selection(population, fitnesses, num_parents):    parents = np.zeros((num_parents, population.shape[1]))    for i in range(num_parents):        idx = np.random.choice(np.arange(population.shape[0]), size=3, replace=False)        parents[i, :] = population[idx[np.argmax(fitnesses[idx])], :]    return parents# Kreuzung (einfacher Ein-Punkt-Crossover)def crossover(parents, offspring_size):    offspring = np.zeros(offspring_size)    crossover_point = np.uint8(offspring_size[1]/2)    for k in range(offspring_size[0]):        parent1_idx = k % parents.shape[0]        parent2_idx = (k + 1) % parents.shape[0]        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]    return offspring# Mutationdef mutation(offspring_crossover, mutation_rate=0.1):    for idx in range(offspring_crossover.shape[0]):        if np.random.rand() < mutation_rate:            mutation_idx = np.random.randint(0, offspring_crossover.shape[1])            random_value = np.random.uniform(-1.0, 1.0, 1)            offspring_crossover[idx, mutation_idx] += random_value    return offspring_crossover# Parameter des genetischen Algorithmuspop_size = 20num_generations = 50num_parents_mating = 10x_bounds = [0, 6]y_bounds = [0, 4]# Initialisieren der Populationpopulation = initialize_population(pop_size, x_bounds, y_bounds)# Evolution durch genetischen Algorithmusgen_best_fitness = np.zeros(num_generations)for generation in range(num_generations):    # Berechne Fitness der aktuellen Population    fitnesses = fitness_function(population[:, 0], population[:, 1])        # Speichern der besten Fitness    gen_best_fitness[generation] = np.max(fitnesses)        # Selektion der besten Eltern für die Kreuzung    parents = selection(population, fitnesses, num_parents_mating)        # Erzeugen der Nachkommen durch Kreuzung    offspring_crossover = crossover(parents, (pop_size - parents.shape[0], 2))        # Anwenden von Mutation auf die Nachkommen    offspring_mutation = mutation(offspring_crossover)        # Erstellen der neuen Population basierend auf Eltern und Nachkommen    population[0:parents.shape[0], :] = parents    population[parents.shape[0]:, :] = offspring_mutation        print('Generation', generation, 'Best Fitness', gen_best_fitness[generation])# Berechne die beste Lösungbest_fitness_index = np.argmax(fitness_function(population[:, 0], population[:, 1]))best_solution = population[best_fitness_index]print(f'Best solution is x = {best_solution[0]}, y = {best_solution[1]} with fitness = {fitness_function(best_solution[0], best_solution[1])}')# Plot der Fitness-Entwicklungplt.plot(gen_best_fitness)plt.title('Fitness-Entwicklung')plt.xlabel('Generation')plt.ylabel('Fitness')plt.show()

Schritte des Algorithmus:

• Initialisierung: Die Population wird zufällig innerhalb der angegebenen Suchbereiche für x (zwischen 0 und 6) und y (zwischen 0 und 4) initialisiert. Dies bedeutet, dass jede Instanz in der Population zufällige Werte für x und y innerhalb dieser Grenzen erhält.
• Selektion: Eine Turnierselektion wird durchgeführt, um die besten Eltern für die Kreuzung auszuwählen. In jeder Turnierrunde werden drei zufällige Individuen ausgewählt, und das Beste von diesen wird als Elternteil ausgewählt.
• Kreuzung: Ein Ein-Punkt-Crossover wird verwendet, um neue Nachkommen zu erzeugen. Hierbei werden Gene von zwei Elternteilen in einem speziellen Punkt zusammengeführt, um einen neuen Nachkommen zu bilden.
• Mutation: Eine Mutation wird auf die Nachkommen angewendet, um die genetische Vielfalt zu bewahren. Mit einer bestimmten Wahrscheinlichkeit wird ein zufälliges Gen aus jedem Nachkommen um einen kleinen zufälligen Wert verändert.

Der Algorithmus iteriert über mehrere Generationen und aktualisiert in jeder Generation die Population durch Selektion, Kreuzung und Mutation. Die beste gefundene Lösung wird am Ende des Algorithmus ausgegeben und die Fitness-Entwicklung wird visuell dargestellt.

c)

Betrachte eine Population von 10 Individuen, deren Fitness-Werte durch die Funktion aus dem vorherigen Teil berechnet wurden. Führe eine lineare Ranking-Selektion mit einem Selektionsdruck von 2 durch. Berechne explizit die selektierten Individuen und zeige die Berechnungen.

Lösung:

Lineare Ranking-Selektion

Bei der linearen Ranking-Selektion werden die Individuen in der Population entsprechend ihrer Fitness-Werte sortiert und nach Rang statistisch aufgeteilt. Der Selektionsdruck bestimmt, wie stark die Fitness-Ränge die Wahrscheinlichkeit der Auswahl beeinflussen. Ein Selektionsdruck von 2 bedeutet, dass das fitteste Individuum doppelt so wahrscheinlich ausgewählt wird wie das schlechteste Individuum.

Gegeben sei die Funktion \(f(x, y) = -((x-3)^2 + (y-2)^2) + 10\) und eine Population von 10 Individuen. Wir berechnen zunächst die Fitness-Werte und dann die Selektion.

Schritte:

• Berechnung der Fitness-Werte für die Population
• Ranking der Population nach Fitness-Werten
• Berechnung der Selektionswahrscheinlichkeiten basierend auf dem Rang und Selektionsdruck
• Durchführung der tatsächlichen Selektion

Hier ist der Python-Code zur Durchführung der linearen Ranking-Selektion:

import numpy as np# Definieren der Fitness-Funktiondef fitness_function(x, y):    return -((x - 3)**2 + (y - 2)**2) + 10# Initialisieren der Populationpop_size = 10x_bounds = [0, 6]y_bounds = [0, 4]population = np.zeros((pop_size, 2))population[:, 0] = np.random.uniform(x_bounds[0], x_bounds[1], pop_size)population[:, 1] = np.random.uniform(y_bounds[0], y_bounds[1], pop_size)# Berechnung der Fitness-Wertefitnesses = fitness_function(population[:, 0], population[:, 1])# Ranking der Population nach Fitness-Wertenranking_indices = np.argsort(fitnesses)ranked_population = population[ranking_indices]ranked_fitnesses = fitnesses[ranking_indices]# Selektionsdrucks = 2# Berechnung der Selektionswahrscheinlichkeitenlinear_rank_prob = np.array([(2 - s) / pop_size + (2 * i * (s - 1)) / (pop_size * (pop_size - 1)) for i in range(pop_size)])# Normierung der Wahrscheinlichkeiten auf Summe 1linear_rank_prob /= np.sum(linear_rank_prob)# Selektion der Individuen auf Basis der Wahrscheinlichkeitenselected_indices = np.random.choice(np.arange(pop_size), size=pop_size, p=linear_rank_prob)selected_population = ranked_population[selected_indices]# Ausgabe der Resultateprint('Bevölkerung nach Fitness sortiert:')for i in range(pop_size):    print(f'Individuum {i + 1}: x = {ranked_population[i][0]}, y = {ranked_population[i][1]}, Fitness = {ranked_fitnesses[i]}')print('Selektierte Individuen:')for i in range(pop_size):    index = selected_indices[i]    print(f'Individuum {i + 1}: x = {ranked_population[index][0]}, y = {ranked_population[index][1]}, Fitness = {ranked_fitnesses[index]}')

Erklärungen zu den Schritten:

• Fitness-Funktion: Berechnet die Fitness-Werte für jedes Individuum in der Population.
• Ranking: Die Population wird basierend auf ihren Fitness-Werten sortiert. Die Ränge werden von 0 (schlechteste Fitness) bis 9 (beste Fitness) vergeben.
• Selektionswahrscheinlichkeiten: Die Selektionswahrscheinlichkeiten werden linear auf Basis der Ränge und des Selektionsdrucks berechnet. Hierbei erhält das beste Individuum eine höhere Wahrscheinlichkeit, ausgewählt zu werden.
• Selektion: Basierend auf den berechneten Wahrscheinlichkeiten werden zufällig Individuen für die nächste Generation ausgewählt.

Die obere Implementierung zeigt die Bevölkerung nach Fitness-Werten sortiert und die ausgewählten Individuen nach der linearen Ranking-Selektion. Beachte, dass die Ergebnisse aufgrund der Zufälligkeit bei der Initialisierung und Selektion variieren können.

d)

Eine Evolutionsstrategie mit \( (\tau, \rho) \) -Strategie wird auf die gleiche Fitness-Funktion angewendet. Skizziere die Funktionsweise dieser Strategie und berechne die neuen Lösungskandidaten nach einer Iteration unter der Annahme, dass die aktuelle Population aus den Punkten \( (1,1), (2,2), (3,3), (4,4), (5,5) \) besteht und die Mutationsstärke \( \rho \) 0,5 beträgt. Verwende eine \( \tau \)-Selektion, um die besten drei Individuen auszuwählen.

Lösung:

Evolutionsstrategie mit \( (\tau, \rho) \) -Strategie

Die \( (\tau, \rho) \) -Strategie (Mikro-Mu+Lambda) bei Evolutionsstrategien bezieht sich auf eine Strategie, bei der \( \tau \) Eltern eine bestimmte Anzahl von \( \rho \) Nachkommen produzieren. Anschließend werden die besten \( \tau \) Individuen aus den \( \rho \) Nachkommen und gegebenenfalls den Eltern zur nächsten Generation gewählt.

Funktionsweise:

• Initialisierung der Population: Wir starten mit einer anfänglichen Population von 5 Individuen, deren Fitness-Werte durch die Funktion \( f(x,y) = -((x-3)^2 + (y-2)^2) + 10 \) berechnet werden.
• Mutation: Jede Lösungsmöglichkeit wird durch Hinzufügen eines Zufallswertes, der aus einer Normalverteilung mit einer Standardabweichung von \( \rho \) (hier 0,5) gezogen wird, mutiert.
• Selektion: Verwende eine \(\tau \)-Selektion, um die besten drei Individuen auszuwählen (Basierend auf Fitness-Werten).

Gegebene Population:

• \( (1,1) \)
• \( (2,2) \)
• \( (3,3) \)
• \( (4,4) \)
• \( (5,5) \)

Mutationsstärke \( \rho = 0,5 \):

Wir generieren \( \rho = 0,5 \) \(a=5 \) Nachkommen für 5 Eltern.

Berechnung: Die neuen Lösungskandidaten werden nach einer Iteration durch Mutation und Selektion ermittelt.

import numpy as np# Definieren der Fitness-Funktiondef fitness_function(x, y):    return -((x - 3)**2 + (y - 2)**2) + 10# Gegebene Populationpopulation = np.array([[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]])mutation_strength = 0.5tau = 3# Mutation der Populationnew_population = population + mutation_strength * np.random.randn(*population.shape)# Berechnung der Fitness-Werte und Auswahl der besten τ Individuenfitnesses = fitness_function(new_population[:, 0], new_population[:, 1])sorted_indices = np.argsort(fitnesses)[::-1]selected_indices = sorted_indices[:tau]best_individuals = new_population[selected_indices]# Ausgabe der Resultateprint('Mutierte Population:')for i in range(len(new_population)):    print(f'Individuum {i + 1}: x={new_population[i][0]}, y={new_population[i][1]}, Fitness={fitnesses[i]}')print('Ausgewählte beste Individuen:')for i in range(len(best_individuals)):    print(f'Individuum {i + 1}: x={best_individuals[i][0]}, y={best_individuals[i][1]}, Fitness={fitness_function(best_individuals[i][0], best_individuals[i][1])}')# Initialisierung der RNGdef initialize_rng():    np. np.random.seed(53687220)# Initialisiert die Zufallsgenerator-Instanzeninitialize_rng()

Als Ergebnis der Mutation und Selektion erhalten wir die mutierte Population und die besten drei Individuen, die für die nächste Generation ausgewählt werden. Beachte, dass bei der Initialisierung und den Zufallswerten können sich die Ergebnisse bei jedem Lauf ändern.

Der oben stehende Python-Code führt eine Iteration der Evolutionsstrategie \( (\tau, \rho) \) durch, wobei die besten Individuen auf Basis der Fitness-Werte ausgewählt werden.

Aufgabe 4)

Betrachte ein nichtlineares Gleichungssystem, das in einem Optimierungsproblem zur Minimierung einer Funktion verwendet wird. Du sollst verschiedene numerische Methoden zur Lösung dieses Systems anwenden und ihre Konvergenzeigenschaften analysieren. Gegeben sei die Funktion \[ f(x,y) = (x-1)^2 + (y-2)^2 \] und die entsprechenden Ableitungsgleichungen \[ f_x = \frac{\text{d}f}{\text{d}x} = 2(x-1) \] und \[ f_y = \frac{\text{d}f}{\text{d}y} = 2(y-2) \].

b)

• Nutze das Quasi-Newton-Verfahren (BFGS) zur Lösung des gegebenen nichtlinearen Gleichungssystems und vergleiche es mit den Ergebnissen des Newton-Verfahrens. Implementiere das BFGS-Verfahren in Python und gib die gefundene Lösung aus.
• Erkläre die Konvergenzeigenschaften des BFGS-Verfahrens und in welchen Situationen es dem Newton-Verfahren überlegen sein könnte.
• Verwende das LU-Zerlegungsverfahren zur Lösung des linearen Systems in der zweiten Iteration des Newton-Verfahrens und beschreibe den Prozess und die Ergebnisse.

Lösung:

Um das Quasi-Newton-Verfahren (BFGS) zur Lösung des gegebenen nichtlinearen Gleichungssystems anzuwenden, gehen wir wie folgt vor:

Die Funktion und ihre Ableitungen sind gegeben:

• Funktion:\( f(x,y) = (x-1)^2 + (y-2)^2 \)
• Gradienten:\( f_x = \frac{\text{d}f}{\text{d}x} = 2(x-1) \)\( f_y = \frac{\text{d}f}{\text{d}y} = 2(y-2) \)

Wir beginnen mit dem Startwert (0,0).

BFGS-Verfahren Implementierung:

 import numpy as np from scipy.optimize import minimize  # Definition der Funktion def f(x):    return (x[0] - 1) ** 2 + (x[1] - 2) ** 2  # Definition der Gradientenfunktion def f_grad(x):    return np.array([2 * (x[0] - 1), 2 * (x[1] - 2)])  # Startwert initial_guess = np.array([0.0, 0.0])  # BFGS-Verfahren anwenden result = minimize(f, initial_guess, jac=f_grad, method='BFGS')  # Ausgabe der gefundenen Lösung print(f'Solution found using BFGS: {result.x}') 

Die Ausgabe sollte zeigen, dass die Lösung bei (1,2) liegt, was das Minimum der Funktion ist.

Konvergenzeigenschaften des BFGS-Verfahrens

Das BFGS-Verfahren bietet mehrere Vorteile:

• Superlineare Konvergenz: Das Verfahren konvergiert oft sehr schnell, insbesondere wenn die Anfangswerte nahe der Lösung liegen.
• Effizienz: Da das BFGS-Verfahren eine Näherung der Hesseschen Matrix verwendet und nicht direkt berechnet, ist es oft effizienter als das Newton-Verfahren.
• Robustheit: Funktioniert gut bei großen und schlecht konditionierten Problemen, während das Newton-Verfahren bei schlechten Anfangswerten stagnieren kann.

Das BFGS-Verfahren ist besonders nützlich, wenn die Hessesche Matrix schwer oder teuer zu bewerten ist, aber immer noch eine effiziente Konvergenz erreicht werden soll.

Verwendung des LU-Zerlegungsverfahrens im Newton-Verfahren

Im Newton-Verfahren aktualisieren wir die Schätzwerte durch das Lösen eines linearen Gleichungssystems. Im klassischen Newton-Verfahren wird dies oft durch die direkte Invertierung der Hesseschen Matrix gemacht, was ineffizient sein kann. Stattdessen können wir das LU-Zerlegungsverfahren verwenden:

LU-Zerlegung in der zweiten Iteration:

• Starte mit dem aktualisierten Punkt \((1, 2)\)
• Identifiziere die Hessesche Matrix: \( abla^2 f = \begin{pmatrix} 2 & 0 \ 0 & 2 \end{pmatrix} \)
• Nutze das LU-Zerlegungsverfahren:
• Für H = LU, wobei L eine untere Dreiecksmatrix und U eine obere Dreiecksmatrix ist.
• Das gegebene System wird gelöst durch Vorwärtssubstitution (L\mathbf{y} = b) und Rückwärtssubstitution (U\mathbf{z} = y).

Hier ist der Prozess in Python:

 from scipy.linalg import lu, solve  # Hessesche Matrix H = np.array([[2, 0], [0, 2]]) grad_at_new_point = np.array([0, 0])  # Gradienten bei (1,2)  # LU-Zerlegung P, L, U = lu(H)  # Vorwärts- und Rückwärtssubstitution y = solve(L, grad_at_new_point) delta_x = solve(U, y)  # Aktualisierte x-Werte x_updated = np.array([1, 2]) - delta_x print(f'Solution with LU decomposition: {x_updated}') 

Im Ergebnis bleibt der Punkt gleich, da die Gradienten im Minimum null sind.

Fazit

Das BFGS-Verfahren kann im Allgemeinen robuster und effizienter sein als das Newton-Verfahren, insbesondere bei großen oder schlecht konditionierten Problemen. Die Nutzung der LU-Zerlegung zur Lösung linearer Gleichungssysteme kann die Stabilität und Effizienz der Lösung verbessern, vor allem bei Problemen, die eine direkte Invertierung der Matrix benötigen.

c)

• Untersuche die Konditionierung des gegebenen Systems. Wie beeinflusst die Wahl der Anfangswerte die Konvergenz der verschiedenen Methoden? Nutze verschiedene Startwerte, um die Stabilität der Methoden zu analysieren.
• Implementiere eine Funktion in Python, die die Konditionierung des Systems berechnet und gibt deine Beobachtungen aus.
• Diskutiere, wie die Konditionierung des Systems die Robustheit der numerischen Lösungen in realen Anwendungen beeinflussen kann.

Lösung:

Um die Konditionierung des gegebenen Systems zu untersuchen, ist es entscheidend zu verstehen, wie stabil oder sensitiv das System gegenüber Störungen und Änderungen der Anfangswerte ist. Die Kondition eines Systems kann uns helfen, die Robustheit der numerischen Lösungen zu bewerten und potenzielle Probleme mit der Konvergenz zu identifizieren.

Die Funktion und ihre Gradienten sind wie folgt gegeben:

• Funktion:\( f(x,y) = (x-1)^2 + (y-2)^2 \)
• Gradienten:\( f_x = \frac{\text{d}f}{\text{d}x} = 2(x-1) \)\( f_y = \frac{\text{d}f}{\text{d}y} = 2(y-2) \)

Um den Einfluss der Anfangswerte auf die Konvergenz zu analysieren, testen wir verschiedene Startwerte mit dem Newton- und BFGS-Verfahren.

Funktion zur Berechnung der Konditionierung

Die Konditionszahl einer Matrix gibt Auskunft über ihre numerische Stabilität. Eine hohe Konditionszahl weist auf eine schlecht konditionierte Matrix hin, die kleine Fehler in den Daten stark verstärken kann. Die Konditionszahl der Hesseschen Matrix wird verwendet, um die Konditionierung des Systems zu bestimmen:

 import numpy as np  def condition_number(H):    return np.linalg.cond(H)  # Hessesche Matrix H = np.array([[2, 0], [0, 2]]) cond_number = condition_number(H) print(f'Konditionszahl des Systems: {cond_number}') 

Für das gegebene System beträgt die Konditionierung :

Untersuchung der Konvergenz mit verschiedenen Startwerten

Python Implementierung zur Analyse der Konvergenz:

 from scipy.optimize import minimize from scipy.linalg import lu, solve  # Definition der Funktion und ihrer Gradienten def f(x):    return (x[0] - 1) ** 2 + (x[1] - 2) ** 2  def f_grad(x):    return np.array([2 * (x[0] - 1), 2 * (x[1] - 2)])  # Newton-Verfahren Implementierung def newton_method(f_grad, initial_guess, tolerance=1e-7, max_iterations=1000):    x = initial_guess    for iteration in range(max_iterations):        grad = f_grad(x)        if np.linalg.norm(grad) < tolerance:            return x        Hess_inv = np.linalg.inv(np.array([[2, 0], [0, 2]]))        delta_x = -Hess_inv.dot(grad)        x = x + delta_x    return x  # BFGS-Verfahren anwenden def bfgs_method(f, f_grad, initial_guess):    result = minimize(f, initial_guess, jac=f_grad, method='BFGS')    return result.x  # Test mit verschiedenen Startwerten start_values = [np.array([0.0, 0.0]), np.array([10.0, 10.0]), np.array([-10.0, -10.0]), np.array([100.0, 100.0])]  print('Konvergenz-Analyse mit verschiedenen Startwerten:')  for start in start_values:    newton_sol = newton_method(f_grad, start)    bfgs_sol = bfgs_method(f, f_grad, start)    print(f'Startwerte: {start}')    print(f'Newton-Lösung: {newton_sol}')    print(f'BFGS-Lösung: {bfgs_sol}')    print('---') 

Diese Implementierung zeigt die Lösungen des Newton- und BFGS-Verfahrens, beginnend mit verschiedenen Startwerten.

Beobachtungen zur Konditionierung und Stabilität:

• Die Konditionszahl des Systems ist niedrig (1), was auf ein gut konditioniertes System hinweist. Dies bedeutet, dass kleine Änderungen oder Störungen in den Eingangsdaten das System nicht stark beeinflussen.
• Das Newton-Verfahren konvergiert sehr schnell, wenn die Startwerte nahe am Minimum (1, 2) liegen. Bei Startwerten, die weiter entfernt liegen (z. B. (100, 100)), kann die Konvergenz länger dauern, und das System könnte anfälliger für numerische Instabilitäten werden.
• Das BFGS-Verfahren zeigt eine robustere Konvergenz auch bei weiter entfernten Startwerten, was es zur bevorzugten Methode macht, wenn die Hessesche Matrix schwer oder unwirtschaftlich zu berechnen ist oder wenn die Anfangswerte weit entfernt vom Minimum liegen.

Einfluss der Kondition auf reale Anwendungen:

• Ein schlecht konditioniertes System kann dazu führen, dass numerische Methoden langsam oder gar nicht konvergieren.
• Hohe Konditionszahlen führen zu numerischer Instabilität, was zu ungenauen Ergebnissen und großer Sensitivität gegenüber kleinen Datenänderungen führt.
• Methoden wie das BFGS-Verfahren bieten eine bessere Robustheit und Stabilität bei schlecht konditionierten Systemen.

Die untersuchten numerischen Methoden und die Analyse der Konditionierung helfen, die Robustheit der Lösungen zu bewerten und liefern wertvolle Einblicke für reale Anwendungen, besonders in Fällen, in denen die Eingabedaten Störungen und Fehler aufweisen können.