aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2018-07-04 12:49:00 +0200
committerAdrian Kummerlaender2018-07-04 12:49:00 +0200
commit776568ac50ac10801b2483f9c490131224b19e6b (patch)
treed4e0f306c60bbe1248329869f6c2cde918935951 /content
parent0a01db38d1f03417aae0f764bd1fb9124fa28ee6 (diff)
downloadmath_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.tar
math_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.tar.gz
math_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.tar.bz2
math_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.tar.lz
math_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.tar.xz
math_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.tar.zst
math_reference_sheets-776568ac50ac10801b2483f9c490131224b19e6b.zip
Expand section on convex optimization
Diffstat (limited to 'content')
-rw-r--r--content/optimierungstheorie.tex70
1 files changed, 70 insertions, 0 deletions
diff --git a/content/optimierungstheorie.tex b/content/optimierungstheorie.tex
index ec41d4c..9883ade 100644
--- a/content/optimierungstheorie.tex
+++ b/content/optimierungstheorie.tex
@@ -290,3 +290,73 @@ Sei \(M \subseteq R^n\) konvex und \(f : M \to \R\).
\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}.