Mathematical Optimization for Communications and Signal Processing - Exam

Aufgabe 1)

Du hast die Aufgabe, eine nichtlineare Optimierung eines Kommunikationssystems durchzuführen. Das Ziel ist die Minimierung der Interferenzen und die Maximierung der Signalstärke. Gegeben sind die folgende Zielfunktion und Restriktionen:

• Zielfunktion: \( f(x) = x_1^2 + 2x_2^2 + x_3^2 \)
• Restriktionen: \( g_1(x) = x_1 + x_2 - 1 \leq 0 \) und \( g_2(x) = x_2 + x_3^2 - 1 \leq 0 \)

Verwende geeignete nichtlineare Optimierungsmethoden zur Lösung der Aufgabe.

a)

Teilaufgabe A: Erstelle das Lagrange-Funktional für das gegebene Problem und leite die notwendigen Bedingungen erster Ordnung (KKT-Bedingungen) her.

• Erläutere detailliert alle Schritte und Annahmen.

Lösung:

Teilaufgabe A: Erstelle das Lagrange-Funktional für das gegebene Problem und leite die notwendigen Bedingungen erster Ordnung (KKT-Bedingungen) her.

• Erläutere detailliert alle Schritte und Annahmen.

Schritte zur Lösung:

• 1. Definition des Lagrange-Funktionals:Das Lagrange-Funktional für das gegebene Optimierungsproblem ist definiert als:
  • \( \text{L}(x_1, x_2, x_3, u_1, u_2) = f(x) + u_1 \times g_1(x) + u_2 \times g_2(x) \)
  Hierbei sind \(u_1\) und \(u_2\) die Lagrange-Multiplikatoren.
• 2. Einsetzen der Zielfunktion und Restriktionen:
  • Die Zielfunktion ist \( f(x) = x_1^2 + 2x_2^2 + x_3^2 \)
  • Die Restriktionen sind:\( g_1(x) = x_1 + x_2 - 1 \leq 0 \)\( g_2(x) = x_2 + x_3^2 - 1 \leq 0 \)
  • Das Lagrange-Funktional wird also zu: \( \text{L}(x_1, x_2, x_3, u_1, u_2) = x_1^2 + 2x_2^2 + x_3^2 + u_1 ( x_1 + x_2 - 1 ) + u_2 ( x_2 + x_3^2 - 1 ) \)
• 3. Ableitung der notwendigen Bedingungen erster Ordnung (KKT-Bedingungen):Die notwendigen Bedingungen erster Ordnung sind die partiellen Ableitungen des Lagrange-Funktionals bezüglich \(x_1, x_2, x_3\) und den Lagrange-Multiplikatoren, und deren Gleichsetzung zu null. Dies ergibt das folgende System von Gleichungen:
  • \( \frac{\text{dL}}{\text{d}x_1} = 2x_1 + u_1 = 0 \)
  • \( \frac{\text{dL}}{\text{d}x_2} = 4x_2 + u_1 + u_2 = 0 \)
  • \( \frac{\text{dL}}{\text{d}x_3} = 2x_3 + 2u_2 x_3 = 0 \)
  • \( u_1 (x_1 + x_2 - 1 ) = 0 \)
  • \( u_2 (x_2 + x_3^2 - 1 ) = 0 \)
  • Die Nichtnegativitätsbedingungen für die Lagrange-Multiplikatoren: \(u_1 \geq 0 \) und \( u_2 \geq 0 \)
• Zusammenfassung der KKT-Bedingungen:Die KKT-Bedingungen für das Optimierungsproblem lauten somit:
  • \( 2x_1 + u_1 = 0 \)
  • \( 4x_2 + u_1 + u_2 = 0 \)
  • \( 2x_3 (1 + u_2) = 0 \)
  • \( u_1 (x_1 + x_2 - 1 ) = 0 \)
  • \( u_2 (x_2 + x_3^2 - 1 ) = 0 \)
  • \( u_1 \geq 0 \)
  • \( u_2 \geq 0 \)

Die oben beschriebenen Schritte detaillieren, wie die Lagrange-Funktion und die KKT-Bedingungen für das gegebene Problem erstellt werden. Als nächstes müssten diese Bedingungen systematisch gelöst werden, um die optimalen Werte für die Variablen \( x_1, x_2, x_3 \) sowie die Lagrange-Multiplikatoren \( u_1 \) und \( u_2 \) zu finden.

b)

Teilaufgabe B: Führe das Gradient-Descent-Verfahren für das gegebene Problem durch. Gehe dabei von einem initialen Punkt \( x^{(0)} = (0, 0, 0)\) aus und berechne die ersten drei Iterationen. Verwende eine Lernrate \( \beta = 0.1 \).

• Zeige alle Rechenschritte und erläutere, wie sich der Punkt in jedem Schritt verändert.

Lösung:

Teilaufgabe B: Führe das Gradient-Descent-Verfahren für das gegebene Problem durch. Gehe dabei von einem initialen Punkt \( x^{(0)} = (0, 0, 0)\) aus und berechne die ersten drei Iterationen. Verwende eine Lernrate \( \beta = 0.1 \).

• Zeige alle Rechenschritte und erläutere, wie sich der Punkt in jedem Schritt verändert.

Schritte zur Lösung:

• 1. Gradient der Zielfunktion berechnen:Die Zielfunktion lautet \( f(x) = x_1^2 + 2x_2^2 + x_3^2 \). Der Gradient der Zielfunktion ist:
  • \( abla f(x) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \frac{\partial f}{\partial x_3} \right) \)
  • \( abla f(x) = \left( 2x_1, 4x_2, 2x_3 \right) \)
• 2. Initialisierung:Initialer Punkt ist \( x^{(0)} = (0, 0, 0) \) und die Lernrate ist \( \beta = 0.1 \).
• 3. Erste Iteration:
  • Gradient an \( x^{(0)} \):\( abla f(x^{(0)}) = \left( 2 \times 0, 4 \times 0, 2 \times 0 \right) = (0, 0, 0) \)
  • Update der Variablen:\( x^{(1)} = x^{(0)} - \beta abla f(x^{(0)}) \)\( x^{(1)} = (0, 0, 0) - 0.1 \times (0, 0, 0) = (0, 0, 0) \)
• 4. Zweite Iteration:
  • Gradient an \( x^{(1)} \):\( abla f(x^{(1)}) = \left( 2 \times 0, 4 \times 0, 2 \times 0 \right) = (0, 0, 0) \)
  • Update der Variablen:\( x^{(2)} = x^{(1)} - \beta abla f(x^{(1)}) \)\( x^{(2)} = (0, 0, 0) - 0.1 \times (0, 0, 0) = (0, 0, 0) \)
• 5. Dritte Iteration:
  • Gradient an \( x^{(2)} \):\( abla f(x^{(2)}) = \left( 2 \times 0, 4 \times 0, 2 \times 0 \right) = (0, 0, 0) \)
  • Update der Variablen:\( x^{(3)} = x^{(2)} - \beta abla f(x^{(2)}) \)\( x^{(3)} = (0, 0, 0) - 0.1 \times (0, 0, 0) = (0, 0, 0) \)

Die ersten drei Iterationen zeigen, dass der Punkt \( x \) sich nicht verändert, da der initiale Punkt \( x^{(0)} = (0, 0, 0) \) bereits ein stationärer Punkt für die Zielfunktion ist.

Obwohl dieser Punkt die Zielfunktion minimiert, erfüllt er möglicherweise nicht die Restriktionen des Problems. Lass uns überprüfen:

• \( g_1(x) = x_1 + x_2 - 1 = 0 + 0 - 1 = -1 \leq 0 \) (ok)
• \( g_2(x) = x_2 + x_3^2 - 1 = 0 + 0^2 - 1 = -1 \leq 0 \) (ok)

Diese Ergebnisse zeigen, dass der Punkt \( x = (0, 0, 0) \) nicht nur ein stationärer Punkt ohne Änderungen im Gradient-Descent-Verfahren ist, sondern auch die Restriktionen erfüllt. Daher ist der Punkt \( x = (0, 0, 0) \) eine gültige Lösung des Problems.

c)

Teilaufgabe C: Diskutiere die Konvergenzgeschwindigkeit und Robustheit des Newton-Verfahrens im Vergleich zum Gradient-Descent-Verfahren für dieses Optimierungsproblem.

• Welche Methode ist in diesem Fall geeigneter? Begründe Deine Antwort.

Lösung:

Teilaufgabe C: Diskutiere die Konvergenzgeschwindigkeit und Robustheit des Newton-Verfahrens im Vergleich zum Gradient-Descent-Verfahren für dieses Optimierungsproblem.

• Welche Methode ist in diesem Fall geeigneter? Begründe Deine Antwort.

Schritte zur Lösung:

Um die Performance und Eignung des Newton-Verfahrens im Vergleich zum Gradient-Descent-Verfahren zu diskutieren, betrachten wir zunächst die Eigenschaften beider Methoden:

• Gradient-Descent-Verfahren:
  • Verwendet den Gradienten der Zielfunktion zur Bestimmung des Abstiegspunkts.
  • Konvergenzgeschwindigkeit: Langsamer als Newton-Verfahren, insbesondere wenn man sich dem Optimum nähert.
  • Lernrate: Es muss eine geeignete Lernrate gewählt werden, was oft durch Trial-and-Error erfolgt.
  • Komplexität: Niedrigere Komplexität pro Iteration, da nur der Gradient berechnet werden muss.
  • Robustheit: Robust gegenüber unglatten Zielfunktionen, aber könnte bei stark gekrümmten Funktionen langsam werden.
• Newton-Verfahren:
  • Verwendet sowohl den Gradienten als auch die Hesse-Matrix (zweite Ableitungen) der Zielfunktion.
  • Konvergenzgeschwindigkeit: Schnellere Konvergenz, vor allem in der Nähe des Optimums (quadratische Konvergenz).
  • Lernrate: Lernt automatisch, benötigt keine Wahl einer externen Lernrate.
  • Komplexität: Höhere Komplexität pro Iteration, da sowohl der Gradient als auch die Hesse-Matrix berechnet werden müssen.
  • Robustheit: Kann problematisch sein, wenn die Hesse-Matrix nicht positiv definit ist oder die Berechnung der Hesse-Matrix numerisch instabil ist.

Betrachtung der Eignung:

Für das gegebene Optimierungsproblem mit der Zielfunktion \( f(x) = x_1^2 + 2x_2^2 + x_3^2 \) und den Restriktionen \( g_1(x) = x_1 + x_2 - 1 \leq 0 \) und \( g_2(x) = x_2 + x_3^2 - 1 \leq 0 \) können wir Folgendes feststellen:

• Die Zielfunktion ist ein quadratisches Polynom, was bedeutet, dass die Hesse-Matrix konstant und positiv definit ist. Dies ist eine günstige Bedingung für das Newton-Verfahren, da keine Instabilität der Hesse-Matrix zu erwarten ist.
• Das Newton-Verfahren wird wahrscheinlich schneller konvergieren, da es die quadratische Struktur der Funktion ausnutzen kann.
• Das Gradient-Descent-Verfahren könnte jedoch einfacher zu implementieren sein und benötigt weniger Berechnungsaufwand pro Iteration.

Fazit:

In diesem Fall scheint das Newton-Verfahren geeigneter zu sein aufgrund der schnelleren Konvergenz und der besonderen Struktur der Zielfunktion. Da die Hesse-Matrix positiv definit ist, wird die Robustheit des Newton-Verfahrens nicht beeinträchtigt sein.

Das Gradient-Descent-Verfahren kann als einfachere Alternative genutzt werden, wenn Rechenressourcen begrenzt sind oder eine Implementierung schnell bereitgestellt werden muss. Es könnte besonders nützlich sein, um erste Schätzungen oder einen Startpunkt für das Newton-Verfahren zu liefern.

In realen Anwendungsszenarien könnte eine Mischung aus beiden Methoden verwendet werden, wobei man mit dem Gradient-Descent-Verfahren startet und dann zu Newton-Verfahren wechselt, sobald man sich in der Nähe des Optimums befindet, um eine schnellere und genauere Konvergenz zu erreichen.

d)

Teilaufgabe D: Beurteile die Anwendbarkeit evolutionärer Algorithmen für das gegebene Optimierungsproblem. Erkläre kurz, wie diese Algorithmen arbeiten und unter welchen Bedingungen sie besser geeignet sein könnten.

• Veranschauliche Deine Antwort mit einem kurzen Beispiel.

Lösung:

Teilaufgabe D: Beurteile die Anwendbarkeit evolutionärer Algorithmen für das gegebene Optimierungsproblem. Erkläre kurz, wie diese Algorithmen arbeiten und unter welchen Bedingungen sie besser geeignet sein könnten.

• Veranschauliche Deine Antwort mit einem kurzen Beispiel.

Einführung in evolutionäre Algorithmen:

Evolutionäre Algorithmen (EA) sind eine Klasse von stochastischen Optimierungsverfahren, die von biologischen Evolutionsprozessen inspiriert sind. Zu den bekanntesten gehören genetische Algorithmen, evolutionäre Strategien und genetische Programmierung. Diese Algorithmen nutzen Mechanismen wie Selektion, Kreuzung (Crossover) und Mutation, um eine Population von Lösungen iterativ zu verbessern.

• Grundlegende Arbeitsweise:
  • Initialisierung: Eine initiale Population von zufälligen Lösungen wird generiert.
  • Bewertung: Jede Lösung in der Population wird anhand der Zielfunktion bewertet.
  • Selektion: Lösungen mit besseren Bewertungen haben eine höhere Wahrscheinlichkeit, für die nächste Generation ausgewählt zu werden.
  • Kreuzung (Crossover): Zwei ausgewählte Lösungen werden kombiniert, um Nachkommen zu erzeugen.
  • Mutation: Kleine zufällige Änderungen werden bei einigen Lösungen vorgenommen, um die Diversität zu erhöhen.
  • Iteration: Die Schritte 2 bis 5 werden wiederholt, bis ein Abbruchkriterium erfüllt ist (z. B. eine maximale Anzahl von Generationen oder eine zufriedenstellende Lösung).

Anwendbarkeit für das gegebene Optimierungsproblem:

Die Anwendung eines evolutionären Algorithmus für die Minimierung der Interferenzen und Maximierung der Signalstärke in einem Kommunikationssystem kann unter bestimmten Bedingungen vorteilhaft sein:

• Komplexe oder nicht glatte Zielfunktion: Evolutionsalgorithmen sind robust gegenüber nicht glatten oder nicht konvexen Zielfunktionen, können also bei Problemen mit mehreren lokalen Minima nützlich sein.
• Restriktionen: Evolutionsalgorithmen können effizient mit Restriktionen umgehen, indem sie Lösungen bestrafen, die die Restriktionen verletzen, oder indem sie Möglichkeiten zur Reparatur solcher Lösungen implementieren.
• Exploratives Suchen: EA eignen sich gut für globale Optimierungsprobleme und können eine weite Lösungslandschaft explorieren, was besonders nützlich ist, wenn der globale Optimum unbekannt oder schwer zugänglich ist.

Beispiel zur Veranschaulichung:

Betrachten wir das gegebene Optimierungsproblem:

• Zielfunktion: \( f(x) = x_1^2 + 2x_2^2 + x_3^2 \)
• Restriktionen: \( g_1(x) = x_1 + x_2 - 1 \leq 0 \)\( g_2(x) = x_2 + x_3^2 - 1 \leq 0 \)

Ein evolutionärer Algorithmus würde wie folgt arbeiten:

1. Initialisierung: Generiere eine Anfangspopulation von Lösungen \( x = (x_1, x_2, x_3) \) innerhalb eines geeigneten Bereichs.
2. Bewertung: Berechne für jede Lösung die Zielfunktion \( f(x) \) und prüfe, ob die Restriktionen erfüllt sind. Falls nicht, weise eine hohe Strafbewertung zu.
3. Selektion: Wähle Lösungen basierend auf ihren Bewertungen aus, um Nachkommen zu erzeugen.
4. Kreuzung und Mutation: Erzeuge neue Lösungen durch Kreuzung von Elternlösungen und wende Mutationen an, um die Diversität zu erhöhen.
5. Iteration: Wiederhole die Schritte 2 bis 4 bis zur Erfüllung des Abbruchkriteriums.

Vorteile und Grenzen:

• Evolutionäre Algorithmen sind besonders nützlich bei nicht konvexen, multimodalen Optimierungsproblemen.
• Sie benötigen keine Informationen über die Ableitungen der Zielfunktion.
• Die Konvergenz könnte langsamer sein als bei gradientenbasierten Methoden, insbesondere bei Problemen mit glatten, gut konditionierten Zielfunktionen.

Fazit: Für das gegebene Problem könnten evolutionäre Algorithmen eine sinnvolle Alternative sein, besonders wenn die Zielfunktion nicht glatt wäre oder die Restriktionen schwieriger zu handhaben wären. Allerdings könnte die relative Einfachheit der Zielfunktion und die lineare Natur der Restriktionen dafür sprechen, dass analytische Methoden oder das Newton-Verfahren in diesem speziellen Fall effizienter sind.

Aufgabe 2)

In einem Kommunikationsnetzwerk sollen Ressourcen effizient zugewiesen werden. Jedes Kommunikationsgerät hat einen bestimmten Bedarf an Bandbreite, der den Gesamtbedarf des Netzwerks darstellt. Das Ziel ist es, die Gesamtkosten der Bandbreitenzuteilung zu minimieren, unter Aufrechterhaltung der benötigten Qualität der Dienstleistung. Hierfür wird ein quadratisches Optimierungsproblem formuliert und gelöst.

a)

Formuliere das quadratische Optimierungsproblem zur Minimierung der Gesamtkosten der Bandbreitenzuteilung für ein Kommunikationsnetzwerk. Gegeben seien die Bandbreitenanforderungen der Geräte als Vektor \(\boldsymbol{b} = [b_1, b_2, \dots, b_n]\) und die Kostengewichte als Vektor \(\boldsymbol{w} = [w_1, w_2, \dots, w_n]\).

Lösung:

Um das quadratische Optimierungsproblem zur Minimierung der Gesamtkosten der Bandbreitenzuteilung zu formulieren, sind folgende Schritte erforderlich:

• Gegeben:
  • Bandbreitenanforderungen der Geräte: \(\boldsymbol{b} = [b_1, b_2, \dots, b_n]\)
  • Kostengewichte: \(\boldsymbol{w} = [w_1, w_2, \dots, w_n]\)
• Ziel: Minimierung der Gesamtkosten der Bandbreitenzuteilung.

Die Kostenfunktion kann als eine quadratische Funktion der zugeteilten Bandbreiten \(\boldsymbol{x} = [x_1, x_2, \dots, x_n]\) beschrieben werden:

• Gesamtkosten: \(K(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^T \boldsymbol{x}\)

Hier ist:

• \(\boldsymbol{x}\) der Vektor der zugeteilten Bandbreiten, d.h., \(x_i\) ist die zugewiesene Bandbreite für Gerät \(i\).
• \(\boldsymbol{Q}\) eine Gewichtungsmatrix, die die quadratischen Kosten beschreibt. In diesem speziellen Fall setzen wir \(\boldsymbol{Q}\) als Diagonalmatrix mit \(\boldsymbol{Q} = \text{diag}(w_1, w_2, \dots, w_n)\).
• \(\boldsymbol{c}\) ein Vektor, der die linearen Kosten beschreibt. Hier kann \(\boldsymbol{c}\) null sein, da die linearen Komponenten in der Gewichtungsmatrix berücksichtigt sind.

Restriktionen: Die zugeteilten Bandbreiten müssen mindestens die Anforderungen der Geräte erfüllen, und es sollte keine negative Zuteilung geben:

• \(x_i \geq b_i \, \text{für} \, i = 1, 2, \dots, n\)
• \(x_i \geq 0 \, \text{für} \, i = 1, 2, \dots, n\)

Zusammengefasst ergibt sich das folgende quadratische Optimierungsproblem:

• Minimiere:

\(\frac{1}{2} \boldsymbol{x}^T \text{diag}(w_1, w_2, \dots, w_n) \boldsymbol{x}\)

• Unter den Einschränkungen:

\(x_i \geq b_i \, \text{für} \, i = 1, 2, \dots, n\) \(x_i \geq 0 \, \text{für} \, i = 1, 2, \dots, n\)

b)

Zeige, dass das formulierte Optimierungsproblem eine konvexe Funktion minimiert, indem Du die Definition der Konvexität heranziehst. Weist die zu minimierende Kostenfunktion die Eigenschaften einer konvexen Funktion auf? Begründe Deine Antwort.

Lösung:

Um zu zeigen, dass das formulierte Optimierungsproblem eine konvexe Funktion minimiert, müssen wir die Definition der Konvexität heranziehen und prüfen, ob die Kostenfunktion die Eigenschaften einer konvexen Funktion aufweist.

Definition der Konvexität: Eine Funktion \(f\) ist konvex, wenn für alle \(\boldsymbol{x}, \boldsymbol{y} \, \in \, \mathbb{R}^n\) und alle \(\theta \, \in \, [0, 1]\) gilt:

• \(f(\theta \boldsymbol{x} + (1 - \theta) \boldsymbol{y}) \leq \theta f(\boldsymbol{x}) + (1 - \theta) f(\boldsymbol{y})\)

Betrachten wir die Kostenfunktion:

• \(K(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^T \boldsymbol{x}\)

Diese Funktion besteht aus zwei Teilen: einem quadratischen Term \(\frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x}\) und einem linearen Term \(\boldsymbol{c}^T \boldsymbol{x}\).

Quadratischer Term: Ein quadratischer Term \(\frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x}\) ist konvex, wenn die Matrix \(\boldsymbol{Q}\) positiv semidefinit ist. Das bedeutet, dass für alle \(\boldsymbol{z} \, \in \, \mathbb{R}^n\) gilt:

• \(\boldsymbol{z}^T \boldsymbol{Q} \boldsymbol{z} \geq 0\)

Da \(\boldsymbol{Q}\) in diesem Fall eine Diagonalmatrix \(\text{diag}(w_1, w_2, \dots, w_n)\) mit positiven Einträgen \(w_i \geq 0\) ist, ist \(\boldsymbol{Q}\) offensichtlich positiv semidefinit, denn:

• \(\boldsymbol{z}^T \boldsymbol{Q} \boldsymbol{z} = \sum_{i=1}^n w_i z_i^2 \geq 0\)

Linearer Term: Ein linearer Term \(\boldsymbol{c}^T \boldsymbol{x}\) ist ebenfalls eine konvexe Funktion, da lineare Funktionen per Definition affine Funktionen sind und jede affine Funktion ist konvex.

Da sowohl der quadratische als auch der lineare Term konvex sind, ist die gesamte Kostenfunktion \(K(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^T \boldsymbol{x}\) eine konvexe Funktion.

Daher minimiert das formulierte Optimierungsproblem eine konvexe Funktion, indem die Gesamtkosten der Bandbreitenzuteilung minimiert werden.

c)

Löse das formulierte Optimierungsproblem mithilfe der Methode der Lagrange-Multiplikatoren. Stelle die Lagrange-Funktion auf und leite die Gleichungen für das Optimum her.

Lösung:

Um das formulierte quadratische Optimierungsproblem mithilfe der Methode der Lagrange-Multiplikatoren zu lösen, gehen wir wie folgt vor:

• Gegeben:
• Die Kostenfunktion: \(K(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^T \boldsymbol{x}\)
• Beschränkungen: \(x_i \geq b_i\) und \(x_i \geq 0\) für alle \(i = 1, 2, \dots, n\)
• Ziel: Die Lagrange-Funktion aufstellen und die Gleichungen für das Optimum herleiten.

Schritt 1: Aufstellen der Lagrange-Funktion

Wir definieren die Lagrange-Funktion \(L\) mit den Lagrange-Multiplikatoren \(\lambda_i\) für die Ungleichheitsbeschränkungen \(x_i \geq b_i\) und \(\mu_i\) für die Nichtnegativitätsbeschränkungen \(x_i \geq 0\):

• \(L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = \frac{1}{2} \boldsymbol{x}^T \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c}^T \boldsymbol{x} + \sum_{i=1}^n \lambda_i (b_i - x_i) + \sum_{i=1}^n \mu_i (0 - x_i)\)

Schritt 2: Bedingungen für das Optimum herleiten

Um das Optimum der Lagrange-Funktion zu finden, müssen die folgenden Bedingungen erfüllt werden:

1. Gradient der Lagrange-Funktion bezüglich \(\boldsymbol{x}\): Die Ableitung von \(L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})\) nach \(\boldsymbol{x}\) muss null sein.

• \(\frac{\partial L}{\partial \boldsymbol{x}} = \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c} - \boldsymbol{\lambda} - \boldsymbol{\mu} = 0\)

1. Dualitätslücken: Die Lagrange-Multiplikatoren müssen die Komplementaritätsbedingungen erfüllen.

• \(\lambda_i (x_i - b_i) = 0\)
• \(\mu_i x_i = 0\)

1. Nichtnegativitätsbedingungen: Die Lagrange-Multiplikatoren und Primärvariablen müssen nicht negativ sein.

• \(\lambda_i \geq 0\)
• \(\mu_i \geq 0\)
• \(x_i \geq 0\)

Schritt 3: Gleichungen lösen

Die Gleichungen für das Optimum sind:

• \(\boldsymbol{Q} \boldsymbol{x} + \boldsymbol{c} = \boldsymbol{\lambda} + \boldsymbol{\mu}\)
• \(\lambda_i (x_i - b_i) = 0\) für alle \(i = 1, 2, \dots, n\)
• \(\mu_i x_i = 0\) für alle \(i = 1, 2, \dots, n\)
• \(\lambda_i \geq 0\) für alle \(i = 1, 2, \dots, n\)
• \(\mu_i \geq 0\) für alle \(i = 1, 2, \dots, n\)
• \(x_i \geq b_i\) und \(x_i \geq 0\) für alle \(i = 1, 2, \dots, n\)

Durch das Lösen dieser Gleichungssysteme finden wir die optimalen Werte für \(\boldsymbol{x}\), \(\boldsymbol{\lambda}\) und \(\boldsymbol{\mu}\). Dies kann in der Regel durch numerische Methoden oder spezialisierte Solver für quadratische Optimierungsprobleme geschehen.

d)

Erläutere, wie die Lösung dieses Optimierungsproblems praktisch in einem realen Netzwerk angewendet werden könnte. Diskutiere dabei mögliche Einschränkungen und Vorteile der Nutzung quadratischer Optimierung bei der Ressourcenverteilung in Kommunikationsnetzwerken.

Lösung:

Die Anwendung der Lösung dieses quadratischen Optimierungsproblems in einem realen Kommunikationsnetzwerk kann einen wesentlichen Beitrag zur effizienten Ressourcenverteilung leisten. Hier sind einige Möglichkeiten, wie die Lösung praktisch umgesetzt werden kann, sowie mögliche Einschränkungen und Vorteile:

Praktische Anwendung

• Zentrale Verwaltung: Ein zentrales Netzwerkmanagement-System sammelt regelmäßig Daten über den Bandbreitenbedarf der einzelnen Geräte und berechnet mithilfe des Optimierungsmodells die optimale Zuteilung der verfügbaren Bandbreite.
• Adaptive Ressourcenallokation: Das System kann dynamisch auf Veränderungen im Netzwerk reagieren, um die Ressourcenallokation kontinuierlich anzupassen und so die Gesamtkosten zu minimieren und die Dienstqualität aufrechtzuerhalten. Dies kann durch regelmäßige Rekonfigurationen erreicht werden.
• Software-Defined Networking (SDN): Mit SDN lassen sich Netzwerke zentral verwalten und flexibel programmieren. SDN-Controller könnten direkt die optimierten Zuteilungsentscheidungen implementieren und entsprechende Regeln in den Netzwerkswitches konfigurieren.

Mögliche Einschränkungen

• Rechenaufwand: Quadratische Optimierungsprobleme können bei großen Netzwerken mit vielen Geräten und dynamischen Anforderungen rechenintensiv sein. Diese Probleme in Echtzeit zu lösen, könnte eine Herausforderung darstellen.
• Implementierungskomplexität: Die Implementierung des Optimierungsmodells und die Integration in bestehende Netzwerkinfrastrukturen kann komplex und kostenintensiv sein.
• Datenqualität: Die Effektivität der Optimierung hängt stark von der Genauigkeit der Bandbreitenbedarfsschätzungen und anderen Eingangsdaten ab. Ungenaue Daten können zu suboptimalen Allokationsentscheidungen führen.

Vorteile quadratischer Optimierung

• Effizienz: Die Nutzung quadratischer Optimierungsmodelle ermöglicht eine mathematisch fundierte und oft sehr effiziente Lösung zur Minimierung der Gesamtkosten bei der Ressourcenverteilung.
• Flexibilität: Quadratische Optimierung kann an unterschiedliche Szenarien und Anforderungen angepasst werden, z.B. durch Eingabe neuer Gewichtungsfaktoren oder Nebenbedingungen.
• Skalierbarkeit: Auch große und komplexe Netzwerke können durch geeignete Optimierungsverfahren effektiv verwaltet werden, sofern die Rechenleistung ausreichend ist.
• Garantierte Optimalität: Quadratische Optimierungsprobleme haben oft wohldefinierte Lösungen, die mathematisch als optimal nachgewiesen werden können. Dies gibt Netzbetreibern Sicherheit, dass die ausgegebenen Lösungen wirklich die bestmöglichen sind.

Zusammengefasst kann die Lösung des formulierten Optimierungsproblems in realen Netzwerken erheblich zur effizienten Ressourcenverteilung und damit zur Kostensenkung und Verbesserung der Dienstqualität beitragen, sofern die Implementierung und die regelmäßige Aktualisierung entsprechend gut umgesetzt werden können.

Aufgabe 3)

In diesem Problem wirst Du numerische Methoden zur Lösung von Optimierungsproblemen im Kontext von Kommunikations- und Signalverarbeitung anwenden. Angenommen, wir haben eine Funktion, die die Verlustleistung eines Kommunikationssystems beschreibt: f(x) = 5x^4 - 4x^3 + 2x^2 - 3x + 7 Du sollst diese Funktion minimieren, um die optimale Betriebsweise des Systems zu ermitteln.

a)

Leite die Funktion f(x) her und bestimme den Gradienten. Schreibe die Herleitung der ersten Ableitung f(x)' klar und deutlich aus.

Lösung:

Um die optimale Betriebsweise des Systems zu ermitteln, musst Du die gegebene Funktion minimieren. Dafür leiten wir die Funktion f(x) ab und bestimmen den Gradienten.

Die gegebene Funktion lautet:

• f(x) = 5x⁴ - 4x³ + 2x² - 3x + 7

Um die erste Ableitung zu ermitteln, werden wir jeden Term der Funktion separat differenzieren:

• Die Ableitung von 5x⁴ ist 20x³.
• Die Ableitung von -4x³ ist -12x².
• Die Ableitung von 2x² ist 4x.
• Die Ableitung von -3x ist -3.
• Die Ableitung der Konstanten 7 ist 0.

Damit ergibt sich die erste Ableitung der Funktion f(x):

• f'(x) = 20x³ - 12x² + 4x - 3

Somit ist der Gradient der Funktion f(x):

• Gradient von f(x) = f'(x) = 20x³ - 12x² + 4x - 3

Zusammengefasst lautet die erste Ableitung der Funktion f(x):

• f'(x) = 20x³ - 12x² + 4x - 3

b)

Verwende das Gradientenabstiegsverfahren, um einen Iterationsschritt durchzuführen. Gegeben sei ein Ausgangspunkt x_0 = 1 , und eine Lernrate (Schrittweite) von 0.01. Berechne den neuen Punkt x_1.

Lösung:

Um die Funktion zu minimieren, verwenden wir das Gradientenabstiegsverfahren. Bei diesem Verfahren iterieren wir schrittweise, um zum Minimum der Funktion zu gelangen. Gegeben sind ein Ausgangspunkt x_0 = 1 und eine Lernrate (Schrittweite) von 0.01. Wir müssen den neuen Punkt x_1 berechnen.

Der Gradientenabstiegsalgorithmus ist definiert als:

\[x_{n+1} = x_n - \text{Lernrate} \times f'(x_n)\]

Zuerst berechnen wir die Ableitung der Funktion f(x) an der Stelle x_0 = 1. Die erste Ableitung f'(x) wurde bereits bestimmt als:

• f'(x) = 20x^3 - 12x^2 + 4x - 3

Wir setzen x_0 = 1 in die Ableitung ein:

\[f'(1) = 20(1)^3 - 12(1)^2 + 4(1) - 3\]

Rechnen wir das aus:

\[f'(1) = 20 - 12 + 4 - 3 = 9\]

Nun können wir den neuen Punkt x_1 mit der gegebenen Lernrate von 0.01 berechnen:

\[x_1 = x_0 - \text{Lernrate} \times f'(x_0) = 1 - 0.01 \times 9 = 1 - 0.09 = 0.91\]

Der neue Punkt ist somit:

• x_1 = 0.91

d)

Erkläre kurz, warum der Gradientenabstieg für nicht-konvexe Funktionen wie die gegebene problematisch sein kann und welche Alternativen existieren könnten, um globale Minima zu finden.

Lösung:

Der Gradientenabstiegsalgorithmus ist eine leistungsstarke numerische Methode zur Minimierung von Funktionen, hat jedoch einige Einschränkungen, insbesondere bei nicht-konvexen Funktionen wie der gegebenen Funktion f(x) = 5x^4 - 4x^3 + 2x^2 - 3x + 7. Hier sind einige Gründe, warum der Gradientenabstieg für solche Funktionen problematisch sein kann:

• Lokale Minima: Nicht-konvexe Funktionen können mehrere lokale Minima haben. Der Gradientenabstieg kann in einem dieser lokalen Minima stecken bleiben, anstatt das globale Minimum zu finden.
• Sattelpunkte: Nicht-konvexe Funktionen können Sattelpunkte haben, an denen der Gradient 0 ist, aber die Stelle kein Minimum ist. Der Algorithmus kann an solchen Punkten stagnieren.
• Bildung von Plateaus: Große flache Bereiche oder Plateaus in der Funktion können den Gradientenabstieg stark verlangsamen, da die Gradienteninformationen in diesen Bereichen sehr gering sind.

Es gibt verschiedene Alternativen und Modifikationen zum Gradientenabstieg, die helfen können, diese Probleme zu überwinden und das globale Minimum zu finden:

• Stochastischer Gradientenabstieg (SGD): Anstatt den vollen Gradienten zu verwenden, verwendet dieser Ansatz zufällige Teildaten, um die Gradientenabschätzung zu berechnen. Dies kann helfen, aus lokalen Minima herauszukommen.
• Simulierte Abkühlung (Simulated Annealing): Diese Methode verwendet eine Metapher des Abkühlungsprozesses von Metallen, um die Wahrscheinlichkeit zu erhöhen, dass das globale Minimum gefunden wird.
• Genetische Algorithmen: Diese optimieren die Funktion durch natürliche Selektion und genetische Vererbung und können ebenfalls helfen, globale Minima zu finden.
• Partikel-Schwarm-Optimierung: Eine weitere evolutionäre Methode, die die Bewegung einer Gruppe von Partikeln verwendet, um das globale Optimum zu suchen.
• Mehrfache Anfangsbedingungen: Der Gradientenabstieg wird von mehreren zufälligen Startpunkten aus gestartet, um die Wahrscheinlichkeit zu erhöhen, das globale Minimum zu finden.

Zusammengefasst ist der Gradientenabstieg zwar ein leistungsstarkes Werkzeug, erfordert jedoch bei der Arbeit mit nicht-konvexen Funktionen oft zusätzliche Techniken oder Modifikationen, um sicherzustellen, dass das globale Minimum gefunden wird.

Aufgabe 4)

Ein Kommunikationssystem benötigt einen digitalen Bandpassfilter, um hochfrequentes Rauschen aus dem empfangenen Signal zu entfernen. Der gewünschte Filter hat folgende Vorgaben: Die untere Grenzfrequenz ist bei 500 Hz, und die obere Grenzfrequenz bei 1500 Hz. Der Filter beträgt eine Abtastrate von 8000 Hz.

a)

Entwerfe einen FIR-Bandpassfilter für das gegebene Kommunikationssystem unter Verwendung des Fensterverfahrens. Verwende ein Hamming-Fenster für das Design. Gib den Filterkoeffizienten an.

Lösung:

Design eines FIR-Bandpassfilters mittels Hamming-FensterUm einen FIR-Bandpassfilter für das gegebene Kommunikationssystem zu entwerfen, folge diesen Schritten:

• Bestimme die normalisierten Grenzfrequenzen.
• Berechne die idealen Filterkoeffizienten für ein Bandpassfilter.
• Wende das Hamming-Fenster an, um die endgültigen Filterkoeffizienten zu erhalten.

1. Normalisierte GrenzfrequenzenDie unteren (\(f_L\)) und oberen (\(f_H\)) Grenzfrequenzen sind als 500 Hz und 1500 Hz gegeben. Die Abtastrate (\(f_s\)) beträgt 8000 Hz.Die normalisierten Grenzfrequenzen für das Design sind:

• \(f_{Ln} = \frac{500}{4000} = 0.125\)
• \(f_{Hn} = \frac{1500}{4000} = 0.375\)

2. Berechne die idealen FilterkoeffizientenFür einen FIR-Bandpassfilter können die idealen Koeffizienten unter Verwendung der folgenden Formel berechnet werden:

• \(h[n] = \frac{\sin(2 \pi f_H n)}{\pi n} - \frac{\sin(2 \pi f_L n)}{\pi n}\) für \(|n| eq 0\)
• \(h[0] = 2(f_H - f_L)\) für \(n = 0\)

3. Wende das Hamming-Fenster anEin Hamming-Fenster ist gegeben durch:\(w[n] = 0.54 - 0.46 \cos\left(\frac{2 \pi n}{N-1}\right)\),wobei \(N\) die Länge des Fensters ist.Die endgültigen Filterkoeffizienten erhält man durch Multiplizieren der idealen Koeffizienten mit dem Hamming-Fenster:\(h_{\text{final}}[n] = h[n] \times w[n]\)Implementierung in Python

• Du kannst die FIR-Koeffizienten für diesen Bandpassfilter mit Python und der Bibliothek Scipy berechnen:

import numpy as npfrom scipy.signal import firwinimport matplotlib.pyplot as pltfs = 8000  # AbtastfrequenzfL = 500  # untere GrenzfrequenzfH = 1500  # obere Grenzfrequenznumtaps = 101  # Filterordnungwn = [fL / (fs / 2), fH / (fs / 2)]  # normalisierte Frequenzenh = firwin(numtaps, wn, pass_zero='bandpass', window='hamming')print('Filter Koeffizienten:', h)plt.plot(h)plt.title('Filter Koeffizienten')plt.show()

Der Code verwendet das Hamming-Fenster und berechnet die entsprechenden Filterkoeffizienten.

b)

Bestimme und zeichne den Frequenzgang des entworfenen FIR-Bandpassfilters. Kommentiere die Ergebnisse und ob der Filter die Anforderungen erfüllt.

Lösung:

Frequenzgang eines FIR-Bandpassfilters bestimmen und zeichnenUm den Frequenzgang des entworfenen FIR-Bandpassfilters zu bestimmen und zu zeichnen, folge diesen Schritten:

• Verwende die Filterkoeffizienten, die mit dem Hamming-Fenster berechnet wurden.
• Verwende die Funktion `freqz` der Bibliothek SciPy, um den Frequenzgang zu berechnen.
• Visualisiere den Frequenzgang mithilfe von Matplotlib.

Schritte zur Berechnung und Visualisierung:

• Berechne den Frequenzgang des Filters.
• Zeichne den Amplitudengang und den Phasengang.
• Kommentiere die Ergebnisse und prüfe, ob der Filter die Anforderungen erfüllt.

Implementierung in Python:

• Das folgende Python-Skript zeigt, wie der Frequenzgang des Filters berechnet und visualisiert werden kann:

import numpy as npfrom scipy.signal import firwin, freqzimport matplotlib.pyplot as pltfs = 8000  # AbtastfrequenzfL = 500  # untere GrenzfrequenzfH = 1500  # obere Grenzfrequenznumtaps = 101  # Filterordnungwn = [fL / (fs / 2), fH / (fs / 2)]  # normalisierte Frequenzenh = firwin(numtaps, wn, pass_zero='bandpass', window='hamming')print('Filter Koeffizienten:', h)# Frequenzgang des Filters berechnenw, h_freqz = freqz(h, worN=8000)frequencies = w * fs / (2 * np.pi)  # Frequenzen in Hz umrechnen# Amplitudengang zeichnenplt.figure(figsize=(12, 6))plt.subplot(2, 1, 1)plt.plot(frequencies, 20 * np.log10(abs(h_freqz)))plt.title('Frequenzgang des FIR-Bandpassfilters (Amplitudengang)')plt.xlabel('Frequenz (Hz)')plt.ylabel('Amplitude (dB)')plt.grid(True)# Phasengang zeichnenplt.subplot(2, 1, 2)plt.plot(frequencies, np.angle(h_freqz))plt.title('Frequenzgang des FIR-Bandpassfilters (Phasengang)')plt.xlabel('Frequenz (Hz)')plt.ylabel('Phase (radian)')plt.grid(True)plt.tight_layout()plt.show()

Der Code berechnet und visualisiert den Frequenzgang des FIR-Bandpassfilters.

Ergebnisse und Kommentar:

• Der Amplitudengang sollte zwischen den Grenzfrequenzen 500 Hz und 1500 Hz eine möglichst flache Durchlassbandcharakteristik zeigen.
• Außerhalb dieses Bereichs sollte der Filter die Amplituden dämpfen, insbesondere im Hochfrequenzbereich (oberhalb 1500 Hz).
• Der Phasengang gibt Aufschluss über die Phasenverschiebungen, die der Filter verursacht; im Durchlassband sollte die Phase möglichst linear sein.
• Wenn der Filter die oben genannten Anforderungen erfüllt, wird er das hochfrequente Rauschen effektiv entfernen und das gewünschte Signal im Durchlassband ungestört passieren lassen.

c)

Analysiere die Stabilität des entworfenen FIR-Filters anhand der Pol-Nullstellen-Plots im z-Bereich. Gib eine Erklärung zur Stabilität von FIR-Filtern im Allgemeinen.

Lösung:

Analyse der Stabilität des entworfenen FIR-Filters anhand der Pol-Nullstellen-Plots im z-BereichUm die Stabilität eines Filters zu analysieren, ist es wichtig, die Lage der Pol- und Nullstellen im z-Bereich zu untersuchen. Dies kann durch den Pol-Nullstellen-Plot (Pole-Zero-Plot) erfolgen. Die Stabilität eines Filters hängt von der Position der Pole im z-Bereich ab.

• Für FIR-Filter können wir diese Analyse durchführen, obwohl FIR-Filter per Definition stabil sind, da sie keine Pole außerhalb des Einheitskreises haben.
• Der Pol-Nullstellen-Plot wird durchgeführt, um die Verteilung der Nullstellen des Filters anzusehen.

Implementierung in Python:

• Das folgende Python-Skript zeigt, wie man die Nullstellen im z-Bereich für den entworfenen Filter berechnet und visualisiert:

import numpy as npfrom scipy.signal import firwin, freqz, zpk2tfimport matplotlib.pyplot as pltfs = 8000  # AbtastfrequenzfL = 500  # untere GrenzfrequenzfH = 1500  # obere Grenzfrequenznumtaps = 101  # Filterordnungwn = [fL / (fs / 2), fH / (fs / 2)]  # normalisierte Frequenzenh = firwin(numtaps, wn, pass_zero='bandpass', window='hamming')print('Filter Koeffizienten:', h)# Berechnen der Nullstellen des FIR-Filterszeros = np.roots(h)
k = 1  # Gain-Faktorplt.figure(figsize=(8, 8))plt.title('Pol-Nullstellen-Plot des FIR-Filters im z-Bereich')plt.xlabel('Re')plt.ylabel('Im')plt.grid(True)plt.axhline(0, color='black', lw=1)plt.axvline(0, color='black', lw=1)# Einheitkreis plottenunit_circle = plt.Circle((0, 0), 1, color='black', fill=False, ls='dotted')plt.gca().add_artist(unit_circle)# Nullstellen plottenplt.scatter(zeros.real, zeros.imag, s=50, color='blue', label='Nullstellen')# Marken setzen für die Pole (keine Pole für FIR)plt.scatter(poles.real, poles.imag, s=50, color='red', label='Pole')plt.legend()plt.show()

Erklärung zur Stabilität von FIR-Filtern im Allgemeinen:

• FIR-Filter (Finite Impulse Response) sind per Definition stabil, da sie nur Nullstellen besitzen und keine Pole außerhalb des Einheitskreises.
• Da FIR-Filter keine rekursiven Komponentensignale haben, bleibt die Ausgabe immer innerhalb der Grenzen des Eingangs. Dies garantiert Stabilität.
• Im Gegensatz zu IIR-Filtern (Infinite Impulse Response), die Pole haben können, sind FIR-Filter stabiler und einfacher zu entwerfen, insbesondere in Bezug auf Phaseneigenschaften.
• In der Praxis erweisen sich FIR-Filter aufgrund ihrer Stabilität und linearphasigen Eigenschaften als sehr nützlich in vielen Anwendungen der digitalen Signalverarbeitung.