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