Start optimization theory digest

1 files changed, 84 insertions, 0 deletions

diff --git a/content/optimierungstheorie.tex b/content/optimierungstheorie.tex
new file mode 100644
index 0000000..6255c41
--- /dev/null
+++ b/content/optimierungstheorie.tex
@@ -0,0 +1,84 @@
+\section*{Optimierungsprobleme}
+
+Sei \(f: M \to \R\). Ein Optimierungsproblem ist:
+
+\((P) \ \min_{x \in M} f(x)\)
+
+\((P)\) ist zulässig, wenn \(M \neq \emptyset\).
+
+\(\exists \hat x \in M \forall x \in M : f(\hat x) \leq f(x)\), so ist \((P)\) lösbar.
+
+\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}
+
+\subsection*{Lineare Programme}
+
+\((P) \ \min_{x \in M} f(x)\) ist linear, wenn:
+
+\(f: \R^n \to \R\) affin linear ist mit \(f(x)=c^T 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)^T \in \R^{(m+p) \times n}, b = (b_g \ b_u)^T \in \R^{m+p}\)
+
+\subsubsection*{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^T x\) mit \(M_N = \{ x \in \R_{\geq 0}^n | Ax=b \}\)
+
+\spacing
+
+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\) für \(i = 1,\dots,s\).
+
+\subsubsection*{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 \} :\)
+
+\( \sum_{j=1}^K \alpha_j = 1 \land x = \sum_{j=1}^K \alpha_j v^{(j)} + y \)