%% LyX 1.2 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[german]{article} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{a4wide} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \usepackage{amsmath} \usepackage{amssymb} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. \providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \newenvironment{lyxlist}[1] {\begin{list}{} {\settowidth{\labelwidth}{#1} \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep} \renewcommand{\makelabel}[1]{##1\hfil}}} {\end{list}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\C}{\mathbb{C}} \usepackage{babel} \makeatother \begin{document} \title{Ausgewählte Kapitel der mathematischen Optimierung} \author{Mitschrift zur Vorlesung von Prof. Guddat im WS 2001/2002} \maketitle \tableofcontents{} \pagebreak \setcounter{section}{1} \section{Elementare Polyedertheorie und lineare Optimierung \cite{1}} \subsection{Das Lineare Optimierungsproblem und seine geometrische Interpretation} \begin{description} \item [Def.:]$\mathrm{E}_{p}^{k}:=\left\{ \left.x\in \R ^{n}\right|x=p+W^{k}\right\} ,\, W^{k}$ ist ein beliebiger linearer Unterraum im $\R ^{n}.$ $\mathrm{E}^{n-1}\left(\alpha \right)=\left\{ \left.x\in \R ^{n}\right|c^{T}x=\alpha \right\} ,\, c\neq 0,\, \alpha \in \R .$ \item [Lemma~2.1:]~ \begin{enumerate} \item $\left\{ \left.\mathrm{E}^{n-1}\left(\alpha \right)\right|\alpha \in \R \right\} $ ist eine Schar paralleler Hyperebenen, die den ganzen $\R ^{n}$ überdecken. \item Der Vektor $c$ steht senkrecht auf jeder Hyperebene. \item Der Wert der Zielfunktion $c^{T}x$ wächst streng monoton in Richtung des Vektors $c$ und fällt streng monoton in Richtung $-c$. \end{enumerate} \begin{description} \item [Bew.:]~ \begin{enumerate} \item Sei $\alpha \in \R $ bel. fest. Dann ist $\mathrm{E}^{n-1}\left(\alpha \right)$ eine Hyperebene (Lsg.menge des inhom. Gl.sys. $c^{T}x=\alpha $). $c^{T}x=\alpha $ ist wegen $c\neq 0$ ein affiner Unterraum der Dimension $n-1,$ da der Rang der Koeffizientenmatrix $1$ ist. Wir betrachten $p^{1},p^{2}\in \R ^{n}$ beliebig fest und berechnen $\alpha _{1}:=c^{T}p^{1},\, \alpha _{2}:=c^{T}p^{2}.$\\ $\rightarrow \, \mathrm{E}^{n-1}\left(\alpha _{1}\right),\mathrm{E}^{n-1}\left(\alpha _{2}\right)$ sind Hyperebenen und es gilt: \begin{eqnarray*} \mathrm{E}^{n-1}\left(\alpha _{i}\right) & = & \left\{ \left.x\in \R ^{n}\right|x=p^{i}+W^{n-1}\right\} ,i=1,2\\ W^{n-1} & = & \left\{ \left.x\in \R ^{n}\right|c^{T}x=0\right\} \end{eqnarray*} \item $\mathrm{E}^{n-1}\left(\alpha _{1}\right)=\left\{ \left.x\in \R ^{n}\right|c^{T}x=c^{T}p^{1}\right\} =\left\{ \left.x\in \R ^{n}\right|c^{T}\left(x-p^{1}\right)=0\right\} \, \rightarrow \, c\bot x-p^{1}.$ \item $L:=\left\{ \left.x\in \R ^{n}\right|x=p^{1}+t\cdot c,\, t\in \R \right\} .$ Dann gilt: \begin{enumerate} \item $L\, \bot \, \mathrm{E}^{n-1}\left(\alpha \right)$ \item $\forall x\in L:\, c^{T}x=x^{T}p^{1}+t\cdot \underbrace{c^{T}c}_{>0}\, \rightarrow \, c^{T}p^{1}+t_{1}c^{T}c\, <\, c^{T}p^{1}+t_{2}c^{T}c,$ falls $t_{1}k\right\} $]heißt pos. Halbraum zur Hyperebene. \end{description} $\bar{H}^{+}=\left\{ \left.x\in \R ^{n}\right|a^{T}x\geq k\right\} $ heißt pos. abg. Halbraum zur Hyperebene. $H^{-},\bar{H}^{-}$ analog $\left(<,\leq \right)$. \item [Lemma~2.3:]~ \begin{enumerate} \item $H^{+}\cup H^{-}\cup A=\R ^{n},\, H^{+}\cap H^{-}=\emptyset $ (man sagt: $H^{+},H^{-},A$ bilden eine Zerlegung des $\R ^{n}$) \item $H^{+},H^{-}$ sind konvex. \item $H^{+},H^{-}$ sind offen. \item $\bar{H}^{+},\bar{H}^{-}$ sind abgeschlossen. \item $\dim H^{+}=\dim H^{-}=n.$ \end{enumerate} \item [Def.~2.6:]Der Durschnitt von endlich vielen abgeschlossenen Halbräumen heißt konvexer Polyeder. \item [Def.~2.7:]Es seien $x^{1},\ldots ,x^{N}\in \R ^{n}.$ Dann heißt \[ x=\sum _{i=1}^{N}\lambda _{i}x^{i},\, \lambda _{i}\geq 0,\, i=1,\ldots ,N,\, \sum _{i=1}^{N}\lambda _{i}=1\] für festgewählte $\lambda _{i},i=1,\ldots ,N$ eine Konvexkombination der Punkte $x^{1},\ldots ,x^{N}.$ \item [Vermutung~I:]Jedes beschränkte konvexe Polyeder P der $\dim P\geq 1$ hat endlich viele {}``Ecken'' $x^{1},\ldots ,x^{N}$ und läßt sich als Menge aller Konvexkombinationen seiner Ecken darstellen, d.h. \[ P=\left\{ x\in \R ^{n}\left|x=\sum _{i=1}^{N}\lambda _{i}x^{i},\, \lambda _{i}\geq 0,\, \sum _{i=1}^{N}\lambda _{i}=1\right.\right\} \] \item [Def.~2.5.:]Sei $M=\left\{ x\in \R ^{n}\left|\sum _{\alpha =1}^{n}a_{r\alpha }x_{\alpha }\leq b_{r},r=1,\ldots ,m,\, \tilde{A}x=b\right.\right\} .$ \[ S_{I}:=\left\{ x\in M\left|\sum _{\alpha =1}^{n}a_{r\alpha }=b_{r},r\in I\right.\right\} ,\, \textrm{I}\subseteq \left\{ 1,\ldots ,m\right\} .\] \begin{enumerate} \item Wenn $S_{I}\neq \emptyset $ und $S_{I}\neq M,$ so heißt $S_{I}$ abgeschlossene Seite des konvexen Polyeders $M.$ \item Wenn $\dim S_{I}=1,$ so heißt $S_{I}$ Kante. \item Wenn $\dim S_{I}=0,$ so heißt $S_{I}$ Ecke. \end{enumerate} \item [Bem.~2.5:]Andere Defintion von Ecken und Seiten: \cite{2} \item [Def.~2.6:]~ \begin{enumerate} \item Eine Hyperebene $\mathrm{E}\left(\hat{\alpha }\right)$ heißt Berührungsebene an das Polyeder $M,$ wenn $\mathrm{E}\left(\hat{\alpha }\right)\cap \partial M\neq \emptyset $ und $\mathrm{E}\left(\hat{\alpha }\right)\cap \textrm{relint}M=\emptyset .$ \item $\hat{x}\in \mathrm{E}\left(\hat{\alpha }\right)\cap M$ heißt Berührungspunkt der Hyperebene $\mathrm{E}\left(\hat{\alpha }\right)$ an den Polyeder $M.$ \end{enumerate} \item [Vermutung~II:]Sei \[ M_{opt}:=\left\{ \left.\hat{x}\in M\right|c^{T}\hat{x}\geq c^{T}x\, \forall x\in M\right\} \] Opt.menge für $\left(\textrm{LOP}\right)_{\max }.$ Dann ist $M_{opt}$ leer, $M$ oder eine abgeschlossene Seite von $M:$ \begin{enumerate} \item $M_{opt}=\emptyset :\, M=\emptyset $ oder $c^{T}x$ ist auf $M$ nach oben unbeschränkt, d.h. \begin{eqnarray*} \exists \left\{ \left.x\in \R ^{n}\right|x=x^{0}+t\cdot c,t\geq 0\right\} & \subseteq & M\\ \textrm{und }\lim _{t\rightarrow \infty }c^{T}\left(x^{0}+tc\right) & = & +\infty \end{eqnarray*} \item $M_{opt}=M$ \item $M_{opt}$ ist eine abgeschlossene Seite von $M.$ \end{enumerate} \item [Vermutung~III:]Wenn $M$ Ecken besitzt und $M_{opt}\neq \emptyset ,$ dann wird das Maximum von $c^{T}x$ bzgl. $M$ immer in einer Ecke angenommen. \item [Vermutung~IV:]Jeder lokale Optimalpunkt ist globaler Optimalpunkt. \item [Vermutung~V:]Geometrische Idee der Simplexmethode: \begin{itemize} \item Start mit einer bekannten bzw. zu konstruierenden Ecke $x^{0}\in M.$ \item Übergang zu einer benachbarten Ecke mit größer werdenden Zielfunktionswert. \end{itemize} \item [Def.~2.7:]Es seien $C=\left\{ x^{0},\ldots ,x^{d}\right\} \subseteq \R ^{n}$ affin unabhängig. Dann heißt die konvexe Hülle \[ \textrm{conv}C:=\left\{ \left.x\in \R ^{n}\right|x=\sum _{i=0}^{d}\lambda _{i}x^{i},\, \lambda _{i}\geq 0\, \forall i,\, \sum _{i=0}^{d}\lambda _{i}=1\right\} \] $d$-dimensionales Simplex. \item [Satz~2.1:]Es sei $M$ ein konvexes Polyeder. $M$ hat einen $d$-dimensionalen affinen Unterraum mit $0\leq d<\dim M$ als Seite, gdw. $M$ eine Seite der Dimension $d$ aber keine Seite einer kleineren Dimension besitzt. \begin{description} \item [Bew.:]\cite{1} \end{description} \item [Cor.~2.1:]$M$ hat eine Gerade als Seite, gdw. $M$ eine Kante aber keine Ecke besitzt. \end{description} \subsection{Darstellungssätze} \begin{description} \item [Satz~2.2~(Vermutung~I):]Jedes beschränkte konvexe Polyeder $M$ mit $\dim M\geq 1$ läßt sich als Konvexkombination seiner (endl. vielen) {}``Ecken'' $x^{1},\ldots ,x^{N}$ darstellen: \[ M=\left\{ x\in \R ^{n}\left|x=\sum _{i=1}^{N}\lambda _{i}x^{i},\, \lambda _{i}\geq 0,i=1,\ldots N,\, \sum _{i=1}^{N}\lambda _{i}=1\right.\right\} \] \begin{description} \item [Bew.:]$M$ hat mind. eine Ecke. Andernfalls würde nach Satz 2.1 $M$ eine Gerade enthalten. (Wid. zu $M$ beschränkt). $M$ hat endlich viele Ecken, da $M$ nur endlich viele Seiten besitzt. Vollständige Induktion über $k=\dim M:$ IA: $k=1\, \Rightarrow \, M=\left[x^{1},x^{2}\right]$ Verbindungsstrecke. IS: IV: Aussage sei $\forall $ Polyeder der Dim. $\leq k$ richtig. IBew.: Sei $M$ ein beschränkter Polyeder mit $\dim =k+1,\, x^{0}\in M$ bel. fest \begin{enumerate} \item Fall: $x^{0}$ liegt auf einer Seite von $M,$ d.h. $x^{0}\in S_{I}.$\\ Da $S_{I}\neq M,S_{I}\neq \emptyset \, \Rightarrow \, \dim S_{I}<\dim M=k+1.\, \Rightarrow \, \dim S_{I}\leq k.$ Wir wissen: $S_{I}$ konvexer Polyeder. Außerdem sind die Ecken von $S_{I}$ auch Ecken von $M.$ IV $\Rightarrow \, \exists \lambda _{1},\ldots ,\lambda _{n}\geq 0,\sum _{i}\lambda _{i}=1:\, x^{0}=\sum _{i=1}^{n}\lambda _{i}x^{i},\, x^{i}$ Ecken \item Fall: $x^{0}$ liegt auf keiner Seite von $M,$ d.h. $x^{0}\in M\setminus \partial M.$ Sei $z\in \R ^{n},z\neq x^{0}.$ Wir betrachten die Gerade $g:=\left\{ \left.x\in \R ^{n}\right|x=t\cdot x_{0}+\left(1-t\right)\cdot z,t\in \R \right\} .$ Wir betrachten die Schnittpunkte $x^{1},x^{2}$ mit $\partial M.$ Es sind genau 2, da $M$ beschränkt. Man kann $x^{1},x^{2}$ wie folgt angeben: $i\in \left\{ 1,2\right\} :$\begin{eqnarray*} x^{i} & = & t_{i}x^{0}+\left(1-t_{i}\right)z\\ t_{1} & = & \min \left\{ \left.t\right|tx^{0}+\left(1-t\right)z\in M\right\} \\ t_{2} & = & \max \left\{ \left.t\right|tx^{0}+\left(1-t\right)z\in M\right\} \end{eqnarray*} $x^{i}$ läßt sich als Konvexkombinationen der Ecken von $S_{I_{i}},i=1,2,$ schreiben (IV) und es gilt $S_{I_{1}}\neq S_{I_{2}},$ d.h. \begin{eqnarray*} x^{1} & = & \sum _{i\in \tilde{I}_{1}}\alpha _{i}x^{i},\, \alpha _{i}\geq 0,i\in \tilde{I}_{1},\, \sum _{i\in \tilde{I}_{1}}\alpha _{i}=1\\ x^{2} & = & \sum _{i\in \tilde{I}_{2}}\alpha _{i}x^{i},\, \alpha _{i}\geq 0,i\in \tilde{I}_{2},\, \sum _{i\in \tilde{I}_{2}}\alpha _{i}=1\\ x^{0} & = & \delta x^{1}+\left(1-\delta \right)x^{2},\, \delta \in \left(0,1\right)\\ \rightarrow \, x^{0} & = & \delta \sum _{i\in \tilde{I}_{1}}\alpha _{i}x^{i}+\left(1-\delta \right)\sum _{i\in \tilde{I}_{2}}\alpha _{i}x^{i}=1,\, \delta \sum _{i\in \tilde{I}_{1}}\alpha _{i}+\left(1-\delta \right)\sum _{i\in \tilde{I}_{2}}\alpha _{i}=1 \end{eqnarray*} \end{enumerate} \end{description} \item [Def.~2.8:]~ \begin{enumerate} \item Sei $K\subseteq \R ^{n}$ mit $x_{0}\in \R ^{n}$ fest: $x^{0},x\in K\, \Rightarrow \, x^{0}+\alpha x\in K\, \forall \alpha \geq 0.$ Dann heißt $K$ Kegel mit Scheitelpunkt $x^{0}.$ \item Sei $K$ ein Kegel mit einem Scheitelpunkt $x^{0}$ und konvexes Polyeder, so heißt $K$ polyedrischer Kegel mit einem Scheitelpunkt $x^{0}.$ \end{enumerate} \item [Satz~2.3(Darstellungssatz~für~polyedrische~Kegel):]Sei $K_{p}=\left\{ \left.x\in \R ^{n}\right|Ax\leq 0\right\} \neq \left\{ 0\right\} .$ Dann existieren Vektoren $y^{1},\ldots ,y^{r}\in K_{p}$ derart, daß \[ K_{p}=\left\{ \left.x\in \R ^{n}\right|x=\sum _{i=1}^{r}\beta _{i}y^{i},\, \beta _{i}\geq 0,i=1,\ldots ,r\right\} .\] \begin{description} \item [Bew.:]Sei $Q:=\left\{ \left.x\in \R ^{n}\right|-1\leq x_{i}\leq 1,i=1,\ldots ,n\right\} $ $n-\dim .$ Einheitswürfel. $K_{Q}=K_{p}\cap Q$ beschr. konvexer Polyeder. S.2.2 \[ \Rightarrow \, K_{Q}=\left\{ \left.y\in \R ^{n}\right|y=\sum _{i=1}^{r}\lambda _{i}y^{i},\lambda _{i}\geq 0,\, \sum _{i}\lambda _{i}=1\right\} ,\] wobei $y^{1},\ldots ,y^{r}$ Ecken von $K_{Q}$ sind. Sei $x\in K_{p}$ bel., $x\neq 0.$ Da $K_{p}$ ein polyedrischer Kegel mit einem Scheitelpunkt in 0 ist, gilt $\alpha x\in K_{p}\, \forall \alpha \geq 0\, \Rightarrow \, y=\frac{x}{\left\Vert x\right\Vert }\in K_{p}.$ Es gilt \begin{eqnarray*} y\in K_{Q} & \rightarrow & y=\sum _{i=1}^{r}\lambda _{i}y^{i},\, \lambda _{i}\geq 0,\sum _{i=1}^{r}\lambda _{i}=1\\ & \rightarrow & x=\sum _{i=1}^{r}\beta _{i}y^{i},\, \beta _{i}=\left\Vert x\right\Vert \cdot \lambda _{i},\, i=1,\ldots ,r. \end{eqnarray*} \end{description} \item [Satz~2.5(Darstellungssatz~für~konvexe~Polyeder):]~ \begin{enumerate} \item Jedes konvexe Polyeder $M,$ das mind. eine Ecke besitzt, hat eine Darstellung der folgenden Form:\begin{eqnarray*} \left(*\right)\, M & = & \left\{ \left.x\in \R ^{n}\right|x=\sum _{i=1}^{k}\lambda _{i}x^{i}+\sum _{j=1}^{l}\beta _{j}y^{j},\, \sum _{i=1}^{k}\lambda _{i}=1,\, \lambda _{i}\geq 0,\, \beta _{j}\geq 0\right\} ,\, k\geq 1 \end{eqnarray*} D.h. $M=P+K$ mit\begin{eqnarray*} P & = & \left\{ \left.x\in \R ^{n}\right|x=\sum _{i=1}^{k}\alpha _{i}x^{i},\, \alpha _{i}\geq 0,\, \sum _{i=1}^{k}\alpha _{i}=1\right\} \\ K & = & \left\{ \left.x\in \R ^{n}\right|x=\sum _{j=1}^{l}\beta _{j}x^{j},\, \beta \geq 0\right\} \end{eqnarray*} \item Jede Menge, die sich in der Form $\left(*\right)$ darstellen läßt, ist ein konvexes Polyeder. \end{enumerate} \begin{description} \item [Bew.:]~ \begin{enumerate} \item o.B.d.A.: $M=\left\{ \left.x\in \R ^{n}\right|Ax\leq b\right\} \neq \left\{ 0\right\} .$ Es gilt \begin{eqnarray*} x\in M & \leftrightarrow & \left(\begin{array}{c} x\\ 1\end{array} \right)\in \tilde{M}:=\left\{ \left.\left(x,\xi \right)\in \R ^{n+1}\right|\left(\begin{array}{cc} A & -b\end{array} \right)\left(\begin{array}{c} x\\ \xi \end{array} \right)\leq 0,\, \xi \geq 0\right\} \end{eqnarray*} $\tilde{M}$ ist ein polyedrischer Pegel. Nach S. 2.3 läßt sich jeder Vektor $\left(\begin{array}{c} x\\ 1\end{array} \right)\in \tilde{M}$ als nichtnegative Linearkomb. von endl. vielen Vektoren $\tilde{a}^{i}\in \R ^{n+1},i\in I$ mit $\tilde{a}^{i}=\left(\begin{array}{c} a^{i}\\ \tilde{a}_{n+1}^{i}\end{array} \right)$ darstellen. Wir betrachten $I_{1}:=\left\{ \left.i\in I\right|\tilde{a}_{n+1}^{i}\neq 0\right\} ,\, I_{2}:=\left\{ \left.i\in I\right|\tilde{a}_{n+1}^{i}=0\right\} .$ o.B.d.A. $\tilde{a}_{n+1}^{i}=1,$ falls $\tilde{a}_{n+1}^{i}\neq 0$ \begin{eqnarray*} \rightarrow \, x & \in & M\\ \leftrightarrow \, \left(\begin{array}{c} x\\ 1\end{array} \right) & \in & \tilde{M}\\ \leftrightarrow \, \left(\begin{array}{c} x\\ 1\end{array} \right) & = & \sum _{i\in I_{1}}\alpha _{i}\left(\begin{array}{c} a^{i}\\ 1\end{array} \right)+\sum _{j\in I_{2}}\beta _{j}\left(\begin{array}{c} a^{j}\\ 0\end{array} \right),\, \alpha _{i},\beta _{j}\geq 0\\ \leftrightarrow \, x & = & \sum _{i\in I_{1}}\alpha _{i}a^{i}+\sum _{j\in I_{2}}\beta _{j}a^{j},\, \sum _{i\in I_{1}}\alpha _{i}=1,\, \alpha _{i}\geq 0,i\in I_{1},\, \beta _{j}\geq 0,j\in I_{2}. \end{eqnarray*} \item analog \end{enumerate} \end{description} \end{description} \subsection{Charakterisierung der Optimalpunkte eines LO-Problems} $\left(P\right)\, \max \left\{ \left.c^{T}x\right|x\in M\right\} ,\, M=\left\{ \left.x\in \R ^{n}\right|Ax=b,\, x\geq 0\right\} $ \begin{description} \item [Satz~2.6:]Wenn $\dim M\geq 1,$ so hat $M$ mind. eine Ecke. \begin{description} \item [Bew.:]Ann.: $M$ hat keine Ecke $\stackrel{\textrm{Cor}.\, 2.1}{\rightarrow }\, M$ enthält eine Gerade als Seite. Sei $g:=\left\{ \left.x\in \R ^{n}\right|x=x^{1}+\lambda \left(x^{2}-x^{1}\right),\lambda \in \R \right\} ,x^{1}\neq x^{2}.$ $g\subseteq M\subseteq \left\{ \left.x\in \R ^{n}\right|x\geq 0\right\} ,$ d.h. $x_{\alpha }^{1}+\lambda \left(x_{\alpha }^{2}-x_{\alpha }^{1}\right)\geq 0,\, \alpha =1,\ldots ,n\forall \lambda \in \R .$ \begin{enumerate} \item Fall: $\exists \alpha ^{*}$ mit $x_{\alpha ^{*}}^{2}-x_{\alpha ^{*}}^{1}>0\, \Rightarrow \, \forall \lambda $ gilt: $\lambda \geq -\frac{x_{\alpha ^{*}}^{1}}{x_{\alpha ^{*}}^{2}-x_{\alpha ^{*}}^{1}}$ Wid. zu $g$ Gerade. \item Fall: $\exists \alpha ^{*}$ mit $x_{\alpha ^{*}}^{2}-x_{\alpha ^{*}}^{1}<0\, \Rightarrow \, \forall \lambda $ gilt: $\lambda <-\frac{x_{\alpha ^{*}}^{1}}{x_{\alpha ^{*}}^{2}-x_{\alpha ^{*}}^{1}}$ Wid. zu $g$ Gerade. \end{enumerate} \end{description} \item [Satz~2.7:]Das Problem \[ \left(P'\right)\, \max \left\{ \left.c^{T}\left(x^{+}-x^{-}\right)\right|A\left(x^{+}-x^{-}\right)+u=b,\tilde{A}\left(x^{+}-x^{-}\right)=\tilde{b},\, x^{+},x^{-},u\geq 0\right\} \] ist äquivalent zu \[ \left(P''\right)\, \max \left\{ \left.c^{T}x\right|Ax\leq b,\tilde{A}x=\tilde{b}\right\} \] im folgenden Sinne: \begin{enumerate} \item Wenn $\left(\hat{x}^{+^{T}},\hat{x}^{-^{T}},\hat{u}^{T}\right)^{T}$ ein Optimalpunkt von $\left(P'\right)$, so ist $\hat{x}=\hat{x}^{+}-\hat{x}^{-}$ eine Lösung von $\left(P''\right).$ \item Wenn $\hat{x}$ eine Lsg. von $\left(P''\right)$ ist, ex. $\hat{x}^{+},\hat{x}^{-},\hat{u}$ derart, daß \begin{enumerate} \item $\left(\hat{x}^{+^{T}},\hat{x}^{-^{T}},\hat{u}^{T}\right)^{T}$ Lsg. von $\left(P'\right)$ \item $\hat{x}=\hat{x}^{+}-\hat{x}^{-}.$ \end{enumerate} \end{enumerate} \item [Def.~2.9:]$u_{r},r=1,\ldots ,m$ heißen Schlupfvariablen. \item [Satz~2.8(Existenzsatz):]Wenn $\sup _{x\in M}c^{T}x<\infty ,$ so wird das Supremum angenommen. \begin{description} \item [Bew.:]Genügt für den Fall, daß $M$ mindestens eine Ecke hat (S.2.6). Darstellungssatz $\Rightarrow $ \[ M=\left\{ \left.x\in \R ^{n}\right|x=\sum _{i=1}^{k}\alpha _{i}x^{i}+\sum _{j=1}^{l}\beta _{j}y^{j},\, \sum \alpha _{i}=1,\alpha _{i}\geq 0,\beta _{j}\geq 0\right\} .\] Sei $x\in M,$ \[ c^{T}x=\sum _{i=1}^{k}\alpha _{i}c^{T}x^{i}+\sum _{j=1}^{l}\beta _{j}\underbrace{c^{T}y^{j}}_{\leq 0,\, \textrm{da }\sup _{x\in M}c^{T}x<\infty }\, \forall \alpha _{i}\geq 0,\sum \alpha _{i}=1.\] Sei $c^{T}x^{i^{*}}=\max \left\{ c^{T}x^{1},\ldots ,c^{T}x^{k}\right\} $ ($x^{i^{*}}$ nicht notwendig eindeutig). \[ \Rightarrow \, c^{T}x\leq \underbrace{\sum _{i=1}^{k}\alpha _{i}}_{1}c^{T}x^{i^{*}}\, \forall x\in M.\] \end{description} \item [Korollar~2.2.:]Wenn $\sup _{x\in M}c^{T}x<\infty $ und $M$ eine Ecke hat, wird das Maximum in einer Ecke angenommen. \item [Satz~2.9:]Jeder lokale Max.pkt. (Min.pkt.) von (LOP)$_{\max \left(\min \right)}$ ist globaler Max.pkt. (Min.pkt.). \begin{description} \item [Bew.:]Sei $\bar{x}$ lokaler Min.pkt. Ann.: $\bar{x}$ ist kein globaler Min.pkt. $\Rightarrow \, \exists y\in M:\, c^{T}y0$ gibt es ein $\lambda \in \left(0,1\right)$ mit \[ x\left(\lambda \right):=\lambda y+\left(1-\lambda \right)\bar{x}\in M\cap U_{\varepsilon }\left(\bar{x}\right).\] Zielfkt. \[ c^{T}x\left(\lambda \right)=c^{T}\left(\lambda y+\left(1-\lambda \right)\bar{x}\right)=\lambda c^{T}y+\left(1-\lambda \right)c^{T}\bar{x}<\lambda c^{T}\bar{x}+\left(1-\lambda \right)c^{T}\bar{x}=c^{T}\bar{x}.\] Wid. zu $\bar{x}$ lok. Min.pkt. \end{description} \item [Satz~2.10:]Es sei $M_{opt}\neq \emptyset .$ Dann gilt: \begin{enumerate} \item $M_{opt}$ ist eine abg. Seite von $M$ oder $M$ selbst. \item Es ex. eine Indexmenge $I\subseteq \left\{ 1,\ldots ,m\right\} $ derart, daß $M_{opt}=\left\{ \left.x\in M\right|\sum _{\alpha }a_{r\alpha }x_{\alpha }=b_{r},\, r\in I\right\} .$ \end{enumerate} \begin{description} \item [Bew.:]Es sei $\bar{x}\in M_{opt}.$ Wir wissen aus der geom. Interpretation $M\subseteq \left\{ \left.x\in \R ^{n}\right|c^{T}x\leq c^{T}\bar{x}\right\} $ und $\bar{x}\in M.$ \begin{eqnarray*} \Rightarrow \, M & = & \left\{ \left.x\in \R ^{n}\right|Ax\leq b,\tilde{A}x=\tilde{b},c^{T}x\leq c^{T}\bar{x}\right\} \\ M_{opt} & = & \left\{ \left.x\in \R ^{n}\right|Ax\leq b,\tilde{A}x=\tilde{b},c^{T}x=c^{T}\bar{x}\right\} \end{eqnarray*} \end{description} \end{description} \section{Die Simplexmethode} \subsection{Theoretische Grundlagen der Simplexmethode} $\left(P\right)\, \max \left\{ \left.c^{T}x\right|x\in M\right\} ,\, M=\left\{ \left.x\in \R ^{n}\right|Ax=b,x\geq 0\right\} ,\, A=\left(a^{1},\ldots ,a^{n}\right)\in \R ^{m\times n}$ Voraussetzungen: \begin{lyxlist}{00.00.0000} \item [(V1)]$m0\right\} $ linear unabhängig. \begin{enumerate} \item $0\leq \left|I^{0}\right|\leq m$ \item Wenn $\left|I^{0}\right|0\right)$ und $\left(A_{B}^{-1}A_{N}\right)_{i_{0}}\leq 0$ ex., so ist $c^{T}x$ auf $M$ nach oben (unten) unbeschränkt. \begin{description} \item [Bew.:]Idee: Konstruieren einer von $x^{0}$ ausgehenden Halbgeraden $h,$ die ganz in $M$ liegt und auf der $c^{T}x$ nach oben unbeschränkt ist. Sei \begin{eqnarray*} h & := & \left\{ \left.x\in \R ^{n}\right|x_{B}=x_{B}^{0}-t\cdot A_{B}^{-1}A_{N}e_{i_{0}},\, x_{N}=t\cdot e_{i_{0}},t\geq 0\right\} \end{eqnarray*} Beh. 1: $h\subseteq M=\left\{ \left.x\in \R ^{n}\right|Ax=b,x\geq 0\right\} .$ \[ x_{B}=x_{B}^{0}-t\cdot A_{B}^{-1}A_{N}e_{i_{0}}\, \Rightarrow \, h\subseteq \left\{ \left.x\in \R ^{n}\right|Ax=b\right\} ,\] d.h. geom. die Halbgerade liegt in dem aff. UR $\left\{ \left.x\in \R ^{n}\right|Ax=b\right\} .$ \[ x_{B}=x_{B}^{0}-t\cdot \underbrace{A_{B}^{-1}A_{N}e_{i_{0}}}_{\leq 0}\geq 0\: \forall t\geq 0\, \Rightarrow \, h\subseteq \left\{ \left.x\in \R ^{n}\right|x\geq 0\right\} \] Beh. 2: $c^{T}x$ auf $h$ nach oben unbeschränkt. \[ c^{T}x=c_{B}^{T}A_{B}^{-1}b-\left(c_{B}^{T}A_{B}^{-1}A_{N}^{T}-c_{N}^{T}\right)x_{N}\, \forall x\in M\, \textrm{insb}.\, \forall x\in h\] \[ x\in h\, \Rightarrow \, c^{T}x=c_{B}^{T}A_{B}^{-1}b-\underbrace{\left(c_{B}^{T}A_{B}^{-1}A_{N}^{T}-c_{N}^{T}\right)\cdot t\cdot e_{i_{0}}}_{\leq 0}\, \stackrel{t\rightarrow \infty }{\rightarrow }+\infty \] \end{description} \item [Def.~3.4:]Zwei Ecken eines konvexen Polyeders $M$ heißen benachbart, wenn sie verschiedene Randpunkte einer Kante von $M$ sind. \item [Satz~3.4:]Es sei $x^{0}$ eine nichtentartete Ecke von $M$ mit $x_{B}^{0}>0,x_{N}=0.$ Wenn $i_{0}\in J_{N}\left(x^{0}\right)$ mit \begin{eqnarray*} \left(c_{N}-A_{B}^{-1}A_{N}^{T}c_{B}\right)_{i_{0}} & < & 0\, \left(>0\right)\\ I_{i_{0}} & := & \left\{ \left.j\right|\left(A_{B}^{-1}A_{N}\right)_{i_{0},j}\geq 0\right\} \neq \emptyset \end{eqnarray*} ex., so gibt es eine Ecke $x^{1}$ von $M$ mit $c^{T}x^{1}>c^{T}x^{0}.$ \begin{description} \item [Bew.:]Idee: Wir betrachten eine Halbgerade $h$ wie beim Bew. von S. 3.3 und bestimmen $x^{1}$ als $h\cap M$ und erhalten die Kante $\left[x^{0},x^{1}\right],$ die das Verlangte leistet. Es sei \[ h:=\left\{ \left.x\in \R ^{n}\right|x_{B}=x_{B}^{0}-A_{B}^{-1}A_{N}^{T}e_{i_{0}}\cdot t,\, x_{N}=t\cdot e_{i_{0}},t\geq 0\right\} .\] Wir wissen $h\subseteq \left\{ \left.x\in \R ^{n}\right|Ax=b\right\} .$ Frage: Für welche $x\in h$ gilt $x\geq 0$ ? D.h. für welche $t$ gilt $x_{B}^{0}-A_{B}^{-1}A_{N}^{T}e_{i_{0}}\cdot t\geq 0$ ? \begin{enumerate} \item $\alpha \in $$\left\{ 1,\ldots ,n\right\} \setminus I_{i_{0}}\, \rightarrow \, \left(A_{B}^{-1}A_{N}\right)_{i_{0},\alpha }\leq 0\, \rightarrow \, x_{\alpha }=x_{\alpha }^{0}-\left(A_{B}^{-1}A_{N}^{T}e^{i_{0}}\right)_{\alpha }\cdot t>0\, \forall t\geq 0$ \item $\alpha \in I_{i_{0}}:$\begin{eqnarray*} x_{\alpha }=x_{\alpha }^{0}-\left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha }\cdot t\, & \geq & 0\\ \leftrightarrow \, 0\leq t & \leq & \frac{x_{\alpha }^{0}}{\left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha }}\, \forall \alpha \in I_{i_{0}}\\ \leftrightarrow \, 0\leq t & \leq & \min _{\alpha \in I_{i_{0}}}\frac{x_{\alpha }^{0}}{\left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha }}=:t_{1} \end{eqnarray*} \end{enumerate} Es gilt $t_{1}>0,$ da $x_{\alpha }^{0},\left(A_{B}^{-1}A_{N}e_{i_{0}}\right)_{\alpha }>0\, \forall \alpha \in I_{i_{0}}.$ Sei $x^{1}=x\left(t_{1}\right).$ Dann gilt \[ \left[x_{0},x_{1}\right]\in \left\{ \left.x\in \R ^{n}\right|x_{B}=x_{B}^{0}-A_{B}^{-1}A_{N}^{T}e_{i_{0}}\cdot t,x_{N}=t\cdot e_{i_{0}},t\in \left[0,t_{1}\right]\right\} ,\] d.h. $x^{0}$ und $x^{1}$ sind benachbart. $\forall x\in M$ gilt: $c^{T}x=c^{T}x^{0}-A_{B}^{-1}A_{N}^{T}x_{N}$ $\forall x\in h$ gilt: $c^{T}x=c^{T}x^{0}-A_{B}^{-1}A_{N}^{T}e_{i_{0}}\cdot t,t\geq 0$ \[ c^{T}x^{1}=c^{T}x^{0}-\underbrace{A_{B}^{-1}A_{N}^{T}e_{i_{0}}}_{<0}\cdot \underbrace{t_{1}}_{>0}\, \rightarrow \, c^{T}x^{1}>c^{T}x^{0}.\] \end{description} \end{description} Austauschschritt (Simplexschritt, Pivotschritt): \begin{enumerate} \item Fall: $c_{N}-\left(A_{B}^{-1}A_{N}\right)^{T}c_{B}\geq 0\, \Rightarrow \, x^{0}$ optimale Ecke \item Fall: $\exists i_{o}\in J_{N}\left(\bar{x}\right),\, \left(c_{N}-\left(A_{B}^{-1}A_{N}\right)^{T}c_{B}\right)_{i_{0}}<0,\, A_{B}^{-1}A_{N}e_{i_{0}}\leq 0\, \Rightarrow \, c^{T}x$ auf $M$ nach oben unbeschränkt. \item Fall: $\exists i_{0}\in J_{N}\left(\bar{x}\right),\, \left(c_{N}-\left(A_{B}^{-1}A_{N}\right)^{T}c_{B}\right)_{i_{0}}<0,\, I_{i_{0}}\neq 0$ Vor.: $x^{0}$ ist nicht entartet. Dann können wir Satz 3.4 anwenden:\begin{eqnarray*} t_{1} & = & \min _{\alpha \in I_{0}}\frac{x_{\alpha }}{\left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha }}=\frac{x_{\alpha _{0}}}{\left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha _{0}}} \end{eqnarray*} Bez.: $i_{0}$-Spalte: Pivotspalte\\ $\alpha _{0}$-Zeile: Pivotzeile\\ $\left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha _{0}}:$ Pivotelement Pivotschritt: Austausch der $i_{0}$-ten NBV gegen die $\alpha _{0}$-te BV, und wir eine benachbarte Ecke $x^{1}$ mit größerem Zielfunktionswert. \begin{tabular}{|c|c|c|c|} \hline & & & $c_{N}$\\ \hline & & & NBV\\ \hline $c_{B}$& BV& $\left(A_{B}^{-1}b\right)_{\alpha _{0}}$& $\begin{array}{ccc} \ddots & \vdots & \cdot \\ \cdots & \left(A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right)_{\alpha _{0}} & \cdots \\ \cdot & \vdots & \ddots \end{array} $\\ \hline & & $c_{B}A_{B}^{-1}b$& $c_{N}-\left(A_{B}^{-1}A_{N}\right)^{T}c_{B}$\\ \hline \end{tabular} \begin{lyxlist}{00.00.0000} \item [Regel~I:]Das Pivotelement wird durch sein Reziprokes ersetzt, d.h. \[ \left[A_{B'}^{-1}A_{N'}^{T}e_{i_{0}}\right]_{\alpha _{0}}=\frac{1}{\left[A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right]_{\alpha _{0}}}.\] Die anderen Elemente der Zeile werden durch $\left[\mathrm{A}_{B}^{-1}A_{N}^{T}e_{i_{0}}\right]_{\alpha _{0}}$ dividiert. \item [Regel~II:]Die Elemente der Pivotspalte werden bis auf das Pivotelement durch $-\left[A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right]_{\alpha _{0}}$ dividiert. \item [Regel~III:]Alle anderen Elemente werden durch die Kreuzregel berechnet: \begin{eqnarray*} \left[A_{B}^{-1}A_{N}^{T}e_{i}\right]_{\alpha _{0}} & = & \frac{\left[A_{B}^{-1}A_{N}^{T}e_{i}\right]_{\alpha }\cdot \left[A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right]_{\alpha _{0}}-\left[A_{B}^{-1}A_{N}^{T}e_{i}\right]_{\alpha _{0}}\cdot \left[A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right]_{\alpha }}{\left[A_{B}^{-1}A_{N}^{T}e_{i_{0}}\right]_{\alpha _{0}}} \end{eqnarray*} \end{lyxlist} \end{enumerate} \begin{description} \item [Satz~3.5:]Sei $\left(P'\right)\, \min \left\{ \left.\sum _{r=1}^{m}u_{r}\right|Ax+u=b,x\geq 0,u\geq 0\right\} .$ Das Problem $\left(P'\right)$ hat eine Lösung $\left(\hat{x},\hat{u}\right)$ und wir unterscheiden 2 Fälle: \begin{enumerate} \item Wenn $\sum _{r=1}^{m}u_{r}=0,$ so ist $M\neq \emptyset .$ \item Wenn $\sum _{r=1}^{m}u_{r}>0,$ so ist $M=\emptyset .$ \end{enumerate} \end{description} \subsection{Der Fall der Entartung (ausführlich siehe \cite{1})} Sei $x^{0}$ bel. zulässiger Basispunkt. Dann gilt $x_{B}^{0}\geq 0,x_{N}^{0}=0,A_{B}$ regulär. $\Rightarrow $ Basisdarstellung: $x_{B}=A_{B}^{-1}b-A_{B}^{-1}A_{N}x_{N}.$ $\exists i_{0}\in J_{N}\left(x^{0}\right):\, x_{i_{0}}=\left[A_{B}^{-1}b\right]_{i_{0}}<0,I_{i_{0}}\neq 0$ Für die Pivotspalte bilden wir $t_{1}:=\min _{\alpha \in I_{i_{0}}}\frac{\left[A_{B}^{-1}b\right]}{\left[A_{B}^{-1}A_{N}e_{i_{0}}\right]_{\alpha }}$. \begin{enumerate} \item $t_{1}>0.$ (Auch wenn $x^{0}$ entartet ist, kann dies eintreten.) Dann gilt $c^{T}x^{1}>c^{T}x^{0},\, x^{1}:=x\left(t_{1}\right).$ \item $t_{1}=0.$ Wir definieren $h$ wie üblich: \[ h=\left\{ \left.x\in \R ^{n}\right|x_{B}=A_{B}^{-1}b-A_{B}^{-1}A_{N}e_{i_{0}}\cdot t,\, x_{N}=t\cdot e_{i_{0}},\, t\in \left[0,t_{1}\right]\right\} .\] $\rightarrow x^{0}=x^{1}=x\left(t_{1}\right),h=\left\{ x^{0}\right\} $ und $c^{T}x^{1}=c^{T}x^{0}.$ \end{enumerate} \begin{description} \item [Bem.~3.11:]Wir führen eine {}``leere'' Simplextransformation durch. Der gleichen Ecke sind zwei verschiedene Basen im $\R ^{m}$ und damit auch zwei verschiedene BV-Systeme mit den entsprechenden Basisdarstellungen und Simplextableaus zugeordnet. \end{description} Eine Möglichkeit: $\varepsilon $-Methode: $P\left(\varepsilon \right):\, \max \left\{ c^{T}x\left|\underbrace{Ax=b\left(\varepsilon \right),x\geq 0}_{M\left(\varepsilon \right)}\right.\right\} $ Ziel: Es gibt ein $\tilde{\varepsilon }>0$ derart, daß gilt: \begin{enumerate} \item $M\left(\varepsilon \right)$ hat nur nichtentartete Ecken $\forall \varepsilon \in \left(0,\tilde{\varepsilon }\right)$ \item $\left(P\right)$ ist lösbar gdw. $P\left(\varepsilon \right)$ lösbar ist \item Wenn $x^{0}\left(\varepsilon \right)$ eine opt. Ecke von $P\left(\varepsilon \right)$ ist, so ist $x^{0}=\lim _{\varepsilon \rightarrow 0}x^{0}\left(\varepsilon \right)$ eine optimale Ecke von $\left(P\right).$ \end{enumerate} Wir müssen $b\left(\varepsilon \right)$ speziell wählen, um diese Bedingung zu erfüllen. $b_{r}\left(\varepsilon \right):=b_{r}+\sum _{\alpha =1}^{n}a_{r\alpha }\varepsilon ^{\alpha },r=1,\ldots ,m$ \begin{description} \item [Lemma~3.1:]Wenn das Problem $\left(P\right)$ die Voraussetzungen $\left(V1\right),\left(V2\right),\left(V3\right)$ erfüllt und $x^{0}$ ein zulässiger Basispunkt ist, dann ex. eine $\varepsilon >0,$ so daß $\forall 0<\varepsilon <\varepsilon _{0}\, P\left(\varepsilon \right)$ folgende Eigenschaften besitzt: \begin{enumerate} \item Das Gleichungssystem in $P\left(\varepsilon \right)$ läßt sich eindeutig nach $x_{B}$ auflösen und es gilt: \begin{eqnarray*} x_{B} & = & A_{B}^{-1}b+\left(\begin{array}{c} \varepsilon ^{1}\\ \vdots \\ \varepsilon ^{n}\end{array} \right)_{B}+\sum _{i\in J_{N}\left(x^{0}\right)}\left(A_{B}^{-1}A_{N}e_{i}\right)\cdot \varepsilon ^{i}-A_{B}^{-1}A_{N}x_{N} \end{eqnarray*} \item $x^{0}\left(\varepsilon \right)$ mit $x_{B}^{0}\left(\varepsilon \right)=A_{B}^{-1}b+\left(\begin{array}{c} \varepsilon ^{1}\\ \vdots \\ \varepsilon ^{n}\end{array} \right)_{B}+\sum _{i\in J_{N}\left(x^{0}\right)}\left(A_{B}^{-1}A_{N}e_{i}\right)\cdot \varepsilon ^{i},\, x_{N}^{0}\left(\varepsilon \right)=0$ ist ein zulässiger Basispunkt. \end{enumerate} \end{description} \section{Dualitätstheorie der Linearen Optimierung (LO) und Anwendungen} \subsection{Dualitätstheorie der LO (siehe auch \cite{1})} $\left(P\right)\, \max \left\{ \left.c^{T}x\right|Ax\leq b,x\geq 0\right\} $ Primalproblem $\left(D\right)\, \min \left\{ \left.b^{T}u\right|A^{T}u\geq c,u\geq 0\right\} $ Dualproblem \begin{description} \item [Lemma~4.1:]Wenn $M_{P}\neq \emptyset $ und $M_{D}\neq \emptyset ,$ dann gilt $c^{T}x\leq u^{T}Ax\leq b^{T}u\, \forall x\in M_{P},u\in M_{D}.$ \begin{description} \item [Bew.:]Sei $x\in M_{P}$ bel. Dann gilt wegen $u\geq 0\, \forall u\in M_{D}:\, u^{T}Ax\leq b^{T}u.$ Analog gilt für jedes $u\in M_{D}$ wegen $x\geq 0\, \forall x\in M_{P}:\, c^{T}x\leq x^{T}A^{T}u.$\begin{eqnarray*} \Rightarrow \, \sup _{x\in M_{P}}c^{T}x & \leq & \inf _{u\in M_{D}}b^{T}u \end{eqnarray*} \end{description} \item [Lemma~4.2(Farkas):]Sei $A=\left(a^{1},\ldots ,a^{m}\right)\in \R ^{n\times m}.$ Dann gilt \begin{eqnarray*} \left\{ \left.x\in \R ^{n}\right|Ax\leq 0\right\} \subseteq \left\{ \left.x\in \R ^{n}\right|c^{T}x\leq 0\right\} & \Leftrightarrow & \exists u\in \R ^{n},u\geq 0:c=A^{T}u \end{eqnarray*} \begin{description} \item [Bew.:]\cite{1} bzw. VL Grundlagen der mathematischen Optimierung \end{description} \item [Satz~4.1(Dualitätssatz):]Wenn $M_{P}\neq 0$ und $M_{D}\neq 0,$ so sind $\left(P\right)$ und $\left(D\right)$ lösbar, und es gilt: \[ c^{T}x^{0}=\max _{x\in M_{P}}c^{T}x=\min _{u\in M_{D}}b^{T}u=b^{T}u^{0},\] wobei $x^{0}$ Lösung von $\left(P\right)$ und $u^{0}$ Lösung von $\left(D\right)$ sind. \begin{description} \item [Bew.:]Die Lösbarkeit von $\left(P\right)$ und $\left(D\right)$ folgt sofort aus dem Ex.satz der Lin. Optimierung. z.z.: $c^{T}x^{0}=b^{T}u^{0}.$ Nach Lemma 4.1 gilt \[ c^{T}x\leq c^{T}x^{0}\leq b^{T}u^{0}\leq b^{T}u\, \forall x\in M_{P},u\in M_{D}.\] Wir zeigen: $\exists \hat{x}\in M_{P}$ und $\hat{u}\in M_{D}$ mit \begin{eqnarray*} c^{T}x & \geq & \min _{u\in M_{D}}b^{T}u=:\nu \\ b^{T}u & \leq & \max _{x\in M_{P}}c^{T}x=:\mu \end{eqnarray*} Es gilt $c^{T}x\leq \mu \, \forall x\in M_{P}.$ Wir wollen den Satz von Farkas anwenden, deshalb $\R ^{n}\times \R :$\begin{eqnarray*} t\cdot c^{T}x-\mu \cdot t & \leq & 0\, \forall \left(x^{T},t\right)\in \R ^{n}\times \R \, \\ \textrm{mit}\, \left(x^{T},t\right) & \in & M_{t}:=\left\{ \left.\left(x^{T},t\right)\right|t\cdot Ax-t\cdot b\leq 0,-tx\leq 0,-t\leq 0\right\} \end{eqnarray*} Es seien $c^{*^{T}}=\left(c^{T},-\mu \right),x^{*^{T}}=\left(tx^{T},t\right),A^{*}=\left(a_{i,j}^{*}\right)_{m+n+1,n+1}=\left(\begin{array}{cc} A & -b\\ -E & 0\\ 0^{T} & -1\end{array} \right).$\[ \rightarrow \, M_{t}=\left\{ \left.x^{*}\right|A^{*}x^{*}\leq 0\right\} ,\, c^{*^{T}}x^{*}\leq 0\, \forall x^{*}\in M_{t}\] $\Rightarrow $ Satz von Farkas $A^{*^{T}}u^{*}=c^{*},u^{*}>0$ hat eine Lsg. $\hat{u}^{*},$ wobei $\hat{u}^{*}$ ein $\left(m+n+1\right)$-dim. Vektor ist: $u^{*^{T}}=\left(u^{T},y^{T},\alpha \right).$ \begin{eqnarray*} \left(\begin{array}{ccc} A^{T} & -E & 0\\ -b & 0 & -1\end{array} \right)\left(\begin{array}{c} u\\ y\\ \alpha \end{array} \right) & = & \left(\begin{array}{c} c\\ -\mu \end{array} \right) \end{eqnarray*} d.h. das System $A^{T}u-y=c,\, b^{T}u+\alpha =\mu ,\, u\geq 0,y\geq 0,\mu \geq 0$ hat eine Lsg. $\left(\hat{u},\hat{y},\hat{\alpha }\right).$ Wegen $\hat{\mu }\geq 0,\alpha \geq 0$ folgt $A^{T}\hat{u}\geq c$ und $b^{T}\hat{u}\leq \mu .$ \end{description} \item [Satz~4.2:]$\left(P\right)$ ist lösbar $\Leftrightarrow \, \left(D\right)$ ist lösbar, und es gilt $\max _{x\in M_{P}}c^{T}x=\min _{u\in M_{D}}b^{T}u.$ \begin{description} \item [Bew.:]Analog zum Bew. von S. 4.1 gibt es ein $\hat{u}\in M_{D}\neq \emptyset $ mit $A^{T}\hat{u}\geq c.$ Nach S. 4.1 ist $\left(D\right)$ lösbar und die opt. Zielfunktionswerte gleich. \end{description} \item [Corollar~4.1:]$x^{0}\in M_{P},u^{0}\in M_{D}$ sind Lsg. von $\left(P\right),\left(D\right)\, \Leftrightarrow \, \left(u^{0}\right)^{T}\left(Ax^{0}-b\right)=\left(\left(u^{0}\right)^{T}A-c\right)^{T}x^{0}=0$ \end{description} \subsection{Einige Anwendungen der Dualitätstheorie} \begin{enumerate} \item Einschließungssatz: Bem. 4.1 \item Manchmal ist das Dualproblem leichter lösbar. \item Duale Simplexmethode: Lsg. des Dualproblems in der Schreibweise des Primalproblems. Übergang von einem Basispunkt, der das Optimalitätskriterium erfüllt, zu einem anderen Basispunkt mit kleinerem Zielfunktionswert (bei Max.prob., Details in \cite{1}). \item Anwendungen in der lin. parametrischen Optimierung $P_{1}\left(t\right):\, \max \left\{ \left.\left(c+t\cdot c^{*}\right)^{T}x\right|Ax=b,x\geq 0\right\} ,t\in \left[t_{0},t_{1}\right]$ mit Simplexmethode $P_{2}\left(t\right):\, \max \left\{ \left.c^{T}x\right|Ax=b+tb^{*},x\geq 0\right\} ,t\in \left[0,1\right]$ mit dualer Simplexmethode $x^{0}$ sei zulässiger Basispunkt für $P_{1}\left(0\right),\, x_{B}=A_{B}^{-1}b-A_{B}^{-1}A_{N}x_{N}$ in $c^{T}x$ subst., hängt von $t$ ab:\begin{eqnarray*} \left(c+t\cdot c^{*}\right)^{T}x & = & c_{B}^{T}x_{B}-\left(\left(c_{B}+t\cdot c_{B}^{*}\right)A_{B}^{-1}A_{N}-\left(c_{N}+t\cdot c_{N}^{*}\right)\right)x_{N} \end{eqnarray*} $\Rightarrow \, x^{0}$ ist optimal $\forall t$ mit \[ \left(c_{B}+tc_{B}^{*}\right)A_{B}^{-1}A_{N}-\left(c_{N}+tc_{N}^{*}\right)\geq 0.\] Dann berechnet sich $t_{1}$ und es ex. ein $i_{0}$ mit \[ \left(\left(c_{B}+tc_{B}^{*}\right)A_{B}^{-1}A_{N}-\left(c_{N}+tc_{N}^{*}\right)\right)_{i_{0}}=0.\] $\Rightarrow i_{0}$ -Spalte ist Pivotspalte, Pivotzeile und -element wie üblich. Simplextransformation und Berechnung einer benachbarten Ecke. In jedem Schritt erhalten wir ein Intervall $\left[t_{i},t_{i+1}\right]$ und eine zugehörige Ecke $x^{i}$ die $\forall t\in \left[t_{i},t_{i+1}\right]$ optimal ist. \begin{description} \item [Bem.~4.3:]Das reicht im Falle nichtentarteter Ecken. Im Falle von Entartungen ist die berechnete Einteilung nicht eindeutig. \end{description} \item Vektoroptimierung (Optimierungsprobleme mit mehreren Zielfunktionen, siehe \cite{3}) \[ \min \left\{ \left.\left(f_{1}\left(x\right),\ldots ,f_{L}\left(x\right)\right)\right|x\in M\right\} ,M\subseteq \R ^{n},f_{j}:\R ^{n}\rightarrow \R ,j=1,\ldots ,L.\] \begin{description} \item [Def.~4.4:]$\hat{x}$ heißt Pareto-optimal oder effizient, wenn es kein $x\in M$ gibt, so daß $f_{j}\left(x\right)\leq f_{j}\left(\hat{x}\right),j=1,\ldots ,L,\exists j^{*}\in \left\{ 1,\ldots ,L\right\} :f_{j^{*}}\left(x\right)0\right\} \textrm{ bel}.\] $M_{eff}=\bigcup _{\mu \in \R ^{L}}M_{opt}\left(\mu \right)$ Dialogverfahren: $K\subseteq \left\{ 1,\ldots ,L\right\} $ zu verbessernde Restriktionen; $a_{j},j\in K$ Ziele; $a_{i},i\not \in K$ obere Schranken\\ $\mu _{j}^{1}=a_{j}$ Wunsch; $x^{k}\in M$ sei bekannt und es sei $f_{j}\left(x^{k}\right)\leq \mu _{j}^{0},j=1,\ldots ,L$ \[ P\left(\mu ^{1},\mu ^{0},t\right):\, \min \left\{ \left.\sum _{j=1}^{L}\lambda _{j}^{0}f_{j}\left(x\right)\right|x\in M,f_{j}\left(x\right)\leq \mu _{j}^{0}+t\left(\mu _{j}^{1}-\mu _{j}^{0}\right),j=1,\ldots ,L,t\in \left[0,1\right]\right\} \] \end{enumerate} \section{Parametrische Optimierung: Singularitäten (\cite{4,5})} \subsection{Einführung und einige Anwendungen der parametrischen Optimierung} $P\left(t\right):\, \min \left\{ \left.f\left(x,t\right)\right|x\in M\left(t\right)\right\} ,t\in \R \, \left(t\in \left[0,1\right]\right)$ $M\left(t\right):=\left\{ \left.x\in \R ^{n}\right|h_{i}\left(x,t\right)=0,i\in I;g_{j}\left(x,t\right)\geq 0,j\in J\right\} ,f,g_{i},h_{j}\in C^{2}\left(\R ^{n}\times \R ,\R \right)$ $\left(x,t\right)$ lok. Minpkt. $\Leftrightarrow \, x$ lok. Minpkt. für $P\left(t\right)$ $\Sigma _{loc}:=\left\{ \left.\left(x,t\right)\in \R ^{n}\times \R \right|x\, \textrm{ist lokaler Minpunkt für }P\left(t\right)\right\} $, $\Sigma _{stat},\Sigma _{crit},\Sigma _{gc}$: stat., krit, verallg. krit. Punkte $\Sigma _{loc}\subseteq \Sigma _{stat}\subseteq \Sigma _{crit}\subseteq \Sigma _{gc}$ $\left(P\right):\, \min \left\{ \left.f\left(x,t\right)\right|h_{i}\left(x\right)=0,i\in I;g_{j}\left(x\right)\leq 0,j\in J\right\} $ \begin{lyxlist}{00.00.0000} \item [Einbettungsprinzip:]~ $\left(A1\right)\, x^{0}$ ist krit.(stat.) Pkt. für $P\left(0\right)$ $\left(A2\right)\, \psi _{glob}\left(t\right)\neq 0\, \forall t\in \left[0,1\right]$ $\left(A3\right)\, P\left(1\right)\cong \left(P\right)$ \item [Standardeinbettung:]\[ P\left(t\right):\min \left\{ t\cdot f\left(x\right)+\left(1-t\right)\cdot \left\Vert x-x^{0}\right\Vert ^{2}\left|\begin{array}{cccc} h_{i}\left(x\right)+\left(t-1\right)h_{i}\left(x^{0}\right) & = & 0 & i\in I\\ g_{j}\left(x\right)+\left(t-1\right)g_{j}\left(x^{0}\right) & \leq & 0 & j\in J\end{array} \right.\right\} \] $\left(A1\right)\, x^{0}$ ist glob. Minpkt. für $P\left(0\right)$ $\left(A2\right)\, M\left(t\right)\neq \emptyset \, \forall t\in \left[0,1\right],I=\emptyset $ $\left(A3\right)\, P\left(1\right)\equiv \left(P\right)$ \end{lyxlist} \subsection{Generische Singularitäten - die Klasse von Jougen-Jonker-Twilt (\cite{4,5,6,7})} \begin{description} \item [Def.~5.1:]$\bar{x}\in \R ^{n}$ heißt verallg. krit. Pkt. für $P\left(\bar{t}\right),$ wenn $\exists \lambda _{i},i=0,\ldots ,m,\mu _{j},j\in J_{0}\left(\bar{x},\bar{t}\right)$ mit $\sum _{i=0}^{m}\left|\lambda _{i}\right|+\sum _{j\in J_{0}\left(\bar{x},\bar{t}\right)}\left|\mu _{j}\right|>0$ und\begin{eqnarray*} \lambda _{0}D_{x}f\left(\bar{x},\bar{t}\right)+\sum _{i=1}^{m}\lambda _{i}D_{x}h_{i}\left(\bar{x},\bar{t}\right)+\sum _{j\in J_{0}\left(\bar{x},\bar{t}\right)}\mu _{j}D_{x}g_{j}\left(\bar{x},\bar{t}\right) & = & 0\\ h_{i}\left(\bar{x},\bar{t}\right) & = & 0,i\in I\\ g_{j}\left(\bar{x},\bar{t}\right) & \geq & 0,j\in J_{0}\left(\bar{x},\bar{t}\right) \end{eqnarray*} Wenn $\lambda _{0}\neq 0$ (setzen $\lambda _{0}=-1$), $\mu _{j}\geq 0,j\in J_{0}\left(\bar{x},\bar{t}\right)$ stationäre Punkte. Wenn nur $\lambda _{0}\neq 0$ kritische Punkte. \end{description} Wir betrachten 5 Typen: $\Sigma _{gc}^{\nu },\nu =1,\ldots ,5,\, J_{0}\left(\bar{x},\bar{t}\right)=\left\{ 1,\ldots ,p\right\} $ \begin{description} \item [Def.:]$\left(\bar{x},\bar{t}\right)\in \Sigma _{gc}^{1},$ wenn $\bar{x}$ ein nichtentarteter krit. Punkt von $P\left(\bar{t}\right)$ ist, d.h. \begin{lyxlist}{00.00.0000} \item [(1a)]LICQ ist in $\bar{x}\in M\left(\bar{t}\right)$ erfüllt. $\rightarrow \, \exists $ eind. best. Lagrangemultiplikatoren $\bar{\lambda }=\left(\bar{\lambda }_{1},\ldots ,\bar{\lambda }_{m}\right),\bar{\mu }^{J_{0}}=\left(\bar{\mu }_{1},\ldots ,\bar{\mu }_{p}\right),$ so daß $\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}},\bar{t}\right)$ ist eine Lsg. von \[ H^{p}\left(x,\lambda ,\mu ,t\right):=\left[\begin{array}{c} D_{x}^{T}L^{J_{0}}\left(x,\lambda ,\mu ^{J_{0}},t\right)\\ h_{1}\left(x,t\right)\\ \vdots \\ h_{m}\left(x,t\right)\\ g_{1}\left(x,t\right)\\ \vdots \\ g_{p}\left(x,t\right)\end{array} \right]=0\] \item [(1b)]$\bar{\mu }_{j}\neq 0,\, j\in J_{0}\left(\bar{x},\bar{t}\right)$ \item [(1c)]$\left.D_{x}^{2}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}},t\right)\right|_{T_{\bar{x}}M\left(t\right)}$ reg., \[ T_{\bar{x}}M\left(t\right):=\left\{ \left.\xi \in \R ^{n}\right|D_{x}h_{i}\left(\bar{x},\bar{t}\right)\cdot \xi =0,i\in I;D_{x}g_{j}\left(\bar{x},\bar{t}\right)\cdot \xi =0,j\in J_{0}\right\} \] \end{lyxlist} \item [Satz:]Es existiert eine lokale Struktur in einer Umgebung $U\left(\bar{x},\bar{t}\right)=U_{1}\left(\bar{x}\right)\times U_{2}\left(\bar{t}\right).$ \begin{description} \item [Bew.:]$H^{p}\in C^{2}\left(\R ^{q}\times \R ,\R ^{q}\right)$ mit $q=m+p+n,\, H^{p}\left(\bar{w},\bar{t}\right)=0.$ Sei $w:=\left(x,\lambda ,\mu ^{J_{0}}\right)\in \R ^{q}.$ Jacobi Matrix \begin{eqnarray*} D_{w}H^{p}\left(\bar{w},\bar{t}\right) & = & \left(\begin{array}{cc} D_{x}^{2}L^{J_{0}}\left(\bar{w},\bar{t}\right) & B\\ B^{T} & 0\end{array} \right)\\ B & = & \left(-D_{x}h_{1}\left(\bar{x},\bar{t}\right),\ldots ,-D_{x}^{T}h_{m}\left(\bar{x},\bar{t}\right),-D_{x}^{T}g_{1}\left(\bar{x},\bar{t}\right),\ldots ,-D_{x}^{T}g_{p}\left(\bar{x},\bar{t}\right)\right) \end{eqnarray*} Satz: $\left(\begin{array}{cc} A & B\\ B^{T} & 0\end{array} \right)$ reg. $\Leftrightarrow \, \left.A\right|_{B}$ reg. und $B$ vollen Rang hat. Der Satz über implizite Funktionen ist anwendbar: $\exists $ Umgebungen $U\subseteq \R ^{n}$ von $\bar{x},\, V\subseteq \R ^{n}$ von $\bar{\lambda },\, W\subseteq \R ^{n}$ von $\bar{\mu }^{J_{0}}$ und $Z\subseteq \R $ von $\bar{t}$ sowie eindeutig bestimmte Funktionen $\left(C^{1}\right):$ \[ \left(x^{p},\lambda ^{p},\mu ^{p}\right):\, t\rightarrow \left(x^{p}\left(t\right),\lambda ^{p}\left(t\right),\mu ^{p}\left(t\right)\right)\in U\times V\times W\] mit folgenden Eigenschaften: \begin{itemize} \item $H^{p}\left(x^{p}\left(t\right),\lambda ^{p}\left(t\right),\mu ^{p}\left(t\right)\right)=0$ \item $\Sigma _{gc}\cap U\times Z=\left\{ \left.\left(x^{p}\left(t\right),t\right)\right|t\in Z\right\} $ \item $\left(x^{p}\left(t\right),t\right)\in \Sigma _{gc}^{1}\, \forall t\in Z$ (da gilt $g_{j}\left(x^{p}\left(t\right),t\right)>0,j\in J\setminus J_{0}\left(\bar{x},\bar{t}\right)$) \end{itemize} \end{description} \item [Def.~Starke~(Whitney-)Topologie:]$k\in \N .$ Sei $\alpha \in \left(\alpha _{1},\ldots ,\alpha _{m}\right)\in \N ^{n},\, \left|\alpha \right|:=\sum \alpha _{i}0\forall x\in \R ^{n}\right\} \] Wir definieren die $C_{s}^{k}$-Topologie, indem wir eine Basis in $C^{k}\left(\R ^{n},\R \right)$ angeben:\begin{eqnarray*} V_{\phi ,f}^{k} & := & \left\{ \left.g\in C^{k}\left(\R ^{n},\R \right)\right|\left|\partial ^{\alpha }f\left(x\right)-\partial ^{\alpha }g\left(x\right)\right|<\phi \, \forall x\in \R ^{n}\forall \alpha ,\left|\alpha \right|0$ (eind. best. bis auf einen gem. Faktor) und \[ \sum _{i=1}^{m}\bar{q}_{i}D_{x}h_{i}\left(\bar{x},\bar{t}\right)+\sum _{j=1}^{p}\bar{q}_{m+j}D_{x}g_{j}\left(\bar{x},\bar{t}\right)=0\, \left(*\right)\] ($n$ Gl. mit $n+1$ Var. (5a) und der Rang der Koeff.matrix ist $n$ wegen (5b)) \begin{lyxlist}{00.00.0000} \item [(5c)]In $\left(*\right)$ gelte $\bar{q}_{m+j}\neq 0,\, j=1,\ldots ,p.$ \item [$M_{q}\left(t\right):=\left\{ \left.x\in \R ^{n}\right|h_{i}\left(x,t\right)=0,i\in I;g_{j}\left(x,t\right)\geq 0,j\in J_{0}\left(\bar{x},\bar{t}\right)\setminus \left\{ q\right\} \right\} ,q\in J_{0}\left(\bar{x},\bar{t}\right)$]~ \end{lyxlist} Wegen (5a), (5b) und (5c) gilt \[ \forall q\in \left\{ 1,\ldots ,p\right\} :\, D_{x}h_{i}\left(\bar{x},\bar{t}\right),D_{x}g_{j}\left(\bar{x},\bar{t}\right),j\in J_{0}\left(\bar{x},\bar{t}\right)\setminus \left\{ q\right\} \textrm{ lin}.\textrm{ unabh}.\] (Bew.: Ann. $D_{x}h_{i},D_{x}g_{j}$ lin. abh. $\rightarrow \, \exists \bar{q}_{i},\bar{q}_{m+j},\, \sum \left|\bar{q}_{i}\right|+\sum \left|\bar{q}_{m+j}\right|>0:\, \sum _{i\in I}\bar{q}_{i}D_{x}h\left(\bar{x},\bar{t}\right)+\sum _{j=1}^{p-1}\bar{q}_{m+j}D_{x}g_{j}\left(\bar{x},\bar{t}\right)=0\, \stackrel{\left(*\right)}{\Rightarrow }\bar{q}_{m+p}=0$ Wid. zu (5c).) \begin{lyxlist}{00.00.0000} \item [(5d)]$\left(\bar{x},\bar{t}\right)$ ist ein nicht-entarteter krit. Pkt. für \begin{eqnarray*} P^{q}\left(t\right) & : & \min \left\{ \left.f\left(x,t\right)\right|x\in M_{q}\left(t\right)\right\} \, \forall q\in J_{0}\left(\bar{x},\bar{t}\right)\\ \tilde{P}^{q}\left(t\right) & : & \min \left\{ \left.f\left(x,t\right)\right|x\in \tilde{M}_{q}\left(t\right)\right\} ,\tilde{M}_{q}\left(t\right):=\left\{ \left.x\in M_{q}\left(t\right)\right|g_{q}\left(x,t\right)\geq 0\right\} \end{eqnarray*} \end{lyxlist} \item [Satz~5.4(Gauvin):]Sei $\Lambda \left(x\right)$ die Menge der Lagrange-Multiplikatoren, die einem stat. Pkt. von $\left(P\right)$ zugeordnet ist. Dann ist $\Lambda \left(x\right)$ nicht leer und ein kompaktes, konvexes Polyeder $\Leftrightarrow $ MFCQ in $\bar{x}$ erfüllt ist. $\Rightarrow $ lokale Struktur der Lagrange-Multiplikatoren \item [Def.~5.2:]Klasse von Jongen-Jonker-Twilt: \[ F:=\left\{ \left.\left(f,H,G\right)\in C^{3}\left(\R ^{n},\R \times \R ^{m}\times \R ^{s}\right)\right|\Sigma _{gc}=\bigcup _{\nu =1}^{5}\Sigma _{gc}^{\nu }\right\} ,\, H=\left(\begin{array}{c} h_{1}\\ \vdots \\ h_{m}\end{array} \right),G=\left(\begin{array}{c} g_{1}\\ \vdots \\ g_{s}\end{array} \right)\] $P\left(t\right)$ JJT-regulär bzgl. $\left[0,1\right]$ \item [Satz~5.5:]$\Sigma _{gc}^{\nu },\nu \in \left\{ 1,\ldots ,5\right\} $ ist eine diskrete Pkt.menge (folgt unmittelbar aus der lokalen Struktur) \item [Satz~5.6:]Seien $P\left(t\right)$ JJT-regulär bzgl. $\R $ und $\left(\bar{x},\bar{t}\right)\in c\ell \Sigma _{stat}.$ Dann ist die MFCQ verletzt $\Leftrightarrow $ entweder $\left(\bar{x},\bar{t}\right)\in \Sigma _{gc}^{4}$ oder $\left(\bar{x},\bar{t}\right)\in \Sigma _{gc}^{5}$ und alle $\bar{q}_{m+j}$ haben das gleiche Vorzeichen: \[ \sum _{i\in I}\bar{q}_{i}D_{x}h_{i}\left(\bar{x},\bar{t}\right)+\sum _{j=1}^{p}\bar{q}_{j}D_{x}g_{j}\left(\bar{x},\bar{t}\right)=0.\] Setzen $a^{i}:=-D_{x}g_{i}\left(\bar{x},\bar{t}\right),i=1,\ldots ,p;\, c^{k}:=D_{x}h_{k}\left(\bar{x},\bar{t}\right),k=1,\ldots ,m$ \[ \stackrel{L.6.3.}{\Rightarrow }\, D_{x}g_{i}\left(\bar{x},\bar{t}\right)\xi >0,\, D_{x}h_{k}\left(\bar{x},\bar{t}\right)\xi =0\] ist nicht lösbar. $\left(\bar{x},\bar{t}\right)\in \Sigma _{gc}^{5}\, \Rightarrow \, J_{0}\left(\bar{x},\bar{t}\right)\neq \emptyset \, \Rightarrow $ MF1($D_{x}h_{i}\left(\bar{x},\bar{t}\right),i\in I,$ lin. unabh.) ist nicht erfüllt. Es gilt: MF2 ist nicht erfüllt $\Leftrightarrow $ in $\sum _{i\in I}\bar{q}_{i}D_{x}h_{i}\left(\bar{x},\bar{t}\right)+\sum _{j=1}^{p}\bar{q}_{m+j}D_{x}g_{j}\left(\bar{x},\bar{t}\right)=0$ alle $\bar{q}_{m+j},j=1,\ldots ,p$ das gleiche Vorzeichen haben. (Lemma 6.3) \end{description} \subsection{Der Generizitätssatz und der Störungssatz (ohne Beweis)} Fragen: \begin{enumerate} \item Ist die Klasse $F$ hinreichend groß? Antwort: $F$ ist offen und dicht bzgl. $C_{s}^{3}$-Topologie (offen und dicht $\sim $ generisch) \item Wie kommt man durch Störungen in die Klasse $F$ ?\begin{eqnarray*} f\left(x,t,A,c\right) & := & f\left(x,t\right)+\frac{1}{2}x^{T}Ax+c^{T}x\\ h_{i}\left(x,t,b^{i},d_{i}\right) & := & h_{i}\left(x,t\right)+b^{i^{T}}x+d_{i},\, i\in I\\ g_{j}\left(x,t,b^{m+j},d_{m+j}\right) & := & g_{j}\left(x,t\right)+b^{m+j^{T}}x+d_{m+j},\, j\in J \end{eqnarray*} \begin{eqnarray*} P_{\mathrm{A}}\left(t\right) & : & \min \left\{ \left.f\left(x,t,A,c\right)\right|h_{i}\left(x,t,b^{i},d_{i}\right)=0,i\in I;g_{j}\left(x,t,b^{m+j},d_{m+j}\right)\geq 0,j\in J;t\in \R \right\} \\ \mathrm{A} & := & \left(A,c,b^{i},d_{i},i\in I,b^{m+j},d_{m+j},j\in J\right) \end{eqnarray*} {}``Für fast alle $\mathrm{A}\in \R ^{\delta }$'' gilt: $\left(f\left(x,t,A,c\right),h_{i}\left(x,t,b^{i},d_{i}\right),g_{j}\left(x,t,b^{m+j},d_{m+j}\right)\right)\in F,\, \mathrm{A}\not \in F$ hat das Lebesgue-Maß 0. \end{enumerate} \begin{description} \item [Def.~5.3:]$A\subseteq \R ^{n}$ hat das Lebesgue-Maß $0,$ wenn $\forall \varepsilon >0$ eine Folge von Würfeln $W_{i}\subseteq \R ^{n}$ ex. mit $A\subseteq \bigcup _{i=1}^{\infty }W_{i}$ und $\sum _{i=1}^{\infty }\textrm{vol}\left(W_{i}\right)<\varepsilon .$ \item [Bem.:]Sei $A\subseteq \R ^{n}$ eine Menge von L-Maß 0. Dann gilt $\R ^{n}\setminus A$ ist dicht, d.h. $c\ell \left(\R ^{n}\setminus A\right)=\R ^{n}.$ \item [Satz~5.7:]Sei $\left(f,H,G\right)\in F.$ Dann ist $\Sigma _{gc}^{1}\, C_{s}^{3}$-offen und $C_{s}^{3}$-dicht in $\Sigma _{gc}$ und die Menge $\Sigma _{gc}^{\nu },\nu \in \left\{ 2,\ldots ,5\right\} ,$ ist eine diskrete Punktmenge. \item [Satz~5.8(Störungssatz):]Jede in \[ \left\{ \left.\mathrm{A}\in \R ^{\gamma }\right|f\left(x,t,A,c\right),h_{i}\left(x,t,b^{i},d^{i}\right),g_{j}\left(c,t,b^{m+j},d_{m+j}\right)\not \in F\right\} \] enthaltene und bzgl. des $\gamma $-dim. L-Maßes meßbare Menge hat das L-Maß 0 (Wir sagen: Für fast alle $A\in \R ^{\gamma }$ gilt: $\left(f,\, h_{i},i\in I,\, g_{j},j\in J\right)\in F$). \item [Satz~5.9(Generizitätssatz):]Sei $\left(f,H,G\right)\in F.$ Dann ist $F\, C_{s}^{3}$-offen und $C_{s}^{3}$-dicht in $C^{3}\left(\R ^{n}\times \R ,\R \right)^{1+m+s}.$ \end{description} \section{Kurvenverfolgung und Sprünge} \begin{description} \item [PATH~III~/~JUMP~I:](V1) JJT-reg. bzgl. $\left[0,1\right]$ (V2) $\left(x^{0},0\right)\in \Sigma _{gc}^{1}\cap \Sigma _{loc}$ bekannt (V3) $M\left(t\right)\neq \emptyset \, \forall t\in \left[0,1\right],\, M\left(t\right)\subseteq C,\, C$ kompakt \item [Satz~6.1:](V1) $M\left(t\right)\neq \emptyset $ und $M\left(t\right)\subseteq C,\, C$ kompakt $\forall t\in \left[0,1\right]$ (V2) $\left(x^{0},t^{0}\right)\in \Sigma _{stat}^{1}$ bekannt und es ist der einzige stat. Pkt für $P\left(0\right)$ (V3) $P\left(t\right)$ ist JJT-regulär bzgl. $\left[0,1\right]$ (V4) MFCQ ist erfüllt $\forall x\in M\left(t\right),t\in \left[0,1\right]$ Dann ex. ein stückweiser $C^{2}$-Weg in $\Sigma _{stat},$ der $\left(x^{0},0\right)$ mit $\left(x^{*},1\right)$ verbindet, und es treten nur Singulatitäten vom Typ 2 und 3 auf. \end{description} It.verfahren: $x^{k+1}=x^{k}+\alpha _{k}s^{k},\, s^{k}$ Richtungsvektor, $\alpha _{k}>0$ Schrittlänge, $f\left(x^{k+1}\right)0,$ so daß $f\left(\bar{x}\right)>f\left(\bar{x}+ts\right)\, \forall t\in \left(0,\bar{t}\right].$ \begin{description} \item [Bew.:]$\phi \left(t\right):=f\left(\bar{x}+ts\right),\phi '\left(0\right)=Df\left(\bar{x}\right)s<0,$ Taylor: $\phi \left(t\right)=\phi \left(0\right)+t\underbrace{\phi '\left(0\right)}_{<0}+o\left(t\right).$ \end{description} \item [Bem.~6.1:]Die durch $Df\left(\bar{x}\right)\cdot s<0$ bestimmte Abstiegsrichtung ergibt sich aus der Approx. von $\phi \left(t\right)$ mit Hilfe der Taylorentw. bis zur 1. Ableitung. Man nennt eine solche Abstiegsrichtung Abstieg von 1. Ordung. Abstiegsrichtung 1. Ordnung mit Restriktionen: $Df\left(\bar{x}\right)s<0,Dg_{j}\left(\bar{x}\right)s\geq 0,j\in J_{0}\left(\bar{x}\right).$ \item [JUMP~II{*}:]Sei $\left[0,1\right]\subseteq \left[t_{A},t_{B}\right]$ und $\left[t_{A},t_{B}\right]$ ein hinreichend großes Intervall. (V1),(V2),(V3) Diskretisieren $\left[t_{A},t_{B}\right]:t_{-q_{1}}<\ldots