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

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

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

\( \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*{Entartete Basislösungen}

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

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, \ 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.

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

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