Kapitel 4 – Nichtlineare Optimierung

Auf einen Blick

Nichtlineare Optimierung löst Extremwertaufgaben, in denen Zielfunktion oder Nebenbedingungen nicht linear sind – klassisches Analysis-Werkzeug statt Simplex.
Bei einer Variablen: $f'(x)=0$ (notwendig), $f''(x)>0$ oder $<0$ (hinreichend). Ränder separat prüfen.
Bei mehreren Variablen: $\nabla f(\vec{x})=\vec{0}$ (notwendig), Eigenwerte der Hesse-Matrix geben Aussage über Minimum, Maximum oder Sattelpunkt.
Ohne Nebenbedingungen: analytisch oder iterativ via Gradientenverfahren (Richtung des steilsten Anstiegs, optimale Schrittweite $\mu_{opt}$).
Mit Nebenbedingungen: Lagrangefunktion $L(x,u) = f(x) - \sum u_i g_i(x)$, Sattelpunkte ergeben Extrema. Vollständige Charakterisierung durch die Kuhn-Tucker-Bedingungen.

Kernkonzepte

4.1 Gegenüberstellung: eine vs. mehrere Variablen

Der klassische Analysis-Zugang zur Extremwertsuche verallgemeinert sich strukturgleich vom 1D- auf den mehrdimensionalen Fall – nur werden Ableitung durch Gradient und zweite Ableitung durch Hesse-Matrix ersetzt.

Aspekt	$n = 1$ (eine Variable)	$n > 1$ (mehrere Variablen)
Notwendige Bedingung	$f'(x) = 0$	$\nabla f(\vec{x}) = \vec{0}$
Hinreichende Bedingung Minimum	$f''(x) > 0$	Alle Eigenwerte der Hesse-Matrix $> 0$ (positiv definit)
Hinreichende Bedingung Maximum	$f''(x) < 0$	Alle Eigenwerte der Hesse-Matrix $< 0$ (negativ definit)
Globales Optimum	Kandidaten + Randwerte vergleichen	Sattelpunkte der Lagrangefunktion untersuchen

4.2 Mathematische Grundlagen

Partielle Ableitung

Bei einer Funktion $f(x_1, x_2, \dots, x_n)$ betrachtet die partielle Ableitung $\dfrac{\partial f}{\partial x_i}$ nur die Änderung entlang $x_i$, alle anderen Variablen werden als Konstanten behandelt.

Beispiel: $f(x, y) = 3x^2 y + y^3 \Rightarrow \dfrac{\partial f}{\partial x} = 6xy, \quad \dfrac{\partial f}{\partial y} = 3x^2 + 3y^2$

Gradient

Der Gradient ist der Vektor aller partiellen Ableitungen. Er zeigt in Richtung des steilsten Anstiegs, sein Betrag entspricht der Steigung in dieser Richtung.

$\nabla f(\vec{x}) = \left( \dfrac{\partial f}{\partial x_1}, \dfrac{\partial f}{\partial x_2}, \dots, \dfrac{\partial f}{\partial x_n} \right)^T$

Hesse-Matrix

Die Hesse-Matrix $H$ enthält alle zweiten partiellen Ableitungen. Sie ist symmetrisch (Satz von Schwarz) und die Verallgemeinerung von $f''(x)$.

$H_{ij} = \dfrac{\partial^2 f}{\partial x_i \partial x_j}, \quad H = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix}$

Eigenwerte und Eigenvektoren

Ein Eigenvektor $\vec{x}$ einer Matrix $A$ erfüllt $A \vec{x} = \lambda \vec{x}$ – die Matrix streckt oder staucht ihn nur um den Faktor $\lambda$ (Eigenwert), ohne die Richtung zu ändern.

Charakteristisches Polynom: $\det(A - \lambda E) = 0$

4.3 Konvexität

Konvexität ist zentral, weil sie garantiert, dass ein lokales Minimum automatisch global ist. Analog: Konkavität + Maximum.

Merksatz: Eine zweimal differenzierbare Funktion $f$ ist genau dann konvex, wenn die Hesse-Matrix an jedem Punkt positiv semi-definit ist – gleichbedeutend: alle Eigenwerte sind nicht-negativ. Für konkav: alle Eigenwerte nicht-positiv.

4.4 Optimierung ohne Nebenbedingungen

Notwendige Bedingung: $\nabla f(\vec{x}^*) = \vec{0}$. Die Kandidaten heißen stationäre Punkte. Ob es sich um Min, Max oder Sattelpunkt handelt, entscheidet die Hesse-Matrix.

Gradientenverfahren (iteratives Näherungsverfahren)

Startlösung $\vec{x}^{(0)}$ wählen.
Suchrichtung: bei Maximierung $+\nabla f$, bei Minimierung $-\nabla f$.
Optimale Schrittweite $\mu_{opt}$ bestimmen (eindimensionale Optimierung entlang der Richtung).
Neue Lösung: $\vec{x}^{(k+1)} = \vec{x}^{(k)} + \mu_{opt} \cdot \nabla f(\vec{x}^{(k)})$.
Wiederholen, bis $|\nabla f| < \varepsilon$ (Abbruchkriterium).

Wichtig: Das Gradientenverfahren liefert eine Näherungslösung, keine exakte Lösung. Es konvergiert lokal – bei nicht-konvexen Zielfunktionen ist das globale Optimum nicht garantiert.

4.5 Optimierung mit Nebenbedingungen

Aufgabenform: $\max f(\vec{x})$ unter $g_i(\vec{x}) \leq 0$ für $i = 1, \dots, m$.

Lagrangefunktion

$L(\vec{x}, \vec{u}) = f(\vec{x}) - \sum_{i=1}^{m} u_i \cdot g_i(\vec{x}), \qquad u_i \geq 0$

Die $u_i$ sind die Lagrange-Multiplikatoren. Sie bestrafen Verletzungen der Nebenbedingungen: verletzt eine Lösung eine NB ($g_i > 0$), wird der Zielfunktionswert durch $-u_i g_i$ reduziert – die Lösung wird unattraktiv.

Sattelpunktsatz: Ein Sattelpunkt der Lagrangefunktion – Maximum in $\vec{x}$, Minimum in $\vec{u}$ – entspricht einem Extremum des ursprünglichen Problems. Ist $f$ konkav und die $g_i$ konvex, ist das gefundene Maximum global.

Voraussetzungen

$f$ und alle $g_i$ sind stetig differenzierbar.
Slater-Bedingung: Es existiert mindestens ein innerer Punkt des zulässigen Bereichs, in dem alle NB strikt erfüllt sind ($g_i(\vec{x}) < 0$). Sichert die Existenz der Multiplikatoren.

4.6 Kuhn-Tucker-Bedingungen

Notwendige und (unter Konvexität) hinreichende Bedingungen für ein Maximum bei $g_i(\vec{x}) \leq 0$:

$\dfrac{\partial L}{\partial x_j} = 0$ für alle $j$ (Stationarität in $\vec{x}$)
$\dfrac{\partial L}{\partial u_i} \leq 0$ für alle $i$ (Zulässigkeit: $g_i(\vec{x}) \leq 0$)
$u_i \geq 0$ (nicht-negative Multiplikatoren)
$u_i \cdot g_i(\vec{x}) = 0$ (Komplementärschlupf)
$\vec{x} \geq \vec{0}$ (falls Nichtnegativität gefordert)
$x_j \cdot \dfrac{\partial L}{\partial x_j} = 0$ (falls Nichtnegativität in $\vec{x}$)

Komplementärschlupf anschaulich: Entweder ist die Nebenbedingung aktiv ($g_i = 0$, Rand des zulässigen Bereichs) – dann kann $u_i > 0$ sein. Oder die NB ist inaktiv ($g_i < 0$, "Platz übrig") – dann muss $u_i = 0$ sein. Beide dürfen niemals gleichzeitig ungleich Null sein.

Merksätze

Gradient anschaulich: Der Gradient ist ein Kompass – er zeigt vom aktuellen Punkt aus in die Richtung, in der die Funktion am steilsten ansteigt. Sein Betrag misst, wie steil dieser Anstieg ist. Bei $\nabla f = \vec{0}$ ist der Punkt "flach" – ein Kandidat für ein Extremum.

Hesse und Konvexität: Positiv (semi-)definite Hesse-Matrix ⇔ konvex ⇔ jede Sekante liegt oberhalb der Kurve ⇔ jedes lokale Minimum ist global. Test: alle Eigenwerte $\geq 0$.

Lagrange als Bestrafung: Die Terme $-u_i g_i(\vec{x})$ ziehen den Zielfunktionswert immer dann herunter, wenn eine Nebenbedingung verletzt ist ($g_i > 0$). Der Multiplikator $u_i$ ist gewissermaßen der "Preis" für die Verletzung dieser NB.

Slater-Bedingung: Existiert mindestens ein Punkt im Inneren des zulässigen Bereichs (alle $g_i(\vec{x}) < 0$ strikt), garantiert dies die Anwendbarkeit der Kuhn-Tucker-Theorie – sonst kann die Multiplikator-Theorie versagen.

Gradientenverfahren-Charakter: Iteratives Näherungsverfahren. Kein Anspruch auf exakte oder globale Lösung. Abbruch bei $|\nabla f| < \varepsilon$ – die Genauigkeit steuert man über $\varepsilon$.

🧮 Rechenaufgaben mit Lösung 8 Aufgaben

Klausur-typische Rechenaufgaben. Klick auf eine Aufgabe, um den vollständigen Lösungsweg zu sehen.

Aufgabe 1: Extremum einer 1-Variablen-Funktion

Aufgabe: Bestimme alle Extremwerte der Funktion $f(x) = x^3 - 6x^2 + 9x + 2$.

Lösung

Schritt 1 – Erste Ableitung bilden und Nullstellen suchen (notwendige Bedingung):

$f'(x) = 3x^2 - 12x + 9 = 3(x^2 - 4x + 3) = 3(x-1)(x-3)$

$f'(x) = 0 \Rightarrow x_1 = 1$ oder $x_2 = 3$.

Schritt 2 – Zweite Ableitung zur Klassifikation (hinreichende Bedingung):

$f''(x) = 6x - 12$

$f''(1) = 6 \cdot 1 - 12 = -6 < 0 \Rightarrow$ lokales Maximum bei $x=1$.
$f''(3) = 6 \cdot 3 - 12 = 6 > 0 \Rightarrow$ lokales Minimum bei $x=3$.

Schritt 3 – Funktionswerte berechnen:

$f(1) = 1 - 6 + 9 + 2 = 6$

$f(3) = 27 - 54 + 27 + 2 = 2$

Ergebnis: Lokales Maximum bei $(1, 6)$, lokales Minimum bei $(3, 2)$.

Aufgabe 2: Gradient und Hesse-Matrix

Aufgabe: Berechne den Gradienten und die Hesse-Matrix von $f(x_1, x_2) = x_1^2 + 2x_1 x_2 + 3x_2^2 - 4x_1 + 2x_2$.

Lösung

Schritt 1 – Partielle Ableitungen erster Ordnung:

$\dfrac{\partial f}{\partial x_1} = 2x_1 + 2x_2 - 4$

$\dfrac{\partial f}{\partial x_2} = 2x_1 + 6x_2 + 2$

Schritt 2 – Gradient zusammensetzen:

$\nabla f(\vec{x}) = \begin{pmatrix} 2x_1 + 2x_2 - 4 \\ 2x_1 + 6x_2 + 2 \end{pmatrix}$

Schritt 3 – Partielle Ableitungen zweiter Ordnung:

$\dfrac{\partial^2 f}{\partial x_1^2} = 2, \quad \dfrac{\partial^2 f}{\partial x_2^2} = 6, \quad \dfrac{\partial^2 f}{\partial x_1 \partial x_2} = \dfrac{\partial^2 f}{\partial x_2 \partial x_1} = 2$

Schritt 4 – Hesse-Matrix zusammensetzen:

$H = \begin{pmatrix} 2 & 2 \\ 2 & 6 \end{pmatrix}$

Ergebnis: $\nabla f = (2x_1+2x_2-4,\ 2x_1+6x_2+2)^T$, $H = \begin{pmatrix} 2 & 2 \\ 2 & 6 \end{pmatrix}$.

Aufgabe 3: Kritischen Punkt bestimmen

Aufgabe: Bestimme den kritischen Punkt (stationären Punkt) von $f$ aus Aufgabe 2, indem du $\nabla f = \vec{0}$ setzt.

Lösung

Schritt 1 – Gleichungssystem aufstellen:

(I) $2x_1 + 2x_2 - 4 = 0$

(II) $2x_1 + 6x_2 + 2 = 0$

Schritt 2 – Gleichung (I) nach $x_1$ auflösen:

$2x_1 + 2x_2 = 4 \Rightarrow x_1 + x_2 = 2 \Rightarrow x_1 = 2 - x_2$

Schritt 3 – In (II) einsetzen:

$2(2 - x_2) + 6x_2 + 2 = 0$

$4 - 2x_2 + 6x_2 + 2 = 0$

$6 + 4x_2 = 0 \Rightarrow x_2 = -1{,}5$

Schritt 4 – $x_1$ berechnen:

$x_1 = 2 - (-1{,}5) = 3{,}5$

Ergebnis: Kritischer Punkt bei $(x_1, x_2) = (3{,}5,\ -1{,}5)$.

Aufgabe 4: Konvexität via Eigenwerte der Hesse-Matrix

Aufgabe: Ist die Funktion $f$ aus Aufgabe 2 konvex? Nutze die Hesse-Matrix $H = \begin{pmatrix} 2 & 2 \\ 2 & 6 \end{pmatrix}$ und bestimme die Eigenwerte.

Lösung

Schritt 1 – Charakteristisches Polynom aufstellen:

$\det(H - \lambda E) = \det\begin{pmatrix} 2-\lambda & 2 \\ 2 & 6-\lambda \end{pmatrix} = (2-\lambda)(6-\lambda) - 4$

Schritt 2 – Ausmultiplizieren:

$(2-\lambda)(6-\lambda) - 4 = 12 - 2\lambda - 6\lambda + \lambda^2 - 4 = \lambda^2 - 8\lambda + 8$

Schritt 3 – Nullstellen mit p-q-Formel (bzw. Mitternachtsformel):

$\lambda = \dfrac{8 \pm \sqrt{64 - 32}}{2} = \dfrac{8 \pm \sqrt{32}}{2} = 4 \pm 2\sqrt{2}$

$\lambda_1 = 4 + 2\sqrt{2} \approx 6{,}83$

$\lambda_2 = 4 - 2\sqrt{2} \approx 1{,}17$

Schritt 4 – Interpretation: Beide Eigenwerte sind strikt positiv $\Rightarrow$ $H$ ist positiv definit $\Rightarrow$ $f$ ist strikt konvex.

Ergebnis: $f$ ist strikt konvex. Der kritische Punkt $(3{,}5,\ -1{,}5)$ ist daher ein globales Minimum.

Aufgabe 5: Gradientenverfahren – ein Iterationsschritt

Aufgabe: Gegeben sei $f(x_1, x_2) = -x_1^2 - x_2^2$ (Maximierung, Optimum bei $(0,0)$). Starte mit $\vec{x}^{(0)} = (2, 1)$ und führe einen Iterationsschritt mit fester Schrittweite $\mu = 0{,}3$ durch.

Lösung

Schritt 1 – Gradient allgemein:

$\nabla f = \begin{pmatrix} -2x_1 \\ -2x_2 \end{pmatrix}$

Schritt 2 – Gradient am Startpunkt $\vec{x}^{(0)} = (2, 1)$:

$\nabla f(2, 1) = \begin{pmatrix} -2 \cdot 2 \\ -2 \cdot 1 \end{pmatrix} = \begin{pmatrix} -4 \\ -2 \end{pmatrix}$

Schritt 3 – Iterationsvorschrift (Maximierung, Suchrichtung $+\nabla f$):

$\vec{x}^{(1)} = \vec{x}^{(0)} + \mu \cdot \nabla f(\vec{x}^{(0)})$

Schritt 4 – Einsetzen:

$\vec{x}^{(1)} = \begin{pmatrix} 2 \\ 1 \end{pmatrix} + 0{,}3 \cdot \begin{pmatrix} -4 \\ -2 \end{pmatrix} = \begin{pmatrix} 2 - 1{,}2 \\ 1 - 0{,}6 \end{pmatrix} = \begin{pmatrix} 0{,}8 \\ 0{,}4 \end{pmatrix}$

Schritt 5 – Kontrolle: $\|\vec{x}^{(1)}\| \approx 0{,}89 < \|\vec{x}^{(0)}\| \approx 2{,}24$ – wir haben uns dem Optimum $(0,0)$ genähert.

Ergebnis: $\vec{x}^{(1)} = (0{,}8,\ 0{,}4)$ – Annäherung an das Optimum.

Aufgabe 6: Lagrangefunktion aufstellen

Aufgabe: Maximiere $f(x_1, x_2) = x_1 \cdot x_2$ unter der Nebenbedingung $x_1 + x_2 \leq 10$ und $x_1, x_2 \geq 0$. Stelle die Lagrangefunktion auf.

Lösung

Schritt 1 – Nebenbedingung in Standardform $g_i(\vec{x}) \leq 0$ bringen:

$g_1(\vec{x}) = x_1 + x_2 - 10 \leq 0$

Schritt 2 – Allgemeine Lagrangefunktion:

$L(\vec{x}, \vec{u}) = f(\vec{x}) - \sum_{i=1}^m u_i \cdot g_i(\vec{x})$ mit $u_i \geq 0$.

Schritt 3 – Einsetzen:

$L(x_1, x_2, u_1) = x_1 \cdot x_2 - u_1 \cdot (x_1 + x_2 - 10)$

Ergebnis: $L = x_1 x_2 - u_1 (x_1 + x_2 - 10)$ mit $u_1 \geq 0$.

Aufgabe 7: Kuhn-Tucker-Bedingungen anwenden und lösen

Aufgabe: Löse das Problem aus Aufgabe 6 mit den Kuhn-Tucker-Bedingungen.

Lösung

Schritt 1 – Stationaritätsbedingungen:

$\dfrac{\partial L}{\partial x_1} = x_2 - u_1 \leq 0$

$\dfrac{\partial L}{\partial x_2} = x_1 - u_1 \leq 0$

Schritt 2 – Zulässigkeit und Multiplikatorvorzeichen:

$g_1 = x_1 + x_2 - 10 \leq 0, \quad u_1 \geq 0, \quad x_1, x_2 \geq 0$

Schritt 3 – Komplementärschlupf:

$u_1 \cdot (x_1 + x_2 - 10) = 0$ sowie $x_1 (x_2 - u_1) = 0$ und $x_2 (x_1 - u_1) = 0$

Schritt 4 – Fallanalyse (innere Lösung $x_1, x_2 > 0$):

Aus $x_1 > 0$ folgt $x_2 - u_1 = 0 \Rightarrow x_2 = u_1$.

Aus $x_2 > 0$ folgt $x_1 - u_1 = 0 \Rightarrow x_1 = u_1$.

Also $x_1 = x_2$.

Schritt 5 – Test, ob NB aktiv sein muss: Wäre $u_1 = 0$, dann $x_1 = x_2 = 0$ und $f = 0$. Aber $f(5,5) = 25 > 0$, also muss $u_1 > 0$ und wegen Komplementärschlupf gilt $x_1 + x_2 = 10$.

Schritt 6 – Einsetzen $x_1 = x_2$:

$2 x_1 = 10 \Rightarrow x_1 = x_2 = 5$ und $u_1 = x_1 = 5$.

Schritt 7 – Zielfunktionswert:

$f(5, 5) = 5 \cdot 5 = 25$

Ergebnis: Optimum bei $(x_1, x_2) = (5, 5)$ mit $u_1 = 5$ und $f^* = 25$.

Aufgabe 8: Eigenwerte einer 2x2-Matrix berechnen

Aufgabe: Berechne die Eigenwerte der Matrix $A = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}$ und beurteile die Definitheit.

Lösung

Schritt 1 – Charakteristisches Polynom aufstellen:

$\det(A - \lambda E) = \det\begin{pmatrix} 3-\lambda & 1 \\ 1 & 3-\lambda \end{pmatrix} = (3-\lambda)^2 - 1$

Schritt 2 – Nullstellen suchen:

$(3-\lambda)^2 - 1 = 0 \Rightarrow (3-\lambda)^2 = 1 \Rightarrow 3 - \lambda = \pm 1$

Schritt 3 – Zwei Fälle auflösen:

$3 - \lambda = 1 \Rightarrow \lambda_1 = 2$
$3 - \lambda = -1 \Rightarrow \lambda_2 = 4$

Schritt 4 – Interpretation: Beide Eigenwerte sind strikt positiv $\Rightarrow$ $A$ ist positiv definit.

Ergebnis: Eigenwerte $\lambda_1 = 2$ und $\lambda_2 = 4$, beide $> 0 \Rightarrow$ $A$ ist positiv definit.

Übungsfragen

Klick auf eine Frage, um die Musterantwort einzublenden.

1. Was ist der Gradient anschaulich – und was folgt daraus für Extrema?

Der Gradient $\nabla f$ ist der Vektor aller partiellen Ableitungen und zeigt vom betrachteten Punkt in die Richtung des steilsten Anstiegs der Funktion. Sein Betrag $|\nabla f|$ gibt an, wie stark der Anstieg dort ist. In einem lokalen Extremum (Minimum oder Maximum) ist die Funktion in jede Richtung "flach" – daher muss $\nabla f = \vec{0}$ sein. Das ist die notwendige Bedingung für ein Extremum bei $n>1$. Anschaulich: stellt man sich eine Berglandschaft vor, zeigt der Gradient überall bergauf; am Gipfel oder im Talboden gibt es keine Richtung mehr, in die es steiler ginge.

2. Wann ist eine Funktion konvex, und welche Rolle spielt die Hesse-Matrix?

Eine zweimal differenzierbare Funktion $f$ ist konvex, wenn ihre Hesse-Matrix an jeder Stelle positiv semi-definit ist. Gleichbedeutend: alle Eigenwerte der Hesse-Matrix sind nicht-negativ ($\lambda_i \geq 0$). Analog: $f$ ist konkav, wenn die Hesse negativ semi-definit ist (Eigenwerte $\leq 0$). Konvexität ist praktisch entscheidend, weil bei konvexen Optimierungsproblemen jedes lokale Minimum automatisch ein globales Minimum ist – man muss also keine Sorge haben, in einem "falschen Tal" zu landen.

3. Wozu dienen Lagrange-Multiplikatoren, und was bedeutet "Bestrafung" konkret?

Lagrange-Multiplikatoren $u_i \geq 0$ machen ein Problem mit Nebenbedingungen zu einem Problem ohne Nebenbedingungen, indem die NB in die Zielfunktion eingebaut werden: $L(\vec{x}, \vec{u}) = f(\vec{x}) - \sum u_i g_i(\vec{x})$. Wird eine NB verletzt ($g_i(\vec{x}) > 0$), zieht der Term $-u_i g_i$ den Wert der Lagrangefunktion herunter – die verletzende Lösung wird "bestraft" und damit für den Maximierer unattraktiv. Bei aktiver NB ($g_i = 0$) verschwindet der Term. Anschaulich: $u_i$ ist der Schattenpreis der Nebenbedingung – er misst, wie stark sich der Zielwert verbessern würde, wenn man die NB um eine Einheit lockerte.

4. Was besagt der Komplementärschlupf $u_i \cdot g_i(\vec{x}) = 0$?

Es dürfen niemals gleichzeitig $u_i > 0$ und $g_i(\vec{x}) < 0$ gelten – mindestens einer der beiden muss null sein. Zwei Fälle:

NB aktiv: $g_i(\vec{x}) = 0$ – die Lösung liegt auf dem Rand des zulässigen Bereichs. Der Multiplikator $u_i$ darf positiv sein und misst, wie "teuer" das Anliegen der NB ist.
NB inaktiv: $g_i(\vec{x}) < 0$ – der Rand ist nicht erreicht, es gibt "Luft" nach oben. Dann muss $u_i = 0$ sein, weil die NB gar nicht bindet.

Der Komplementärschlupf entspricht damit dem Prinzip: Nur bindende Restriktionen verdienen einen Preis.

5. Was besagt die Slater-Bedingung, und warum ist sie wichtig?

Die Slater-Bedingung verlangt, dass es mindestens einen Punkt im strikten Inneren des zulässigen Bereichs gibt, also einen Punkt $\vec{x}$ mit $g_i(\vec{x}) < 0$ für alle Nebenbedingungen. Sie ist eine Regularitätsbedingung, die garantiert, dass die Kuhn-Tucker-Theorie überhaupt anwendbar ist: Ohne sie kann es passieren, dass zwar ein Optimum existiert, aber keine gültigen Lagrange-Multiplikatoren $u_i$. Wichtig: Es reicht ein einziger innerer Punkt – das Optimum selbst darf durchaus auf dem Rand liegen.

6. Wie unterscheidet sich die Suche nach Extrema bei $n=1$ und $n>1$?

Strukturell sind beide Fälle gleich, nur werden im Mehrdimensionalen die Ableitungen durch Vektoren bzw. Matrizen ersetzt:

Schritt	$n=1$	$n>1$
Notwendige Bedingung	$f'(x)=0$	$\nabla f(\vec{x}) = \vec{0}$
Hinreichend (Min)	$f''(x) > 0$	Hesse positiv definit (alle EW $>0$)
Hinreichend (Max)	$f''(x) < 0$	Hesse negativ definit (alle EW $<0$)
Global	Randwerte betrachten	Sattelpunkte der Lagrangefunktion

Im Mehrdimensionalen kann zusätzlich der Fall Sattelpunkt auftreten (Hesse indefinit, gemischte Vorzeichen der Eigenwerte) – bei $n=1$ existiert das so nicht.

7. Was liefert das Gradientenverfahren – exakte Lösung oder Näherung? Wann wird abgebrochen?

Das Gradientenverfahren ist ein iteratives Näherungsverfahren. Es liefert grundsätzlich keine exakte, sondern eine approximative Lösung. Ausgehend von einer Startlösung wird in jeder Iteration ein Schritt in Richtung $+\nabla f$ (Maximierung) oder $-\nabla f$ (Minimierung) mit optimaler Schrittweite $\mu_{opt}$ gemacht. Abbruchkriterium: der Betrag des Gradienten unterschreitet eine vorgegebene Toleranz, d.h. $|\nabla f(\vec{x}^{(k)})| < \varepsilon$. Bei nicht-konvexen Zielfunktionen kann das Verfahren in einem lokalen Optimum stecken bleiben – das globale Optimum ist nicht garantiert.

8. Wie prüft man mit der Hesse-Matrix, ob ein stationärer Punkt Minimum, Maximum oder Sattelpunkt ist?

Ist $\nabla f(\vec{x}^*) = \vec{0}$, bestimmt man die Eigenwerte der Hesse-Matrix $H(\vec{x}^*)$ aus $\det(H - \lambda E) = 0$:

Alle Eigenwerte $> 0$ (positiv definit) $\Rightarrow$ lokales Minimum.
Alle Eigenwerte $< 0$ (negativ definit) $\Rightarrow$ lokales Maximum.
Gemischte Vorzeichen (indefinit) $\Rightarrow$ Sattelpunkt.
Alle Eigenwerte $\geq 0$ oder $\leq 0$ mit mindestens einem $= 0$ (semi-definit) $\Rightarrow$ Test versagt, höhere Ableitungen prüfen.

9. Was geschieht bei der Lagrangefunktion in einem Sattelpunkt?

Ein Sattelpunkt $(\vec{x}^*, \vec{u}^*)$ der Lagrangefunktion ist ein Punkt, an dem $L$ bezüglich $\vec{x}$ maximal und bezüglich $\vec{u}$ minimal ist. Das bedeutet: für jedes $\vec{u} \geq 0$ und jedes zulässige $\vec{x}$ gilt $L(\vec{x}, \vec{u}^*) \leq L(\vec{x}^*, \vec{u}^*) \leq L(\vec{x}^*, \vec{u})$. Das $\vec{x}^*$ ist dann ein Optimum des ursprünglichen Problems – bei konkaver Zielfunktion und konvexen NB sogar ein globales Maximum. Der Sattelpunkt vereint zwei gegenläufige Sichten: der Primaloptimierer will $f$ maximieren, der Dualoptimierer will die Bestrafung minimieren.

10. Warum reicht $\nabla f = \vec{0}$ nicht als hinreichende Bedingung?

$\nabla f = \vec{0}$ ist nur notwendig, d.h. jeder Extrempunkt erfüllt sie – aber nicht jeder Punkt, der sie erfüllt, ist ein Extremum. Beispiel: bei $f(x, y) = x^2 - y^2$ ist $\nabla f(0,0) = \vec{0}$, obwohl der Ursprung ein Sattelpunkt ist. Um zu entscheiden, welche Art von stationärem Punkt vorliegt, braucht man die zweite Ableitungsinformation – bei $n=1$ das Vorzeichen von $f''$, bei $n>1$ die Definitheit der Hesse-Matrix.

11. Wie interpretiert man die Werte der Lagrange-Multiplikatoren ökonomisch?

Die $u_i^*$ im Optimum sind Schattenpreise der Nebenbedingungen. Sie geben an, um wie viel sich der optimale Zielfunktionswert $f(\vec{x}^*)$ ändert, wenn die $i$-te Nebenbedingung um eine kleine Einheit gelockert wird. Ist $u_i = 0$, ist die NB inaktiv und ihr Lockern bringt keinen Nutzen. Ist $u_i > 0$, ist die NB bindend und ein Ausdehnen der Kapazität würde den Zielwert um exakt $u_i$ pro zusätzlicher Einheit erhöhen. Diese Interpretation kennt man ebenso aus der Dualitätstheorie der linearen Optimierung.

12. Was passiert, wenn die Zielfunktion nicht konvex/konkav ist?

Ohne Konvexität geht die schöne Eigenschaft "lokal = global" verloren. Konsequenzen:

Das Gradientenverfahren kann in einem lokalen Optimum stehen bleiben, das nicht das globale ist. Startpunkt-Wahl beeinflusst das Ergebnis.
Ein Sattelpunkt der Lagrangefunktion ist zwar notwendig, aber nicht mehr hinreichend für ein globales Optimum.
Man muss ggf. mehrere Startlösungen probieren oder globale Verfahren einsetzen (z.B. Multistart, stochastische Suche).

Deshalb ist die erste Prüfung immer: Ist mein Problem konvex/konkav?

13. Wie geht man bei einer Klausuraufgabe zur nichtlinearen Optimierung mit NB systematisch vor?

Empfohlener Schrittplan:

Zielfunktion $f$ und Nebenbedingungen $g_i(\vec{x}) \leq 0$ notieren; Slater prüfen (existiert innerer Punkt?).
Lagrangefunktion aufstellen: $L(\vec{x}, \vec{u}) = f(\vec{x}) - \sum u_i g_i(\vec{x})$.
Partielle Ableitungen $\partial L / \partial x_j$ und $\partial L / \partial u_i$ berechnen.
Kuhn-Tucker-Bedingungen aufschreiben (alle 6 Punkte, insbesondere Komplementärschlupf).
Fälle diskutieren (welche NB aktiv, welche inaktiv?) – Komplementärschlupf reduziert die Fälle.
Für jeden Fall die Gleichungen lösen und Kandidaten prüfen.
Zielfunktionswerte vergleichen, ökonomisch interpretieren (Schattenpreise).