\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)\)