Projektseminar Optimierung - Exam

Aufgabe 1)

In einer bestimmten Optimierungsaufgabe wird Dir eine Menge von Punkten gegeben, und es ist bekannt, dass diese Punkte aus einer konvexen Menge stammen. Du sollst die folgenden Eigenschaften der Menge und der Funktionen darauf untersuchen und beweisen.

a)

Sei die Menge von Punkten durch die Menge \( C \subseteq \mathbb{R}^2 \) gegeben. Zeige, dass die Menge \( C \) konvex ist, indem Du die formale Definition der Konvexität anwendest. Wähle willkürliche Punkte \( x, y \in C \) und zeige, dass für alle \( \lambda \in [0,1] \) gilt: \( \lambda x + (1 - \lambda)y \in C \).

Lösung:

Beweis:

Um zu zeigen, dass die Menge C konvex ist, müssen wir die formale Definition der Konvexität anwenden. Eine Menge C in \(\bb{R}^2\) ist konvex, wenn für alle Punkte x und y in C und jedes \( \lambda \in [0,1] \) der Punkt \( \lambda x + (1 - \lambda)y \in C \) liegt.

Schritte:

• Wähle willkürliche Punkte x und y aus der Menge C.
• Nimm ein beliebiges \( \lambda \in [0,1] \).
• Betrachte die Linearkombination \( \lambda x + (1 - \lambda) y \).

Beweis:

Seien x und y zwei beliebige Punkte in C. Wir müssen zeigen, dass \( \lambda x + (1 - \lambda)y \in C \) für jedes \( \lambda \in [0,1] \) gilt.

• Da x und y in C liegen, zeigt die Definition der Konvexität, dass jeder Punkt auf der Linie, die x und y verbindet, ebenfalls in C liegt.
• Sei \(\bb{x}\) der Vektor, der den Punkt x in \(\bb{R}^2\) darstellt, und \(\bb{y}\) der Vektor, der den Punkt y darstellt.
• Die Linearkombination \( \lambda x + (1 - \lambda)y \) kann als gewichtete Summe der beiden Punkte interpretiert werden, wobei \( \lambda\) und \( (1 - \lambda)\) die Gewichte sind, die die Anteile von x und y bestimmen.
• Diese Kombination berücksichtigt alle Punkte auf der Linie zwischen x und y, da die Gewichtung von \( \lambda\) und \( (1 - \lambda)\) bei \( \lambda = 0\) den Punkt y ergibt und bei \( \lambda = 1\) den Punkt x.

Da x und y beliebig gewählt sind und alle Punkte auf der Linie ebenfalls in der Menge C liegen, erfüllt die Menge C die Bedingung der Konvexität. Daher ist die Menge C konvex.

b)

Betrachte eine Funktion \( f: \mathbb{R}^2 \rightarrow \mathbb{R}\), die auf der Menge \( C \) definiert ist. Zeige, dass diese Funktion konvex ist, indem Du für beliebige Punkte \( x, y \in C \) und \( \lambda \in [0,1] \) die Ungleichung \( f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \) überprüfst.

Lösung:

Beweis:

Um zu zeigen, dass die Funktion f: \( \mathbb{R}^2 \rightarrow \mathbb{R} \), die auf der Menge C definiert ist, konvex ist, müssen wir die Ungleichung

\[ f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \] für beliebige Punkte x und y in C sowie für beliebige \( \lambda \in [0,1] \) überprüfen.

Schritte:

• Wähle beliebige Punkte x und y aus der Menge C.
• Nimm ein beliebiges \( \lambda \in [0,1] \).
• Betrachte die Funktion f an der Stelle der Linearkombination \( \lambda x + (1 - \lambda) y \).
• Überprüfe, ob die Ungleichung \[ f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \] erfüllt ist.

Beweis:

Seien x und y zwei beliebige Punkte in der Menge C und \( \lambda \in [0,1] \). Wir möchten überprüfen, ob die folgende Ungleichung gilt:

\[ f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \]

• Da x und y in der konvexen Menge C liegen, liegt auch der Punkt \( \lambda x + (1 - \lambda)y \) in C. Dies folgt direkt aus der Definition der Konvexität.
• Nun müssen wir zeigen, dass die Funktion f die Ungleichung \[ f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \] erfüllt. Dies bedeutet, dass der Wert der Funktion f an der Stelle \( \lambda x + (1 - \lambda)y \) kleiner oder gleich der gewichteten Summe der Funktionswerte f(x) und f(y) ist.

Um dies zu beweisen, gehen wir Schritt für Schritt vor:

1. Linearkombination betrachten: Setze \( z = \lambda x + (1 - \lambda)y \). Da z in C liegt, existiert der Funktionswert \( f(z) \).
2. Konvexität der Funktion: Um die Konvexität der Funktion zu überprüfen, müssen wir zeigen, dass \[ f(z) \leq \lambda f(x) + (1 - \lambda) f(y) \].
3. Analytische Methode: Eine allgemeine Methode, dies zu zeigen, besteht darin, eine bekannte konvexe Funktion zu verwenden, zum Beispiel die quadratische Funktion \( f(x) = \|x\|^2 \).

Beispiel: Angenommen, f sei die quadratische Funktion

\[ f(x) = \|x\|^2 \],

• dann ist f durch ihre Definition konvex. Dies kann überprüft werden, indem man zeigt:
• Betrachte die Linke Seite unserer Ungleichung: \[ f(\lambda x + (1 - \lambda)y) = \|\lambda x + (1 - \lambda)y\|^2 \]
• Nun betrachten wir die rechte Seite der Ungleichung: \[ \lambda f(x) + (1 - \lambda) f(y) = \lambda \|x\|^2 + (1 - \lambda) \|y\|^2 \]

Da eine Norm durch ihre Definition konvex ist, ergibt:

\[ \|\lambda x + (1 - \lambda)y\|^2 \leq \lambda \|x\|^2 + (1 - \lambda) \|y\|^2 \]

Schlussfolgerung: Dies zeigt, dass

\[ f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda) f(y) \]

für die quadratische Funktion \(f(x) = \|x\|^2\) erfüllt ist, was die Konvexität dieser speziellen Funktion beweist.

Dieses Prinzip kann auf andere Funktionen angewendet werden, indem geeignete Methoden zum Nachweis der Konvexität verwendet werden.

c)

Finde ein Beispiel für eine Menge, die nicht konvex ist, und zeige anhand der formalen Definition, warum diese Menge nicht die Konvexitätseigenschaft erfüllt. Beschreibe ein Paar von Punkten in der Menge und einen Wert von \( \lambda \), der die Non-Konvexität veranschaulicht.

Lösung:

Beispiel für eine nicht-konvexe Menge:

Betrachten wir die Menge D in \(\mathbb{R}^2\), die durch zwei getrennte Intervalle auf der x-Achse definiert ist:

\[ D = \{(x, y) \in \mathbb{R}^2 : (x = -1, \, -1 \leq y \leq 1) \, oder \, (x = 1, \, -1 \leq y \leq 1)\} \]

Diese Menge besteht aus zwei vertikalen Liniensegmenten, ein Segment bei \(x = -1\) und ein Segment bei \(x = 1\). Diese beiden Segmente sind nicht verbunden und liegen weit auseinander.

Überprüfung der Nicht-Konvexität:

Um zu zeigen, dass diese Menge nicht konvex ist, müssen wir nachweisen, dass es zwei Punkte \( x, y \in D \) und einen Wert \( \lambda \in [0,1] \) gibt, für die der Punkt

\[ \lambda x + (1 - \lambda)y \]

nicht in \( D \) liegt.

• Wähle die beiden Punkte \( A = (-1, 0) \) und \( B = (1, 0) \) aus der Menge D.
• Betrachte den Wert \( \lambda = 0.5 \).
• Berechne die Linearkombination der beiden Punkte:

\[ C = \lambda A + (1 - \lambda) B = 0.5(-1, 0) + 0.5(1, 0) = (0, 0) \]

Der Punkt \(C = (0, 0)\) liegt genau in der Mitte zwischen den beiden Punkten \((-1, 0)\) und \((1, 0)\) auf der x-Achse.

Überprüfung der Zugehörigkeit:

Der Punkt \( C = (0, 0) \) liegt nicht in der Menge D, da D lediglich die Punkte bei \(x = -1\) und \(x = 1\) umfasst und keine Punkte mit \(x = 0\).

Schlussfolgerung:

Da der Punkt \( C = (0, 0) \) nicht in der Menge D liegt, erfüllt D nicht die Konvexitätseigenschaft. Das bedeutet, dass D keine konvexe Menge ist.

Diese Veranschaulichung zeigt deutlich, warum D nicht konvex ist, da es möglich ist, zwei Punkte in D zu finden, deren Linearkombination nicht in D liegt.

d)

Berechne den Durchschnitt zweier konvexer Mengen \( A \) und \( B \) und zeige, dass der Durchschnitt ebenfalls eine konvexe Menge ist. Verwende dazu die formale Definition der Konvexität, um nachzuweisen, dass für beliebige Punkte \( x, y \in A \cap B \) und \( \lambda \in [0,1] \) gilt: \( \lambda x + (1 - \lambda)y \in A \cap B \).

Lösung:

Beweis:

Um zu zeigen, dass der Durchschnitt zweier konvexer Mengen A und B ebenfalls eine konvexe Menge ist, müssen wir die formale Definition der Konvexität anwenden. Das bedeutet, wir müssen nachweisen, dass für beliebige Punkte x und y in A und B und für beliebige \(\lambda \in [0,1]\) der Punkt \(\lambda x + (1 - \lambda)y\) in A und B liegt. Dies zeigt, dass \(\lambda x + (1 - \lambda)y\) im Durchschnitt \(A \cap B\) liegt.

Schritte:

• Seien \(A\) und \(B\) konvexe Mengen.
• Wähle beliebige Punkte \(x, y \in A \cap B\).
• Nimm ein beliebiges \( \lambda \in [0,1] \).
• Berechne den Punkt \( \lambda x + (1 - \lambda)y \).
• Zeige, dass dieser Punkt sowohl in A als auch in B liegt.

Beweis:

Seien x und y zwei beliebige Punkte im Durchschnitt der Mengen A und B, d.h., \(x, y \in A \cap B\). Dies bedeutet, dass \(x\) und \(y\) sowohl in A als auch in B liegen.Nehmen wir nun ein beliebiges \(\lambda \in [0,1]\).

Da \(A\) und \(B\) konvex sind, gilt:

• Da \(x\) und \(y\) in A liegen und A konvex ist, liegt der Punkt \(\lambda x + (1 - \lambda)y\) in A.
• Da \(x\) und \(y\) in B liegen und B konvex ist, liegt der Punkt \(\lambda x + (1 - \lambda)y\) in B.

Da der Punkt \(\lambda x + (1 - \lambda)y\) sowohl in A als auch in B liegt, liegt er somit im Durchschnitt \(A \cap B\).

Schlussfolgerung:

Wir haben gezeigt, dass für beliebige Punkte \(x, y \in A \cap B\) und für beliebige \(\lambda \in [0,1]\) der Punkt \(\lambda x + (1 - \lambda)y\) ebenfalls im Durchschnitt \(A \cap B\) liegt. Dies beweist, dass der Durchschnitt \(A \cap B\) konvex ist.

Aufgabe 2)

Ein Unternehmen möchte die Produktionskosten minimieren, während es bestimmte Produktionsauflagen erfüllt. Die Zielfunktion beschreibt die Gesamtkosten der Produktion für verschiedene Produkte, und die Nebenbedingungen repräsentieren die Produktionsanforderungen. Die Kostenfunktion sei gegeben durch f(x) und die Nebenbedingungen durch g(x). Du sollst die Lagrange-Multiplikatoren nutzen, um das Problem zu lösen, und das duale Problem formulieren und untersuchen, ob schwache oder starke Dualität vorliegt.

a)

Formuliere das primale Optimierungsproblem als Minimierungsproblem:

• Zielfunktion: Die Kostenfunktion sei

   \( f(x) = 2x_1^2 + 3x_2^2 + x_1x_2 \) 

• Nebenbedingungen: Die Produktionsauflagen sind

   \( g_1(x) = x_1 + x_2 - 1 \ g_2(x) = x_1 - 0.5 \) 

Lösung:

Primales Optimierungsproblem

• Zielfunktion: Die Kostenfunktion sei gegeben durch:

   \( f(x) = 2x_1^2 + 3x_2^2 + x_1 x_2 \) 

• Nebenbedingungen: Die Produktionsauflagen sind:

   \( g_1(x) = x_1 + x_2 - 1 \)  \( g_2(x) = x_1 - 0.5 \) 

b)

Leite die KKT-Bedingungen für das Problem her und bestimme die Werte von abla f(x) und abla g(x). Überprüfe, ob diese Bedingungen erfüllt sind und berechne die möglichen Lösungen für x und \lambda unter Verwendung der Lagrange-Funktion

 \( \mathcal{L}(x, \lambda) = f(x) + \lambda^T g(x) \) 

Lösung:

Lösen des Optimierungsproblems mit Lagrange-Multiplikatoren

Um das Optimierungsproblem zu lösen, nutzen wir die KKT-Bedingungen. Zuerst sollten wir die Lagrange-Funktion formulieren:

Die Lagrange-Funktion lautet:

 \( \mathcal{L}(x, \lambda) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x) \) 

Wobei:

• \( f(x) = 2x_1^2 + 3x_2^2 + x_1x_2 \)
• \( g_1(x) = x_1 + x_2 - 1 \)
• \( g_2(x) = x_1 - 0.5 \)

Die Lagrange-Funktion ist somit:

 \( \mathcal{L}(x, \lambda) = 2x_1^2 + 3x_2^2 + x_1 x_2 + \lambda_1 (x_1 + x_2 - 1) + \lambda_2 (x_1 - 0.5) \) 

Wir müssen die partiellen Ableitungen der Lagrange-Funktion bestimmen:

• \( \frac{{\partial \mathcal{L}}}{{\partial x_1}} = 4x_1 + x_2 + \lambda_1 + \lambda_2 \)
• \( \frac{{\partial \mathcal{L}}}{{\partial x_2}} = 6x_2 + x_1 + \lambda_1 \)
• \( \frac{{\partial \mathcal{L}}}{{\partial \lambda_1}} = x_1 + x_2 - 1 \)
• \( \frac{{\partial \mathcal{L}}}{{\partial \lambda_2}} = x_1 - 0.5 \)

Setze alle partiellen Ableitungen gleich Null um die KKT-Bedingungen zu erfüllen:

 \( \begin{cases} 4x_1 + x_2 + \lambda_1 + \lambda_2 = 0 \ 6x_2 + x_1 + \lambda_1 = 0 \ x_1 + x_2 - 1 = 0 \ x_1 - 0.5 = 0 \ \end{cases} \) 

Wir wissen aus \( x_1 - 0.5 = 0 \), dass \( x_1 = 0.5 \).

Substituiere \( x_1 = 0.5 \) in die dritte Gleichung:

 \( 0.5 + x_2 - 1 = 0 \)

 \( x_2 = 0.5 \)

Das ergibt \( x_1 = 0.5 \) und \( x_2 = 0.5 \).

Berechne nun die Lagrange-Multiplikatoren \( \lambda \):

• \( 4(0.5) + 0.5 + \lambda_1 + \lambda_2 = 0 \)
• \( 6(0.5) + 0.5 + \lambda_1 = 0 \)

 \( \lambda_1 = -3.5 \) \( 2.5 + \lambda_2 = -3.5 \) \( \lambda_2 = -6 \) 

Die Lösungen sind:

• \( x_1 = 0.5 \)
• \( x_2 = 0.5 \)
• \( \lambda_1 = -3.5 \)
• \( \lambda_2 = -6 \)

Somit sind die KKT-Bedingungen erfüllt, und wir haben die optimalen Werte für \( x \) und \( \lambda \) bestimmt.

Aufgabe 3)

Gegeben ist ein lineares Programm:

• Maximiere: z = 3x_1 + 2x_2
• unter den Nebenbedingungen:
• 2x_1 + x_2 ≤ 10
• x_1 + x_2 ≤ 8
• x_1, x_2 ≥ 0

• Führe das Simplex-Verfahren von einer zulässigen Basislösung ausgehend durch.
• Finde die optimale Basislösung und überprüfe die Zielfunktion.

a)

Teilaufgabe 1:

• Formuliere das Problem im Standardformen mit Hilfe der Schlupfvariablen s1 und s2.
• Berechne die anfängliche zulässige Basislösung.
• Ergebnis: Setze die Variablen in die Gleichungen ein und überprüfe die Lösung.

Lösung:

Gegeben ist ein lineares Programm:

• Maximiere: z = 3x_1 + 2x_2
• unter den Nebenbedingungen:
• 2x_1 + x_2 ≤ 10
• x_1 + x_2 ≤ 8
• x_1, x_2 ≥ 0

• Führe das Simplex-Verfahren von einer zulässigen Basislösung ausgehend durch.
• Finde die optimale Basislösung und überprüfe die Zielfunktion.

Teilaufgabe 1:

• Formuliere das Problem im Standardformen mit Hilfe der Schlupfvariablen s1 und s2.
• Berechne die anfängliche zulässige Basislösung.
• Ergebnis: Setze die Variablen in die Gleichungen ein und überprüfe die Lösung.

Hier ist die Lösung zu Teilaufgabe 1 in kleinen Schritten: 1. Formuliere das Problem in Standardform: Zuerst fügen wir Schlupfvariablen (s1 und s2) zu den Ungleichungen hinzu, um sie in Gleichungen umzuwandeln.

• Die ursprünglichen Ungleichungen lauten:
  • 2x_1 + x_2 ≤ 10
  • x_1 + x_2 ≤ 8
• Durch Hinzufügen der Schlupfvariablen werden diese zu:
  • 2x_1 + x_2 + s1 = 10
  • x_1 + x_2 + s2 = 8

Hierbei sind s1 und s2 ≥ 0. 2. Schreibe die Standardform des linearen Programms:

• Zielfunktion: Maximiere z = 3x_1 + 2x_2
• Nebenbedingungen:
  • 2x_1 + x_2 + s1 = 10
  • x_1 + x_2 + s2 = 8
  • x_1, x_2, s1, s2 ≥ 0

3. Berechne die anfängliche zulässige Basislösung: In der anfänglichen Basislösung setzen wir die nicht-Basisvariablen (x1 und x2) auf 0 und berechnen die Werte der Basisvariablen (s1 und s2).

• Setze x1 = 0 und x2 = 0:
• Die Gleichungen werden zu:
  • s1 = 10
  • s2 = 8

Daraus folgt, dass die anfängliche Basislösung lautet:x1 = 0, x2 = 0, s1 = 10, s2 = 8 Ergebnis: Setzen wir die ermittelten Werte in die ursprünglichen Gleichungen ein, erhalten wir:

• 2x_1 + x_2 + s1 = 2*0 + 0 + 10 = 10
• x_1 + x_2 + s2 = 0 + 0 + 8 = 8

Die anfängliche Basislösung (x1 = 0, x2 = 0, s1 = 10, s2 = 8) erfüllt also die Gleichungen und ist damit zulässig.

b)

Teilaufgabe 2:

• Führe die ersten zwei Iterationen des Simplex-Verfahrens durch.
• Bestimme die ein- und ausgehenden Variablen und berechne die aktualisierte Basislösung nach jeder Iteration.
• Verwende die Simplex-Tabelle, um den Prozess zu verdeutlichen.
• Ergebnis: Dokumentiere jeden Schritt und überprüfe, ob die Zielfunktion verbessert wurde.

Lösung:

Gegeben ist ein lineares Programm:

• Maximiere: z = 3x_1 + 2x_2
• unter den Nebenbedingungen:
• 2x_1 + x_2 ≤ 10
• x_1 + x_2 ≤ 8
• x_1, x_2 ≥ 0

• Führe das Simplex-Verfahren von einer zulässigen Basislösung ausgehend durch.
• Finde die optimale Basislösung und überprüfe die Zielfunktion.

Teilaufgabe 2:

• Führe die ersten zwei Iterationen des Simplex-Verfahrens durch.
• Bestimme die ein- und ausgehenden Variablen und berechne die aktualisierte Basislösung nach jeder Iteration.
• Verwende die Simplex-Tabelle, um den Prozess zu verdeutlichen.
• Ergebnis: Dokumentiere jeden Schritt und überprüfe, ob die Zielfunktion verbessert wurde.

Hier ist die Lösung zu Teilaufgabe 2, Schritt für Schritt: 1. Anfängliche Simplex-Tabelle:

• Füge Schlupfvariablen hinzu und schreibe das lineare Programm in Standardform:

 Maximiere: z = 3x_1 + 2x_2  Nebenbedingungen:  2x_1 + x_2 + s1 = 10  x_1 + x_2 + s2 = 8  x_1, x_2, s1, s2 ≥ 0 

Initiale Basislösung: x1 = 0, x2 = 0, s1 = 10, s2 = 8

Initiale Simplex-Tabelle:

| Basis | cB | x1  | x2  | s1 | s2 | RHS | |-------|----|-----|-----|----|----|-----| |  s1   |  0 |  2  |  1  | 1  | 0  | 10  | |  s2   |  0 |  1  |  1  | 0  | 1  |  8  | |-------|----|-----|-----|----|----|-----| |   z   |    | -3  | -2  | 0  | 0  |  0  |

2. Erste Iteration:

• Bestimme die eintrittende Variable: x1, da -3 am negativsten ist.
• Bestimme die austretende Variable:
  • s1: 10 / 2 = 5
  • s2: 8 / 1 = 8
  Die austretende Variable ist s1, da 5 das kleinste Verhältnis ist.

Pivotiere:

• Führe elementare Reihenoperationen durch, um x1 in die Basis aufzunehmen und s1 zu entfernen:

| Basis | cB | x1 | x2  |  s1   | s2 | RHS | |-------|----|----|-----|------|----|-----| |  x1   |  3 |  1 | 0.5 | 0.5  | 0  |  5  | |  s2   |  0 |  0 | 0.5 | -0.5 | 1  |  3  | |-------|----|----|-----|------|----|-----| |   z   |    |  0 | -0.5| 1.5  | 0  | 15  |

3. Zweite Iteration:

• Bestimme die eintrittende Variable: x2, da -0.5 am negativsten ist.
• Bestimme die austretende Variable:
  • x1: 5 / 0.5 = 10
  • s2: 3 / 0.5 = 6
  Die austretende Variable ist s2, da 6 das kleinste Verhältnis ist.

Pivotiere:

• Führe elementare Reihenoperationen durch, um x2 in die Basis aufzunehmen und s2 zu entfernen:

| Basis | cB | x1 | x2 | s1 | s2 | RHS  | |-------|----|----|----|----|----|------| |  x1   |  3 |  1 |  0 | 1  | -1 |  4   | |  x2   |  2 |  0 |  1 | -1 |  2 |  6   | |-------|----|----|----|----|----|------| |   z   |    |  0 |  0 |  1 |  1 |  18  |

Ergebnis nach zwei Iterationen:

• Aktualisierte Basislösung: x1 = 4, x2 = 6, s1 = 0, s2 = 0
• Zielfunktion (z) = 18; hat sich verbessert.

Jeder Schritt wurde dokumentiert und die Verbesserung der Zielfunktion überprüft.

Aufgabe 4)

Betrachten wir ein konvexes Optimierungsproblem, welches mithilfe eines Inneren-Punkte-Verfahrens (Interior-Point Method) gelöst werden soll:

Gegebene Optimierungsaufgabe:

Minimiere die Funktion \( f(x) = x^2 + y^2 + z^2 \)

unter den Nebenbedingungen:

• \( x + y + z = 1 \)
• \( x, y, z > 0 \)

Benutze eine Barrieremethode, um das Problem zu lösen. Dabei wird der Barriere-Term zu der Zielfunktion hinzugefügt:

\( L(x, y, z, t) = x^2 + y^2 + z^2 - \frac{1}{t} (\text{log}(x) + \text{log}(y) + \text{log}(z)) \)

• Initialisierungspunkt: \( (x_0, y_0, z_0) = (0.3, 0.3, 0.4) \)

a)

Leite die KKT-Bedingungen für dieses Problem her und formuliere das Lagrange-System, das zur Lösung der Näherungsprobleme verwendet wird. Berechne danach die ersten Newton-Schritte.

Lösung:

Um das gegebene Optimierungsproblem zu lösen, lassen sich die KKT-Bedingungen (Karush-Kuhn-Tucker-Bedingungen) herleiten. Diese vervollständigen das Lagrange-System, welches für die Näherungsprobleme verwendet wird. Gehen wir Schritt für Schritt vor:

1. Das Lagrange-System:

Die Zielfunktion lautet:

\( f(x, y, z) = x^2 + y^2 + z^2 \)

Die Nebenbedingungen sind:

• \( x + y + z = 1 \)
• \( x, y, z > 0 \)

Unter der Verwendung einer Barrierefunktion ergibt sich die modifizierte Zielfunktion:

\( L(x, y, z, t) = x^2 + y^2 + z^2 - \frac{1}{t} (\text{log}(x) + \text{log}(y) + \text{log}(z)) \)

Mit der Lagrange-Multiplikator-Variable \( \lambda \) kann das Lagrange-System erstellt werden:

\( L(x, y, z, \lambda, t) = x^2 + y^2 + z^2 - \frac{1}{t} (\text{log}(x) + \text{log}(y) + \text{log}(z)) + \lambda (x + y + z - 1) \)

2. Herleitung der KKT-Bedingungen:

Die KKT-Bedingungen beinhalten die folgenden Gleichungen:

• \( \frac{\partial L}{\partial x} = 2x - \frac{1}{t} \frac{1}{x} + \lambda = 0 \)
• \( \frac{\partial L}{\partial y} = 2y - \frac{1}{t} \frac{1}{y} + \lambda = 0 \)
• \( \frac{\partial L}{\partial z} = 2z - \frac{1}{t} \frac{1}{z} + \lambda = 0 \)
• \( \frac{\partial L}{\partial \lambda} = x + y + z - 1 = 0 \)

3. Berechnung der ersten Newton-Schritte:

Mit den KKT-Bedingungen haben wir ein Gleichungssystem. Wir können typische Schritte des Newton-Verfahrens anwenden, um eine numerische Lösung zu finden. Hier sind die Schritte:

• Setze den Initialisierungspunkt \((x_0, y_0, z_0) = (0.3, 0.3, 0.4)\) ein.
• Initialisiere \(\lambda\) mit einem Startwert, beispielsweise 0.
• Berechne die partiellen Ableitungen des Lagrange-Systems am Initialisierungspunkt:

\(f_x = 2x - \frac{1}{t} \frac{1}{x} + \lambda\)\(f_y = 2y - \frac{1}{t} \frac{1}{y} + \lambda\)\(f_z = 2z - \frac{1}{t} \frac{1}{z} + \lambda\)\(f_\lambda = x + y + z - 1\)

Einsetzen der Werte \(x = 0.3\), \(y = 0.3\), \(z = 0.4\) und ein Startwert für \(t\), beispielsweise \(t = 1\):

\(f_x = 2(0.3) - \frac{1}{1} \frac{1}{0.3} + 0 \)\(f_y = 2(0.3) - \frac{1}{1} \frac{1}{0.3} + 0 \)\(f_z = 2(0.4) - \frac{1}{1} \frac{1}{0.4} + 0 \)\(f_\lambda = 0.3 + 0.3 + 0.4 - 1\)

Dies führt zu:

\(f_x = 0.6 - \frac{1}{0.3}\)\(f_y = 0.6 - \frac{1}{0.3}\)\(f_z = 0.8 - \frac{1}{0.4}\)\(f_\lambda = 1.0 - 1\)

4. Berechnung der Jacobian-Matrix und des Hessian:

Nun können numerische Verfahren (z.B. Newton-Raphson) verwendet werden, um die vier Variablen zu aktualisieren und eine iterative Berechnung

f1_t = (0.6 - \frac{1}{0.3}, 0.6 - \frac{1}{0.3}, 0.8 - \frac{1}{0.4}, 1.0 - 1)

b)

Diskutiere die Vorteile des Innen-Punkte-Verfahrens gegenüber klassischen Verfahren wie dem Simplex-Verfahren, insbesondere im Kontext großer und spärlich besetzter Probleme.

Lösung:

Das Innen-Punkte-Verfahren (Interior-Point Method) ist eine effiziente Methode zur Lösung von Optimierungsproblemen, besonders wenn es um große und spärlich besetzte Probleme geht. Hier sind einige Vorteile des Innen-Punkte-Verfahrens im Vergleich zu klassischen Verfahren wie dem Simplex-Verfahren:

• Effizienz bei großen Problemen: Das Innen-Punkte-Verfahren ist in der Lage, große Optimierungsprobleme effizient zu lösen. Es bietet eine bessere Skalierbarkeit als das Simplex-Verfahren, da seine Rechenzeit typischerweise polynomial ansteigen kann, während die Rechenzeit des Simplex-Verfahrens im schlimmsten Fall exponentiell ansteigen kann.
• Bewältigung spärlicher Matrizen: Innen-Punkte-Verfahren nutzen die Struktur spärlicher Matrizen, was die Speichernutzung und Rechenzeit deutlich reduzieren kann. Dies ist besonders wichtig in Bereichen wie Netzoptimierung oder großen Datenanalysen, wo die Problemsysteme oft sehr groß, aber spärlich besetzt sind.
• Numerische Stabilität: Das Innen-Punkte-Verfahren tendiert zu einer besseren numerischen Stabilität im Vergleich zum Simplex-Verfahren, besonders bei schlecht konditionierten Problemen. Das liegt daran, dass das Innen-Punkte-Verfahren deutlich weniger auf Pivot-Operationen angewiesen ist, die anfällig für numerische Fehler sein können.
• Polynomielle Konvergenz: Das Innen-Punkte-Verfahren hat bewiesene polynomielle Konvergenzeigenschaften, die für eine gewisse Klasse von Problemen garantieren, dass die Lösung in einem praktikablen Zeitrahmen gefunden wird. Das Simplex-Verfahren hat dagegen keine festen Konvergenzgarantien und kann im schlimmsten Fall deutlich längere Rechenzeiten haben.
• Nah an der optimalen Lösung: Innen-Punkte-Verfahren bewegen sich im Inneren des zulässigen Bereichs und konvergieren typischerweise direkt zur optimalen Lösung. Im Gegensatz dazu bewegt sich das Simplex-Verfahren entlang der Kanten des Polytops und kann so in hohe Dimensionen vielfach durch unerwünschte Regionen wandern, bevor es die optimale Lösung findet.
• Robustheit gegenüber Degenerationen: Innen-Punkte-Verfahren sind robuster gegenüber degenerierten Problemen, d.h. Problemen, bei denen viele Nebenbedingungen aktiv sind oder mehrere optimale Lösungen existieren, was beim Simplex-Verfahren zu Zyklischen Wechseln oder langen Pfaden führen kann.

Zusammenfassend lässt sich sagen, dass das Innen-Punkte-Verfahren für große und spärlich besetzte Optimierungsprobleme mehrere signifikante Vorteile gegenüber dem Simplex-Verfahren bietet. Es zeichnet sich durch bessere Effizienz, Skalierbarkeit und numerische Stabilität aus, was es zu einer bevorzugten Wahl in vielen praktischen Anwendungen macht.