\section*{Optimierungsprobleme}

Sei \(f: M \to \R\). Ein Optimierungsproblem ist:
\[(P) \ \min_{x \in M} f(x)\]

\((P)\) ist \emph{zulässig}, wenn \(M \neq \emptyset\).

\(x \in M\) ist zulässiger Punkt.

\(\exists \hat x \in M \forall x \in M : f(\hat x) \leq f(x)\), so ist \((P)\) lösbar.

Die Menge der Lösungen von \((P)\) ist:
\[\text{argmin}_{x \in M} f = \{ \hat x \in M | \forall x \in M : f(\hat x) \leq f(x) \}\]

\subsection*{Klassifizierung}

\begin{enumerate}[label=(\alph*)]
	\item Endlich dim. Probleme mit \(M \subseteq \R^m\)
	\item Lineare Probleme (vgl. LP)
	\item Konvexe Probleme
	\item Differenzierbare Probleme
\end{enumerate}

\section*{Lineare Programme}

\((P) \ \min_{x \in M} f(x)\) ist linear, wenn:

\(f: \R^n \to \R\) affin linear ist mit \(f(x)=c^\top x + c_0\) für \(c \in \R^n, c_0 \in \R\) und \(M\) folgende Darstellung besitzt:

\(M = \{ x \in \R^n | A_g x = b_g, A_u x \leq b_u \}\) mit \\ \(A = (A_g \ A_n)^\top \in \R^{(m+p) \times n}, b = (b_g \ b_u)^\top \in \R^{m+p}\)

\subsection*{Normalform}

Ein LP \((P_N)\) ist in Normalform gegeben, wenn \(A \in \R^{m \times n}, b \in \R^m\) und \(c \in \R^n\) ex. s.d. gilt:
\[(P_N) \ \min c^\top x \text{ mit } M_N = \{ x \in \R_{\geq 0}^n | Ax=b \}\]

Jedes LP \((P)\) besitzt Normalform \((P_N)\).

Dafür werden Ungleichungsbedingungen über \emph{Schlupfvariablen} umgeformt:
\[ A_u x \leq b_u \rightsquigarrow x_i^s = (b_u)_i - (A_u x)_i \text{ für } i = 1,\dots,s \]

\subsection*{Konvexe Mengen}

\(U \subseteq \R^n\) ist \emph{konvex}, wenn für \(x, y \in U \land \lambda \in [0,1] : (1-\lambda)x + \lambda y \in U\) gilt.

\spacing

\( v = \sum_{j=1}^m \lambda_j v^{(j)} \) mit \( \lambda_j \in [0,1] \land \sum_{j=1}^m \lambda_j = 1\) heißt \emph{Konvexkombination} von \( v^{(1)}, \dots, v^{(m)} \).

\spacing

\((M_N)\) der Normalform ist konvex.

\spacing

Schnitte endlich vieler Halbräume in \(R^n\) heißen \emph{Polyeder}, beschränkte Polyeder heißen \emph{Polytope}.

\spacing

\(M_n\) ist Polytop gdw. \( \not\exists y \in \R_{\geq 0}^n \setminus \{0\} : Ay = 0 \).

\subsubsection*{Charakterisierung von Ecken in \(M_N\)}

\(x \in M\) ist Ecke, wenn aus \(x=(1-\lambda) u+\lambda v\) mit \(u, v \in M, \lambda \in (0,1)\) folgt: \( u = v = x \).

Ecke ist nicht als echte Konvexkomb. darstellbar.

\spacing

\( x \in M_N \) ist Ecke von \(M_N\) gdw. die Spalten \(\{a_{*j}\}_{j \in J_x}\) mit \(J_x = \{ j \in \{1,\dots,n\} | x_j > 0 \}\) linear unabhg. sind.

\subsubsection*{Satz zur Existenz endl. vieler Ecken in \(M_N\)}

\[ M_N \neq \emptyset \implies \exists x \in M_N : x \text{ ist Ecke} \]

Insgesamt existieren endlich viele Ecken.

\subsubsection*{Konvexkombination von Ecken}

Seien \( v^{(k)} \in M_N \) mit \(k=1,\dots,K\) Ecken von \(M_N\).

Dann \( \forall x \in M_N \exists \alpha_j \in [0,1], y \in \{ y \in \R_{\geq 0}^n | Ay = 0 \} :\)
\[ \textstyle\sum_{j=1}^K \alpha_j = 1 \land x = \sum_{j=1}^K \alpha_j v^{(j)} + y \]

\subsection*{Existenz von linearen Programmen}

Sei \( (P_N) \ \min c^\top x \) auf \( M_N = \{ x \in \R_{\geq 0}^n | Ax = b \} \neq \emptyset\).

Dann gilt entweder \(\inf (P_N) = -\infty\) oder \((P_N)\) ist mit einer Ecke von \(M_N\) lösbar.

\section*{Simplex-Algorithmus}

\subsection*{Basislösung}

\(x \in \R^n\) ist Basislösung zu \(A_N x = b_N\), wenn es \(m\)-elementige Indexmenge \(J_x\) gibt mit linear unabhg. \(\{a_{*j} | j \in J_x\}\) und \(\forall j \notin J_x : x_j = 0\).

\spacing

\(x \in M_N\) Basislösung \(\iff x\) ist Ecke von \(M_N\)

\subsection*{Phase I}

Bestimme Basislösung \(z \in M_N\) und äquivalente Darstellung \((P)\) zu \((P_N)\):

\vspace*{-2mm}
\[ (P) \ \min c^\top x \text{ auf } M = \{ x \in \R_{\geq 0}^n | Ax=b \} \]

Mit Bedingungen:

\begin{enumerate}[label=(E\arabic*)]
	\item \(a_{*j} = e_{\ell_j}\) für \(j \in J_z\)
	\item \(c_j = 0\) für \(j \in J_z\)
	\item \(b \geq 0\)
	\item \(c^\top x = c_N^\top x - c_N^\top z\) d.h. \(c^\top z = 0\)
\end{enumerate}

\subsection*{Phase II}

Seien \(z, A, b, c\) aus Phase I gegeben.

Iterativ werden nun neue Basislösungen \(\tilde z\) und Darstellungen \(\tilde A x = \tilde b\) mit Bedingungen (E1)-(E4) bestimmt s.d.: \(c^\top \tilde z \leq c^\top z = 0\)

Diese Iteration bricht ab, wenn \(\tilde z\) Lösung zu \((P_N)\) ist oder \(\inf (P_N) = -\infty\) gilt.

\subsubsection*{Algorithmus zu Phase II}

\begin{enumerate}[label=(\arabic*)]
	\item \(c \geq 0? \rightsquigarrow\) Abbruch denn \(z\) ist Lösung zu \((P)\) mit \(c^\top z = \eta - c_N^\top z = 0\)
	\item Wähle Pivotindex \(s \in \{1,\dots,n\}\) mit \(c_s < 0\)
	\item \(a_{*s} \leq 0? \rightsquigarrow\) Abbruch mit \(\inf (P) = -\infty\)
	\item Wähle \(r \in \{1,\dots,m\}\) s.d. Pivotelement \(a_{rs}\) mit \(\frac{b_r}{a_{rs}} = \min \left\{ \frac{b_i}{a_{is}} \middle| i \in \{1,\dots,n\} \text{ mit } a_{is} > 0 \right\}\) die Bedingung \(a_{rs} > 0\) erfüllt
	\item Gauß-Transformation zu \(\tilde A x = \tilde b\) s.d. \(r\)-ter Einheitsvektor in \(\tilde A\) in der \(s\)-ten Spalte steht
	\item Ersetze \((P)\) mit \((\tilde P)\) und wiederhole ab (1)
\end{enumerate}

\subsection*{Durchführbarkeit des Simplex-Verfahren}

Sei \((P)\) mit \(A,b,c\) und Basislsg. \(z \in M\) aus Phase I und \((\tilde P)\)  durch Phase II Schritt erzeugt. Dann:

\begin{enumerate}[label=(\alph*)]
	\item \(c \geq 0 \implies z\) ist optimal
	\item \(c_s < 0 \land a_{*s} \leq 0 \implies \inf (P) = -\infty\)
	\item \((P)\) und \((\tilde P)\) sind äquiv. mit \(\tilde c^\top x = c^\top x - c^\top \tilde z\) für \(x \in M\)
	\item \(c^\top \tilde z \leq c^\top z = 0\)
	\item \((\tilde P)\) mit Basislösung \(\tilde z\) erfüllt (E1)-(E4)
\end{enumerate}

\subsubsection*{Bestimmung von Basislösung in Phase I}

Definiere Hilfsproblem \((H) \ \min e^\top (b-Ax)\) auf \(M_H = \{ x \in \R_{\geq 0}^n | A_N x \leq b_N \}\) wobei \(e = 1 \in \R^n\).

Für das Hilfsproblem \((H)\) gelten:

\begin{enumerate}[label=(\alph*)]
	\item wg. \(b_N \geq 0 \implies 0 \in M_H\) ist \((H)\) zulässig
	\item \(x \in M_H \implies e^\top (b_N - A_N x) \geq 0\) \\ d.h. \((H)\) hat immer Lösung, \(\inf \ (H) > -\infty\)
	\item Mit Schlupfvariablen lässt sich Phase II auf \((H)\) direkt anwenden
\end{enumerate}

Ist \(\hat z \in M_H\) optimale Basislösung zu \((H)\) so gelten:

\begin{enumerate}[label=(\alph*)]
	\item \(e^\top (b_N - A_N \hat z) = 0 \implies \hat z\) ist zulässig zu \((P_N)\)
	\item \(e^\top (b_N - A_N x) \geq e^\top (b_N - A_N \hat z) > 0 \\ \implies M_N \neq \emptyset\) und \((P_N)\) ist nicht zulässig
\end{enumerate}

\subsubsection*{Entartete Basislösungen}

Sei \(z \in M\) eine Basislösung.

\(z \in M\) ist \emph{nicht entartet}, wenn \(z_j > 0\) für \(j \in J_z\) gilt.

\spacing

Im Simplex-Tableau ist \(z\) nicht entartet gdw. \(b_i > 0\) für \(i=1,\dots,m\) gilt.

Für entartete \(z \in M\) ist das Simplex-Verfahren i.A. nicht zyklenfrei.

\subsubsection*{Regel von Bland}

Sei \(s := \min \{ j \in \{1,\dots,n\} | c_j < 0 \}\) die Pivotspalte und \(r\) die Pivotzeile s.d. gilt:
\[\frac{b_r}{a_{rs}} = \min \left\{ \frac{b_i}{a_{is}} \middle| a_{is} > 0 \text{ für } i=1,\dots,m \right\}\]

Wird das Minimum für mehrere Zeilen angenommen, so wähle die Pivotzeile \(r\) s.d. \(j_r < j_k\) gilt. d.h. der \(r\)-te Einheitsvektor steht am weitestens links.

\spacing

Phase II mit Regel von Bland stoppt immer im Optimum zu \((P)\) insofern ein solches existiert.


\section*{Dualitätstheorie}

Sei \((P_N) \ \min_{x \in M} c^\top x\) auf \(M = \{ x \in \R_{\geq 0}^n | Ax=b \}\) mit \(A \in \R^{m \times n}, b \in \R^m\) und \(c \in \R^n\).

Dann gilt für Lösung \(\hat x \in M\) von \((P_N)\):
\[\exists \hat y \in N = \{ y \in \R^m | A^\top y \leq c \} \text{ mit } b^\top \hat y = c^\top \hat x\]

\subsection*{Duales Optimierungsproblem}

Zu \emph{primalem} LP in Normalform \((P_N)\) ist das duale Optimierungsproblem \((D)\) gegeben durch:
\[(D) \ \max_{y \in N} b^\top y \text{ auf } N = \{y \in \R^m | A^\top y \leq c\}\]

\subsection*{Schwacher Dualitätssatz}

Für zulässige \((P_N)\) und \((D)\) gelten:

\begin{enumerate}[label=(\alph*)]
	\item \(\forall x \in M, y \in N : b^\top y \leq c^\top x\)
	\item \((P_N)\) und \((D)\) sind lösbar
	\item \(\hat x \in M \land \hat y \in N \land b^\top \hat y = c^\top \hat x \\ \implies \hat x\) löst \((P_N)\) und \(\hat y\) löst \((D)\)
\end{enumerate}

\subsection*{Satz von Kuhn-Tucker}

\[\hat x \in M \text{ löst } (P_N) \iff \exists \hat y \in N : b^\top \hat y = c^\top \hat x\]

\subsection*{Starker Dualitätssatz}

Für \((P_N)\) und duales \((D)\) gelten:

\begin{enumerate}[label=(\alph*)]
	\item \((P_N)\), \((D)\) zulässig \(\implies (P_N)\), \((D)\) lösbar und \[\min (P_N) = \max (D)\]
	\item \((P_N)\) zulässig, \((D)\) nicht \(\implies \inf (P) = -\infty\)
	\item \((D)\) zulässig, \((P_N)\) nicht \(\implies \sup (D) = \infty\)
\end{enumerate}

\subsection*{Komplementaritäts-Bedingung}

\(\hat x \in M, \hat y \in N\) sind optimal zu \((P_N)\) bzw. \((D)\) gdw.:
\[\hat x^\top (c-A^\top \hat y) = 0\]

d.h. \(\forall j = 1,\dots,n : \hat x_j = 0 \lor c_j = (A^\top \hat y)_j\)

\subsection*{Farkas-Lemma}

Seien \(A \in \R^{m \times n}\) und \(b \in \R^m\). Dann:
\begin{align*}
&\exists x \in \R_{\geq 0}^n &&: Ax=b \\
\iff &\not\exists y \in \R^m &&: A^\top y \leq 0 \land b^\top y > 0
\end{align*}

\section*{Konvexe Optimierung}

Die \emph{konvexe Hülle} von \(M \subseteq \R^n\) ist definiert als:
\[\text{conv}(M) = \left\{ \sum_{i=1}^m \lambda_i x^{(i)} \middle| x^{(i)} \in M, \lambda_i \geq 0, \sum_{i=1}^m \lambda_i = 1 \right\}\]

\(M \subseteq \R^n\) ist \emph{Kegel}, wenn \(x \in M \land \lambda \geq 0 \implies \lambda x \in M\).

Die \emph{konvexe Kegelhülle} von \(M \subseteq \R^n\) ist def. als:
\[\text{cone}(M) = \left\{ \sum_{i=1}^m \lambda_i x^{(i)} \middle| x^{(i)} \in M, \lambda_i \geq 0 \right\}\]

\[M \subseteq \R^n \text{ ist konvex} \iff \sum_{i=1}^m \lambda_i x^{(i)} \in M\]

\subsection*{Projektionssatz}

Sei \(M \subseteq \R^n\) nichtleer, abg. und konvex. Dann: \[\forall x \in \R^n \exists! \hat x \in M \forall y \in M: \|\hat x - x\| \leq \|y - x\|\]

Ein \(\hat x \in M\) ist dieser \emph{Projektionspunkt} gdw.: \[\forall y \in M : (x-\hat x)^\top (y-\hat x) \leq 0\]

\subsection*{Trennungssatz}

Seien \(M \subseteq \R^n\) nichtleer, abg. und konvex sowie \(x \in \R^n \setminus M\). Dann ex. \(x\) und \(M\) strikt trennende Hyperebene: \[\exists a \in \R^n \setminus \{0\}, \gamma \in \R \forall y \in M : a^\top y \leq \gamma < a^\top x\]

Ist \(M\) Kegel, so kann \(\gamma = 0\) gesetzt werden.

\subsection*{Satz von Caratheodory}

\(M \subseteq \R^n \land x \in \text{cone}(M) \setminus \{0\} \\ \implies \exists m \leq n \text{ linear unabhg. } v^{(j)} \in M \text{ und } \lambda_j \geq 0 : \\ \phantom{\implies} x = \sum_{j=1}^m \lambda_j v^{(j)}\)

\spacing

\(M \subseteq \R^n \land x \in \text{conv}(M) \\ \implies \exists m \leq n+1 \ v^{(j)} \in M \text{ s.d. } \\ \phantom{\implies} \{v^{(2)} - v^{(1)},\dots,v^{(m)}-v^{(1)}\} \text{ linear unabhg. und} \\ \phantom{\implies} \lambda_j \in [0,1] \text{ mit } x = \sum_{j=1}^m \lambda_j v^{(j)} \land \sum_{j=1}^m \lambda_j = 1\)

\subsection*{Simplex}

Die konvexe Hülle \(S = \text{conv}\{v^{(j)} | j=1,\dots,m\}\) ist ein \emph{Simplex}, wenn \(\{v^{(2)} - v^{(1)},\dots,v^{(m)}-v^{(1)}\}\) linear unabhängig sind. Ein \emph{simplizialer Kegel} ist die konvexe Kegelhülle linear unabhg. Vektoren.

\subsection*{Konvexe Funktionen}

Sei \(M \subseteq R^n\) konvex und \(f : M \to \R\).

\spacing

\(f\) ist \emph{konvex}, wenn: \(\forall x, y \in M, \lambda \in [0,1] : \\ f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)\)

\spacing

\(f\) ist \emph{strikt konvex}, wenn: \(\forall x \neq y \in M, \lambda \in (0,1) : \\ f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda)f(y)\)

\spacing

\(f\) ist \emph{glm. konvex}, wenn \(\exists k > 0 \forall x, y \in M, \lambda \in [0,1] : \\ \hspace*{3mm} f(\lambda x + (1-\lambda)y) + k\lambda(1-\lambda)\|x-y\|^2 \\ \leq \lambda f(x) + (1-\lambda)f(y)\)

Glm. konvexe Funktionen sind strikt konvex.

\spacing

Der \emph{Epigraph} von \(f : M \to \R\) ist definiert als: \[E(f) = \{(x,\alpha) \in M \times \R | f(x) \leq \alpha\} \subseteq \R^{n+1}\]

\(f\) ist (strikt) konvex gdw. \(E(f)\) (strikt) konvex ist.

\subsubsection*{Jensensche Ungleichung}

Für Konvexkombination \(x = \sum_{i=1}^m \lambda_i v^i\) von \(v^i \in M\) mit \(\lambda_i \in [0,1]\) und \(\sum_{i=1}^m \lambda_i = 1\) zusammen mit konvexer Funktion \(f: M \to \R\) gilt: \[f(x) \leq \sum_{i=1}^m \lambda_i f(v^i)\]

\subsubsection*{Stetigkeitskriterium}

Sei \(f : M \to \R\) konvex, \(M \subseteq \R^n\) offen und konvex.

Dann ist \(f\) stetig.

\subsubsection*{Konvexheitskriterien}

Sei \(M \subseteq \R^n\) offen und konvex sowie \(f \in C^2(M,\R)\).

Gleichmäßige Konvexität von \(f\) ist äquivalent zu:

\begin{enumerate}[label=(\alph*)]
\item \(\exists c > 0 \forall x, y \in M : \\ f(y)-f(x) \geq \nabla f(x)(y-x) + c\|y-x\|^2\)
\item \(\exists c > 0 \forall x, y \in M : \\ (\nabla f(y) - \nabla f(x))^\top (y-x) \geq c\|y-x\|^2\)
\item \(\exists c > 0 \forall x \in M, z \in \R^n : z^\top \nabla^2 f(x)z \geq c\|z\|^2\)
\end{enumerate}

Strikte Konvexität von \(f\) ist äquivalent zu:

\begin{enumerate}[label=(\alph*)]
\item \(\forall x, y \in M : f(y)-f(x) > \nabla f(x)(y-x)\)
\item \(\forall x, y \in M : (\nabla f(y) - \nabla f(x))^\top (y-x) > 0\)
\item \(\forall x \in M, z \in \R^n \setminus \{0\} : z^\top \nabla^2 f(x)z > 0\)
\end{enumerate}

Konvexität von \(f\) ist äquivalent zu:

\begin{enumerate}[label=(\alph*)]
\item \(\forall x, y \in M : f(y)-f(x) \geq \nabla f(x)(y-x)\)
\item \(\forall x, y \in M : (\nabla f(y) - \nabla f(x))^\top (y-x) \geq 0\)
\item \(\forall x \in M, z \in \R^n : z^\top \nabla^2 f(x)z \geq 0\)
\end{enumerate}

\subsection*{Konvexe Optimierungsaufgaben}

Problem \((P) \ \min_{x \in M} f(x)\) auf \(M \subseteq \R^n\) ist \emph{konvex}, wenn \(M\) und \(f\) konvex sind.

\spacing

Hier sind lokale Minima auch globale Minima.

\subsubsection*{Eindeutigkeit}

Sei \(M \subseteq \R^n\) konvex und \(f : M \to \R\) strikt konvex. Dann hat \((P)\) höchstens eine Lösung.

\spacing

Sei \(M\) nichtleer, abg. und konvex sowie \(f\) glm. konvex und stg. Dann hat \((P)\) genau eine Lösung.

\subsubsection*{Konvexes Optimierungsproblem}

Sei \(f : \R^n \to \R\) konvex und \(M\) gegeben als: \[M = \{x \in \R^n | h(x) \leq 0 \land Ax=b\}\]

für \(A \in \R^{m \times n}, b \in \R^m\) und konvexe \(h_j : \R^n \to \R\).

Dann ist \((P)\) ein \emph{konvexes Optimierungsproblem}.

\spacing

\(\Lambda = \{(f(x)+r, h(x)+z, Ax-b) \in \R \times \R^p \times \R^m \\ \phantom{\Delta = \{}| r, z \geq 0, x \in \R^n \}\)

\(\Lambda\) ist konvexe Menge zu gegebenem \((P)\).

\subsubsection*{Existenz von Lösung}

Sei \(M \neq \emptyset, \ \inf(P) > -\infty\) und \(\Lambda\) abgeschlossen.

Dann besitzt konvexes \((P)\) eine Lösung.

\subsubsection*{Satz von Weyl}

Alle endlich erzeugten konvexen Kegel \(K \in \R^n\) sind polyedral und besitzen Darstellung: \[K = \{x \in \R^n | Bx \leq 0\} \text{ mit } B \in \R^{q \times n}\]

\subsubsection*{Dualität konvexer Probleme}

Konvexes \((P)\) mit \(\Lambda\) hat äquivalentes Problem \((P')\)
\[(P') \ \min \gamma \text{ mit } (\gamma,u,v) \in \Lambda \cap (\R \times \{0\} \times \{0\}) \subseteq \R^{1+p+m}\]

\subsubsection*{Lagrange Funktion}

\[L(x,u,v) = f(x) + u^\top h(x) + v^\top (Ax-b)\]

\subsubsection*{Duales Problem}

Sei \(F : \R_{\geq 0}^p \times \R^m \to \R, \ (u,v) \mapsto \inf_{x \in \R} L(x,u,v)\)

\[(D) \ \max_{(u,v) \in N} F(u,v) \text{ auf } N\]

Wobei \(N =\{(u,v) \in \R_{\geq 0}^p \times \R^m | F(u,v) > -\infty\}\)

\subsubsection*{Schwacher Dualitätssatz}

Seien konvexe \((P)\) und \((D)\) gegeben. Dann:
\[\forall x \in M, (u,v) \in N : f(x) \geq F(u,v)\]

Sei \(\hat x \in M, (\hat u, \hat v) \in N\) s.d. \(f(\hat x) = F(\hat u, \hat v)\) dann löst \(\hat x\) \((P)\) und \((\hat u, \hat v)\) ist Maximalstelle von \((D)\).

\subsubsection*{Sattelpunktsatz}

Sei \((P)\) konvexes Problem mit dualem \((D)\).

\(\hat x \in M, (\hat u, \hat v) \in N\) sind optimal zu \((P)\) bzw. \((D)\) mit \(f(\hat x) = F(\hat u, \hat v)\) gdw. \((\hat x, \hat u, \hat v) \in M \times N\) Sattelpunkt der Lagrange-Funktion ist.

d.h: \(\forall x \in \R^n, u \in \R_{\geq 0}^p, v \in \R^m :\) \[L(\hat x,u,v) \leq L(\hat x,\hat u,\hat v) \leq L(x,\hat u,\hat v)\]

\subsubsection*{Slater-Bedingung}

Zulässige Menge \(M = \{x \in \R^n | h(x) \leq 0, Ax=b\}\) erfüllt \emph{Slater-Bedingung (SB)}, wenn:

\begin{enumerate}[label=(\roman*)]
	\item \(\text{Rg}(A) = m \leq n\) maximal
	\item \(\tilde x \in M\) ex. mit \(h(\tilde x) < 0\)
\end{enumerate}

\subsubsection*{Starker Dualitätssatz}

Sei \((P)\) konvexes Problem mit dualem \((D)\) und \(M\) erfülle (SB). Ist \((P)\) lösbar mit \(\hat x \in M\) dann:
\[\exists \text{Lösung } (\hat u,\hat v) \in N \text{ von } (D) : f(\hat x) = F(\hat u,\hat v)\]

\subsubsection*{Konvexer Kuhn-Tucker}

Sei \((P)\) konvexes Problem mit dualem \((D)\) und \(M\) erfülle (SB).
\(\hat x \in M\) ist Lösung von (P) gdw. \(\exists (\hat u,\hat v) \in N : f(\hat x) = F(\hat u,\hat v)\)

\subsubsection*{Komplementaritäts-Bedingung}

Für \(\hat x, (\hat u,\hat v)\) des konvexen Kuhn-Tucker gilt die \emph{Komplementaritätsbedingung}: \(\hat u^\top h(\hat x) = 0\)

\section*{Differenzierbare Optimierung}

\[(P) \ \min f \text{ auf } M = \{ x \in \R^n | h(x) \leq 0, g(x)=0\}\]

\(f \in C^1(\R^n,\R), h \in C^1(\R^n,\R^n), g \in C^1(\R^n,\R^m)\).

\subsection*{Lagrangesche Multiplikatorenregel}

Ziel: Linearisierung und Anw. von Kuhn-Tucker.

Mit \((\nabla f(x))^\top = f'(x) \in \R^{1 \times n}, f'(x) \in \R^{m \times n}\) und \(h'(x) \in \R^{p \times n}\) sind Linearisierungen gegeben:
\begin{align*}
f(x+z) &= f(x) + f'(x)z + o(\|z\|) \\
g(x+z) &= g(x) + g'(x)z + o(\|z\|) \\
h(x+z) &= h(x) + h'(x)z + o(\|z\|)
\end{align*}

Linearisierung von \((P)\): \[(LP) \ \min f'(x)z\]

auf \(M_L = \{ z \in \R^n | h(x) + h'(x)z \leq 0, g'(x)z = 0 \}\)

\subsubsection*{Zulässige Abstiegsrichtung}

Sei \(M \in \R^n\) und \(f : M \to \R\) dann ist \(z \in \R^n\) \emph{zulässige Abstiegsrichtung} zu \(f\) in \(x \in M\), wenn \(\exists \epsilon > 0 \forall t \in (0,\epsilon) : x + tz \in M \land f(x+tz) < f(x)\).

\subsubsection*{Kegel}

Sei \(M = \{x \in \R^n | h(x) \leq 0\}\) mit \(h \in C^1(\R^n,\R^p)\).

\(T(x,M) := \{ z \in \R^n | \exists t_k \geq 0, z^{(k)} \in \R^n : t_k \to 0, z^{(k)} \to z \ (k \to \infty), \forall k \in \N : x+t_k z^{(k)} \in M\}\)
