%% 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} \usepackage{fancyhdr} \pagestyle{fancy} \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{\N}{\mathbb{N}} \rhead{} \usepackage{babel} \makeatother \begin{document} \title{\noindent {\Large VL Grundlagen der mathematischen Optimierung}} \author{~\\ \\ \\ Mitschrift zur Vorlesung von Prof. Dr. Jürgen Guddat im WS 2001/2002\\ HU Berlin, Institut für Mathematik\\ \\ \\ \\ } \maketitle \pagebreak \tableofcontents{} \pagebreak \section{Einleitung} \subsection{Formulierung des allgemeinen Optimierungsproblems} \begin{itemize} \item $X$ allgemeiner Raum, z.B. normierter Raum oder $X=\R ^{n}$ \item $f:X\rightarrow \R $ \item $M\subseteq X$\[ (P)\, \, \, \min \left\{ f\left(x\right)\left|x\in M\right.\right\} \] \end{itemize} allgem.~Ziel: bestimme $\bar{x}\in M$ mit $f\left(\bar{x}\right)\leq f\left(x\right),\, \forall x\in M$ \begin{description} \item [Bezeichnungen]~ \begin{description} \item [$\bar{x}$]heißt globaler Minimalpunkt \item [$f\left(x\right)$]heißt Zielfunktion \item [$M$]heißt zulässiger Bereich oder Restriktionsmenge \item [$x\in M$]heißt zulässiger Punkt \end{description} \item [Definition~1.1](Lokaler Minimalpunkt) \begin{description} \item [$\exists \varepsilon >0,\, \bar{x}\in M$]mit $f\left(\bar{x}\right)\leq f\left(x\right),\, \forall x\in M\cap U_{\varepsilon }\left(\bar{x}\right)$ und $U_{\varepsilon }\left(\bar{x}\right):=\left\{ x\in X\left|\left\Vert x-\bar{x}\right\Vert \leq \varepsilon \right.\right\} $ \end{description} \end{description} \subsection{Klassen von Optimierungsproblemen} \begin{enumerate} \item $(P)$ heißt Optimierungsproblem in unendlich-dimensionalen Räumen (infinite Optimierung). \item $X=\R ^{n}$ und $M:=\left\{ x\in \R ^{n}\left|h_{i}\left(x\right)=0,g_{j}\left(x\right)\geq 0,i\in \left\{ 1,\ldots ,m\right\} ,j\in \left\{ 1,\ldots ,s\right\} \right.\right\} $ heißt endlich-dimensionale oder finite Optimierung. Wenn mindestens eine der Funktionen nichtlinear ist $\rightarrow $ nichtlineare Optimierung. \item Sind alle Funktionen linear $\rightarrow $ lineare Optimierung. \item \noindent Ist $f$ eine konvexe Funktion und $M$ eine konvexe Menge $\rightarrow $ konvexe Optimierung. \item $M:=\left\{ x\in \R ^{n}\, |\, h_{i}\left(x\right)=0,g_{j}\left(x\right)\geq 0,i\in I,j\in J\right\} $ und $\left|I\cup J\right|=\infty \, \rightarrow $ semiinfinite Optimierung. \item $X=\R ^{n}$ und $M$ ist eine diskrete Punktmenge $\rightarrow $ diskrete Optimierung. \end{enumerate} \pagebreak \section{Eigenschaften konvexer Funktionen und konvexer Optimierungsprobleme (\cite{1})} \subsection{Eigenschaften konvexer Funktionen} \begin{description} \item [Definition~2.1](Konvexität einer Menge) \begin{description} \item [$M$]heißt konvexe Menge, wenn $\forall x,y\in M,x\neq y$ gilt: $\lambda x+\left(1-\lambda \right)y\in M$ für alle $\lambda \in \left[0,1\right]$. \end{description} \end{description} Es sei $M\subseteq \R ^{n}$ konvex, nicht leer und $f:M\rightarrow \R $. \begin{description} \item [Definition~2.2](Konvexität einer Funktion) \begin{enumerate} \item $f$ heißt (streng) konvex auf $M$, wenn gilt:\[ f\left(\lambda x+\left(1-\lambda \right)y\right)\leq \left(<\right)\lambda f\left(x\right)+\left(1-\lambda \right)f\left(y\right),\, \forall x,y\in M,\, \lambda \in \left[0,1\right]\] \item $f$ heißt (streng) konkav auf $M$, gdw. $-f$ konvex auf $M$ ist. \end{enumerate} \item [Definition~2.3]~ \begin{enumerate} \item Interior$M\, \left(\textrm{int}M\right)$ ist die Menge aller Punkte $x_{0}\in M$, für die ein $\varepsilon >0$ ex., so daß $U_{\varepsilon }\left(x_{0}\right):=\left\{ x\in \R ^{n}\left|\left\Vert x-x_{0}\right\Vert <\varepsilon \right.\right\} $ ganz in $M$ liegt. \item RelativInterior$M\, \left(\textrm{relint}M\right)$ ist die Menge aller Punkte $x_{0}\in M$ mit $U_{\varepsilon }\left(x_{0}\right)\cap \textrm{aff}M\subseteq M$. \item aff$M$ ist der kleinste affine Unterraum (bzgl. Dimension), der $M$ enthält. \end{enumerate} \item [Satz~2.1]~ Seien $M\subseteq \R ^{n}$ konvex und $f:M\rightarrow \R $ konvex. Dann ist $f$ auf relint$M$ stetig. \item [Definition~2.4]~ \begin{enumerate} \item epi$\left(f\right):=\left\{ \left(x,a\right)\in M\times \R \left|f\left(x\right)\leq a\right.\right\} $ heißt Epigraph von $f$. \item $f^{c}:=\left\{ x\in M\left|f\left(x\right)\leq c\right.\right\} ,\, c\in \R $ heißt untere Niveaumenge. \end{enumerate} \item [Satz~2.2]~ Sei $M$ eine konvexe Teilmenge des $\R ^{n}$ \begin{enumerate} \item $f:M\rightarrow \R $ ist konvex auf $M$, gdw. epi$\left(f\right)$ konvex ist. \item Wenn $f$ konvex auf $M$ ist, so ist $f^{c}$ konvex für alle $c\in \R $. \item Sind $f,g:M\rightarrow \R $ konvex, so sind auch $h_{1}\left(x\right):=f\left(x\right)+g\left(x\right)$ und $h_{2}\left(x\right):=\sup \left\{ f\left(x\right),g\left(x\right)\right\} $ konvex. \item Jensens'sche Ungleichung: $f$ konvex auf $M$\\ \[ f\left(\sum _{i=1}^{n}\lambda _{i}x_{i}\right)\leq \sum _{i=1}^{n}\lambda _{i}f\left(x_{i}\right),\, \forall x_{i}\in M,\, \lambda _{i}\geq 0,\, \sum \lambda _{i}=1\] \end{enumerate} \item [Satz~2.3]~ Sei $f\in C^{1}\left(\R ^{n},\R \right)$. Dann ist $f$ (streng) konvex auf $\R ^{n}$ gdw. $\forall x,y\in \R ^{n}$ gilt:\[ f\left(y\right)-f\left(x\right)\geq \left(>\right)Df\left(x\right)\left(y-x\right).\] \begin{description} \item [Bew.:]$\left(\Rightarrow \right):$ Sei $\phi \left(\lambda \right):=f\left(x+\lambda \left(y-x\right)\right),\lambda \in \left[0,1\right]\, \Rightarrow \, \phi '\left(\lambda \right)=Df\left(x+\lambda \left(y-x\right)\right)\cdot \left(y-x\right)$ Taylor um $0:\, \phi \left(\lambda \right)=\phi \left(0\right)+\lambda \phi '\left(0\right)+o\left(\lambda \right)$ (Def.: $o:\, \R \rightarrow \R $ stetig in $0,\, \frac{o\left(\left|\lambda \right|\right)}{\lambda }\stackrel{\lambda \rightarrow 0}{\rightarrow }0$) Konv.: \begin{eqnarray*} \left(1-\lambda \right)f\left(x\right)+\lambda f\left(y\right) & \geq & f\left(\left(1-\lambda \right)x+\lambda y\right)\\ & = & f\left(x+\left(y-x\right)\cdot \lambda \right)=\phi \left(\lambda \right)\\ & = & f\left(x\right)+\lambda \cdot Df\left(x\right)\left(y-x\right)+o\left(\lambda \right)\\ \Rightarrow -\lambda f\left(x\right)+\lambda f\left(y\right) & \geq & \lambda Df\left(x\right)\left(y-x\right)+o\left(\lambda \right)\\ \Rightarrow \, f\left(y\right)-f\left(x\right) & \geq & Df\left(x\right)\left(y-x\right)+\underbrace{\frac{o\left(\lambda \right)}{\lambda }}_{\stackrel{\lambda \rightarrow 0^{+}}{\rightarrow }0} \end{eqnarray*} $\left(\Leftarrow \right)$ Mit $\lambda \in \left(0,1\right)$ und $x:=\lambda y+\left(1-\lambda \right)z$ folgt aus $\left(\Rightarrow \right)\, \forall y,z\in \R ^{n}:$\begin{eqnarray*} f\left(y\right)-f\left(x\right) & \geq & Df\left(x\right)\left(y-x\right)\\ f\left(z\right)-f\left(x\right) & \geq & Df\left(x\right)\left(z-x\right)\\ \stackrel{+}{\Rightarrow }\lambda f\left(y\right)+\left(1-\lambda \right)f\left(z\right)-f\left(x\right) & \geq & Df\left(x\right)\underbrace{\left[\lambda \left(y-x\right)+\left(1-\lambda \right)\left(z-x\right)\right]}_{=0} \end{eqnarray*} \end{description} \item [Satz~2.4]~ Sei $f\in C^{2}\left(\R ^{n},\R \right)$. $f$ ist konvex, gdw. $D^{2}f\left(x\right)$ positiv semidefinit $\forall x\in \R ^{n}$. \begin{description} \item [Bew.:]$\left(\Leftarrow \right):$ Seien $x,y\in \R ^{n}$ bel. Taylor:\begin{eqnarray*} f\left(y\right) & = & f\left(x\right)+Df\left(x\right)\left(y-x\right)+\frac{1}{2}\left(y-x\right)^{T}D^{2}f\left(x\right)\left(y-x\right)\\ z & = & x+\Theta \left(y-x\right),\, \Theta \in \left(0,1\right) \end{eqnarray*} \begin{description} \item [$D^{2}f\left(z\right)$]ist pos. semidef. $\forall x,y\in \R ^{n}$\begin{eqnarray*} \Rightarrow \, \left(y-x\right)^{T}D^{2}f\left(x\right)\left(y-x\right) & \geq & 0\\ \Rightarrow \, f\left(y\right)-f\left(x\right) & \geq & Df\left(x\right)\left(y-x\right)\, \stackrel{S.2.3}{\Rightarrow }\, \textrm{Beh}. \end{eqnarray*} \item [$\left(\Rightarrow \right)$]siehe Ende vom 4. Kapitel \end{description} \end{description} \item [Corollar~2.1]~ Seien $f\in C^{2}\left(\R ^{n},\R \right)$ und $D^{2}f\left(x\right)$ positiv definit $\forall x\in \R ^{n}$. Dann ist $f$ streng konvex.\\ Die Umkehrung ist im allgemeinen nicht gültig. \end{description} \subsection{Eigenschaften konvexer Optimierungsprobleme} \begin{description} \item [$\left(P\right)$]$\min \left\{ f\left(x\right)\left|x\in M\right.\right\} $ $M:=\left\{ x\in \R ^{n}\left|h_{i}\left(x\right)=0,\, g_{j}\left(x\right)\leq 0,\, i\in I=\left\{ 1,\ldots ,m\right\} ,\, j\in J=\left\{ 1,\ldots ,s\right\} \right.\right\} $\\ $h_{i}\left(x\right):=a_{i}^{T}x=b_{i},\, i=1,\ldots ,m$ affin-lineare Funktion\\ $g_{j}\left(x\right),\, j=1,\ldots ,s$ konvexe Funktion und $f$ konvex\\ $\Rightarrow $ $M$ ist eine konvexe Menge \end{description} konvexe Optimierung: $\min \left\{ f\left(x\right)\left|x\in M\right.\right\} $, $f$ konvex, $M$ konvex\\ $\Rightarrow $ dann sind die folgenden Probleme ebenfalls konvexe Probleme: \begin{enumerate} \item $\min \left\{ f\left(x\right)\left|h_{i}\left(x\right)=0,\, g_{j}\left(x\right)\geq 0,\, i\in I,\, j\in J\right.\right\} $ \\ mit $f$ konvex, $g_{j}$ konkav, $h_{i}$ affin-linear \item $\max \left\{ f\left(x\right)\left|h_{i}\left(x\right)=0,\, g_{j}\left(x\right)\leq 0,\, i\in I,\, j\in J\right.\right\} $\\ mit $f$ konkav, $g_{j}$ konvex, $h_{i}$ affin-linear \item $\max \left\{ f\left(x\right)\left|h_{i}\left(x\right)=0,\, g_{j}\left(x\right)\geq 0,\, i\in I,\, j\in J\right.\right\} $\\ mit $f$ konkav, $g_{j}$ konkav, $h_{i}$ affin-linear \end{enumerate} \begin{description} \item [$\left(P\right)$]$\min \left\{ f\left(x\right)\left|x\in M\right.\right\} ,\, M\subseteq \R ^{n}$ konvex, $f$ konvex \item [Satz~2.5]~ Jeder lokale Minimalpunkt von $\left(P\right)$ ist globaler Minimalpunkt. \begin{description} \item [Bew.:]Sei $\bar{x}$ lok. Min.pkt. und kein glob. Min.pkt. $\rightarrow \, \exists y\in M:f\left(y\right)0$ fest. Bilden $\phi \left(t\right):=f\left(0,\ldots ,t\cdot \tilde{x}_{i^{*}},0\ldots ,0\right).$ Taylor um $t=0:$\begin{eqnarray*} \phi \left(t\right) & = & \phi \left(0\right)+t\cdot \phi '\left(0\right)+o\left(t\right)=\phi \left(0\right)+t\left(\phi '\left(0\right)+\frac{o\left(t\right)}{t}\right),\, t>0\\ \phi '\left(0\right) & = & \frac{\partial f}{\partial x_{i}^{*}}\left(0\right)<0\\ \rightarrow \, \phi '\left(0\right) & < & \frac{1}{2}\phi '\left(0\right) \end{eqnarray*} Da $\frac{o\left(t\right)}{t}\stackrel{t\rightarrow 0}{\rightarrow }0,$ ex. ein $\bar{t}>0,$ so daß \begin{eqnarray*} \phi '\left(0\right)+\frac{o\left(t\right)}{t} & \leq & \frac{1}{2}\phi '\left(0\right)\, \forall t\in \left(0,\bar{t}\right)\\ \rightarrow \, \phi \left(t\right) & \leq & \phi \left(0\right)+\frac{1}{2}\phi '\left(0\right)\cdot t\, \forall t\in \left(0,\bar{t}\right)\\ \stackrel{\phi \left(0\right)<0}{\rightarrow }\, \phi \left(t\right) & < & \phi \left(0\right)\, \forall t\in \left(0,\bar{t}\right)\\ \rightarrow \, f\left(0,\ldots ,0,t\cdot \tilde{x}_{i^{*}},0,\ldots ,0\right) & < & f\left(0\right)\, \forall t\in \left(0,\bar{t}\right) \end{eqnarray*} und $\left(0,\ldots ,0,t\cdot \tilde{x}_{i^{*}},0,\ldots ,0\right)\in U\cap \mathbb{H}^{n}\, \forall t\in \left(0,\bar{t}\right).$ Wid. zu $0$ ist lok. Min.pkt. \end{description} \item [Satz~3.3]~ Es sei $f\in C^{1}\left(\R ^{n},\R \right)$ und $0$ lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|\R ^{p}\times \mathbb{H}^{q}\right.\right\} ,n=p+q$. Dann gilt:\[ \frac{\partial f}{\partial x_{i}}\left(0\right)=0,\, i=1,\ldots ,p\qquad \frac{\partial f}{\partial x_{j}}\geq 0,\, j=p+1,\ldots ,n\] \item [Bezeichnung]~ $B\left(\bar{x},r\right):=\left\{ x\in \R ^{n}\left|\left\Vert x-\bar{x}\right\Vert \leq r\right.\right\} $ mit $r>0,\, \bar{x}\in \R ^{n}$ fest \item [Satz~3.4]~ Seien $f\in C^{1}\left(\R ^{n},\R \right)$ und $\frac{\partial f}{\partial x_{i}}\left(0\right)>0,\, i=1,\ldots ,n$. Dann gibt es eine Umgebung $U$ von $0$, und $\gamma >0$, so daß\[ f\left(x\right)\geq f\left(0\right)+\gamma \sum _{i=1}^{n}x_{i},\, \forall x\in U\cap \mathbb{H}^{n}\] Insbesondere ist $0\in \mathbb{H}^{n}$ ein strikter lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|x\in \mathbb{H}^{n}\right.\right\} $. \begin{description} \item [Bew.:]Letzte Aussage ist klar, da $\sum _{i=1}^{n}\bar{x}_{i}>0,$ falls $\bar{x}\in U\cap \mathbb{H}^{n}$ und $\bar{x}\neq 0.$ Da $f\in C^{1}\left(\R ^{n},\R \right),$ sind $\frac{\partial f}{\partial x_{i}},i=1,\ldots ,n,$ stetige Funktionen. Wegen $\frac{\partial f}{\partial x_{i}}\left(0\right)>0,i=1,\ldots ,n,$ gibt es ein $r>0$ und $\gamma _{i}>0,$ so daß $\frac{\partial f}{\partial x_{i}}\left(0\right)\geq \gamma _{i}>0\, \forall x\in B\left(0,r\right).$ Setze \[ \gamma :=\min _{i=1,\ldots ,n}\gamma _{i}\, \Rightarrow \, \gamma >0.\] Hauptsatz der Integral- und Diff.rechnung: \begin{eqnarray*} f\left(x\right)-f\left(0\right) & = & \int _{0}^{1}\frac{d}{dt}f\left(tx\right)dt=\int _{0}^{1}\frac{d}{dt}f\left(tx_{1},\ldots ,tx_{n}\right)dt\\ & = & \int _{0}^{1}\sum _{i=1}^{n}\frac{\partial f}{\partial x_{i}}\left(tx\right)x_{i}dt\\ & = & \sum _{i=1}^{n}\left[\int _{0}^{1}\frac{\partial f}{\partial x_{i}}\left(tx\right)dt\right]x_{i}\\ & \geq & \sum _{i=1}^{n}\left[\int _{0}^{1}\gamma dt\right]x_{i}\\ & = & \gamma \cdot \sum _{i=1}^{n}x_{i}\, \Rightarrow \, \textrm{Beh}. \end{eqnarray*} \end{description} \end{description} \subsection{Optimalitätsbedingung 2. Ordnung} \begin{description} \item [Satz~3.5]~ Es sei $f\in C^{2}\left(\R ^{n},\R \right)$ und $\bar{x}\in \R ^{n}$ ein lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|x\in \R ^{n}\right.\right\} $. Dann gilt $Df\left(\bar{x}\right)=0$ und $D^{2}f\left(\bar{x}\right)$ ist positiv semidefinit. \begin{description} \item [Bew.:]Aus Satz 3.1 folgt $Df\left(\bar{x}\right)=0.$ Ann.: $D^{2}f\left(\bar{x}\right)$ ist nicht pos. semidefinit. Dann gibt es $\xi \in \R ^{n}$ mit $\xi ^{T}D^{2}f\left(\bar{x}\right)\xi =:\alpha <0.$ $\phi \left(t\right):=f\left(\bar{x}+t\xi \right).$ Taylor für $t=0:\, \phi \left(t\right)=\phi \left(0\right)+t\cdot \phi '\left(0\right)+\frac{1}{2}t^{2}\phi '\left(0\right)+o\left(t^{2}\right)$ mit $\frac{o\left(t^{2}\right)}{t^{2}}\stackrel{t\rightarrow 0}{\rightarrow }0.$ Es gilt \begin{eqnarray*} \phi '\left(t\right) & = & Df\left(\bar{x}+t\xi \right)\xi =\xi ^{T}D^{T}f\left(\bar{x}+t\xi \right)\, \stackrel{Df\left(\bar{x}\right)=0}{\rightarrow }\phi '\left(0\right)=0\\ \rightarrow \, \phi ''\left(t\right) & = & \xi ^{T}D^{2}f\left(\bar{x}+t\xi \right)\xi =\alpha <0\\ \rightarrow \, \phi \left(t\right) & = & \phi \left(0\right)+t^{2}\left[\frac{1}{2}\alpha +\frac{o\left(t^{2}\right)}{t^{2}}\right],\, t\neq 0\\ \lim _{t\rightarrow 0}\frac{o\left(t^{2}\right)}{t^{2}}=0 & \Rightarrow & \exists \bar{t}>0:\, \frac{1}{2}\alpha +\frac{o\left(t^{2}\right)}{t^{2}}\leq \frac{1}{4}\alpha \, \forall t\in \left(0,\bar{t}\right)\\ \rightarrow \, \phi \left(t\right) & \leq & \phi \left(0\right)+\frac{1}{4}t^{2}\alpha \stackrel{\alpha <0}{<}\phi \left(0\right)\, \forall t\in \left(0,\bar{t}\right)\\ \rightarrow \, f\left(\bar{x}+t\xi \right) & < & f\left(\bar{x}\right)\, \forall t\in \left(0,\bar{t}\right) \end{eqnarray*} Wid. zu $\bar{x}$ lok. Min.pkt. \end{description} \item [Satz~3.6]~ Es seien $f\in C^{2}\left(\R ^{n},\R \right),\, n=p+q$ und $0\in \R ^{p}\times \mathbb{H}^{q}$ ein lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|x\in \R ^{p}\times \mathbb{H}^{q}\right.\right\} $. Dann gilt:\begin{eqnarray*} \frac{\partial f}{\partial x_{i}}\left(0\right)=0,\, i=1,\ldots ,p & & \left(\frac{\partial ^{2}f}{\partial x_{i}\partial x_{j}}\left(0\right)\right)_{i,j=1,\ldots ,p}\textrm{ positiv semidefinit}\\ \frac{\partial f}{\partial x_{j}}\left(0\right)\geq 0,\, j=p+1,\ldots ,n & & \end{eqnarray*} \item [Satz~3.7]~ Es seien $f\in C^{2}\left(\R ^{n},\R \right),\, n=p+q$ und die folgenden Bedingungen erfüllt: \begin{enumerate} \item $\frac{\partial f}{\partial x_{i}}\left(0\right)=0,\, i=1,\ldots ,p,\quad \left(\frac{\partial ^{2}f}{\partial x_{i}\partial x_{j}}\left(0\right)\right)$ positiv definit \item $\frac{\partial f}{\partial x_{j}}\left(0\right)>0,\, j=p+1,\ldots ,n$ \end{enumerate} Dann existiert eine Umgebung $U$ von $0$ und ein $\gamma >0$, so daß\[ f\left(x\right)\geq f\left(0\right)+\gamma \left\Vert x\right\Vert ^{2},\, \forall x\in U\cap \left(\R ^{p}\times \mathbb{H}^{q}\right)\] Insbesondere ist $0\in \R ^{p}\times \mathbb{H}^{q}$ ein strikter lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|x\in \R ^{p}\times \mathbb{H}^{q}\right.\right\} $. \item [Lemma~3.1]~ Es sei $M\subseteq \R ^{n}$ kompakt, nicht leer und $f\in C^{0}\left(\R ^{n}\times \R ^{m},\R \right),\, z=\left(x,y\right),\, x\in \R ^{n},\, y\in \R ^{m}$ und\[ \phi \left(x\right):=\min _{y\in M}f\left(x,y\right)\quad \tilde{\phi }\left(x\right):=\max _{y\in M}f\left(x,y\right)\] Dann sind $\phi $ und $\tilde{\phi }$ stetig auf $M$. \begin{description} \item [Bew.:]Wir zeigen die Stetigkeit von $\phi :$ Sei $\left\{ x^{k}\right\} $ bel. mit $x^{k}\rightarrow \bar{x}.$ z.z.: $\phi \left(x^{k}\right)\rightarrow \phi \left(\bar{x}\right)$ Nach dem Satz von Weierstraß ex. zu jedem $x^{k}$ ein $y^{k}\in M$ mit $\phi \left(x^{k}\right)=f\left(x^{k},y^{k}\right)$ (da $M$ kompakt). Ann.: $\phi \left(x^{k}\right)\not \rightarrow \phi \left(\bar{x}\right)$ $\rightarrow \left(*\right)\, \exists \varepsilon >0$ und Teilfolge $\left\{ x^{k_{i}}\right\} \subseteq \left\{ x^{k}\right\} ,$ so daß $\phi \left(x^{k_{i}}\right)\not \in \left(\phi \left(\bar{x}\right)-\varepsilon ,\phi \left(\bar{x}\right)+\varepsilon \right),i\in \N $ $\left\{ y^{k_{i}}\right\} $ hat einen Häufunktspunkt $\bar{y}\in M,$ da $M$ kompakt. o.B.d.A. $y^{k_{i}}\rightarrow \bar{y}$ (ansonsten wählen wir eine geeignete Teilfolge) $\Rightarrow \, \left(x^{k_{i}},y^{k_{i}}\right)\rightarrow \left(\bar{x},\bar{y}\right)\, \Rightarrow $(Stetigkeit) $f\left(x^{k_{i}},y^{k_{i}}\right)\rightarrow f\left(\bar{x},\bar{y}\right).$ Andererseits folgt aus $\left(*\right):\, f\left(\bar{x},\bar{y}\right)\neq \phi \left(\bar{x}\right)$ $\rightarrow \, \exists \tilde{y}\in M$ und $\alpha >0$ mit $f\left(\bar{x},\tilde{y}\right)\leq f\left(\bar{x},\bar{y}\right)-\alpha $ ($\tilde{y}$ realisiert $\min _{y\in M}f\left(\bar{x},y\right)$) $\rightarrow \, \exists i_{0}$ mit $f\left(x^{k_{i}},\tilde{y}\right)\leq f\left(\bar{x},\bar{y}\right)-\frac{\alpha }{2}$ für $i\geq i_{0}.$ Wegen $f\left(x^{k_{i}},y^{k_{i}}\right)\leq f\left(x^{k_{i}},\tilde{y}\right)$ gilt: $f\left(x^{k_{i}},y^{k_{i}}\right)\leq f\left(\bar{x},\bar{y}\right)-\frac{\alpha }{2}$ für $i\geq i_{0}.$ Wid. zu $f\left(x^{k_{i}},y^{k_{i}}\right)\rightarrow f\left(\bar{x},\bar{y}\right).$ \end{description} \item [Lemma~3.2]~ Es sei $x\in \R ^{p}$ und $y\in \R ^{q}$ und $A:\left(x,y\right)\rightarrow A\left(x,y\right)$ eine stetige Abbildung von $\R ^{p}\times \R ^{q}$ in den linearen Raum der symmetrischen $p\times p$-Matrizen (d.h. jedes Matrixelement $a_{ij}\left(x,y\right)$ ist eine stetige Funktion in $\left(x,y\right)$ ). Weiterhin sei $A\left(0,0\right)$ positiv definit. Dann gibt es eine Umgebung $U\subset \R ^{p}\times \R ^{q}$ von $\left(0,0\right)$ um $\gamma >0$, so daß\[ x^{T}A\left(x,y\right)x\geq \gamma \left\Vert x\right\Vert ^{2},\, \forall \left(x,y\right)\in U\] \begin{description} \item [Bew.:]Setze $\eta \left(x,y\right):=x^{T}A\left(x,y\right)x.$ \begin{enumerate} \item $x=0,\eta \left(0,y\right)=0$ trivial für jedes $\gamma $ \item $x\neq 0.$ Dann gilt \begin{eqnarray*} \eta \left(x,y\right) & = & \left[\left(\frac{x}{\left\Vert x\right\Vert }\right)^{T}A\left(x,y\right)\left(\frac{x}{\left\Vert x\right\Vert }\right)\right]\left\Vert x\right\Vert ^{2}\\ & \geq & \min _{\left\Vert \xi \right\Vert =1}\xi ^{T}A\left(x,y\right)\xi \cdot \left\Vert x\right\Vert ^{2} \end{eqnarray*} $\rightarrow $(Lemma 3.1) $\phi \left(x,y\right):=\min _{\left\Vert \xi \right\Vert =1}\xi ^{T}A\left(x,y\right)\xi $ stetig. Es ist $A\left(0,0\right)$ pos. def. $\Rightarrow \, \phi \left(0,0\right)=c>0$ $\phi $ stetig $\rightarrow \, \phi \left(x,y\right)\geq \frac{c}{2}>0\, \forall \left(x,y\right)$ in einer Umgebung $U\subseteq \R ^{p}\times \R ^{q}$ von $\left(0,0\right).$ Setze $\gamma :=\frac{c}{2}.$ \end{enumerate} \end{description} \item [Lemma~3.3]~ Es sei $g:\R ^{n}\rightarrow \R $ stetig und $g\left(0\right)>0$. Dann existiert zu jedem $\gamma >0$ eine Umgebung $U_{\gamma }\subset \R ^{n}$ von $0$, so daß $\forall i=1,\ldots ,n$ gilt:\[ x_{i}g\left(x\right)\geq \gamma x_{i}^{2},\, \forall x\in U_{\gamma }\textrm{ mit }x_{i}\geq 0\] \begin{description} \item [Bew.:]Sei $\delta >0$ bel. Wir betrachten $\phi _{i}\left(x\right):=g\left(x\right)-\delta x_{i},i=1,\ldots ,n.$ $\phi _{i}$ stetig auf $\R ^{n}.$ Außerdem gilt: $\phi _{i}\left(0\right)=g\left(0\right)>0\, \forall i=1,\ldots ,n.$ $\rightarrow \, \exists $ Umgebung $U_{\delta }$ von $0$ mit $\phi _{i}\left(x\right)>0\, \forall i=1,\ldots ,n\, \forall x\in U_{\delta }$ $\rightarrow \, x_{i}\phi _{i}\left(x\right)>\delta ^{2}x_{i}^{2}\, \forall x\in U_{\delta }$ mit $x_{i}\geq 0.$ \end{description} \item [Bew.~S.3.7:]Es genügt, $\exists U\left(0\right),\gamma :\, f\left(x\right)\geq f\left(0\right)+\gamma \left\Vert x\right\Vert ^{2}\, \forall x\in U\cap \left(\R ^{p}\times \mathbb{H}^{q}\right)$ zu zeigen. Hauptsatz der Diff.- und Int.rechnung:\begin{eqnarray*} f\left(x\right)-f\left(0\right) & = & \int _{0}^{1}\frac{d}{dt}f\left(tx\right)dt\\ & = & \sum _{i=1}^{n}x_{i}g_{i},\, g_{i}\left(x\right)=\int \frac{\partial g_{i}}{\partial x_{i}}\left(tx\right)dt,\, i=1,\ldots ,n \end{eqnarray*} $f\in C^{2}\, \Rightarrow \, g_{i}\in C^{1},i=1,\ldots ,n$ Vor. 1 $\Rightarrow \, g_{i}\left(0\right)=0,\, i=1,\ldots ,p.$ Hauptsatz der Diff.- und Int.rechnung:\begin{eqnarray*} g_{i}\left(x\right) & = & \int _{0}^{1}\frac{d}{dt}g_{i}\left(tx\right)dt\\ & = & \sum _{j=1}^{n}x_{j}h_{i,j}\left(x\right),\, h_{i,j}\left(x\right)=\int _{0}^{1}\frac{\partial g_{i}}{\partial x_{j}}\left(x\right)dt,\, h_{i,j}\in C^{0},i=1,\ldots ,p\\ \Rightarrow \, f\left(x\right) & = & f\left(0\right)+\sum _{i=1}^{p}\sum _{j=1}^{n}x_{i}x_{j}h_{i,j}\left(x\right)+\sum _{j=p+1}^{n}x_{j}g_{j}\left(x\right) \end{eqnarray*} Sortierung $\tilde{h}_{i,j}=\frac{1}{2}\left(h_{i,j}+h_{j,i}\right),\, \tilde{g}_{j}\left(x\right)=g_{j}\left(x\right)+\sum _{i=1}^{p}h_{i,j}\left(x\right)x_{i}$\begin{eqnarray*} \Rightarrow \, f\left(x\right) & = & f\left(0\right)+\underbrace{\sum _{i,j=1}^{p}x_{i}x_{j}\tilde{h}_{i,j}\left(x\right)}_{\geq \gamma \left\Vert x\right\Vert ^{2}\, \left(\textrm{L}.3.2\right)}+\underbrace{\sum _{j=p+1}^{n}x_{j}\tilde{g}_{j}\left(x\right)}_{>\gamma \left\Vert x\right\Vert \, \left(\textrm{L}.3.3.\right)} \end{eqnarray*} $\hat{g}_{j}\left(0\right)=\frac{\partial f}{\partial x_{j}}\left(0\right)>0$ nach Vor. 2. \end{description} \section{Optimalitätsbedingungen für allg. Optimierungsprobleme mit Nebenbedingungen} \subsection{Optimalitätsbedingungen für nichtlineare Optimierungsprobleme} \begin{description} \item [$(P)$]$\min \left\{ f\left(x\right)\left|x\in M\right.\right\} ,\, f:\R ^{n}\rightarrow \R ,\, M\subseteq \R ^{n}$ $M=M\left[h,g\right]=\left\{ x\in \R ^{n}\left|h_{i}\left(x\right)=0,\, i\in I,\, g_{j}\left(x\right)\geq 0,\, j\in J\right.\right\} $ $h=\left(\begin{array}{ccc} h_{1} & \cdots & h_{m}\end{array} \right)^{T},\, g=\left(\begin{array}{ccc} g_{1} & \cdots & g_{s}\end{array} \right)^{T},\, I=\left\{ 1,\ldots ,m\right\} ,\, J=\left\{ 1,\ldots ,s\right\} $ $J_{0}\left(x\right):=\left\{ j\in J\left|g_{j}\left(x\right)=0\right.\right\} $ Indexmenge der aktiven Restriktionen \item [Satz~4.1]~ Es sei $h_{i},\, g_{j}\in C^{0}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$. Dann ist $M$ eine abgeschlossene Menge, und es gilt:\\ Zu jedem $\bar{x}\in M$ gibt es eine Umgebung $U$ von $\bar{x}$, so daß:\[ J_{0}\left(x\right)\subseteq J_{0}\left(\bar{x}\right),\, \forall x\in U\cap M\] \item [Definition~4.1]~ Es sei $h_{i},\, g_{j}\in C^{1}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$ und $\bar{x}\in M$. \begin{enumerate} \item Die lineare Unabhängigkeitsbedingung (LICQ) ist in $\bar{x}\in M$ erfüllt, wenn die Vektoren $Dh_{i}\left(\bar{x}\right),\, i\in I,\, Dg_{j}\left(\bar{x}\right),\, j\in J_{0}\left(\bar{x}\right)$ linear unabhängig sind. Falls die LICQ in jedem Punkt von $M$ erfüllt ist, so sagt man die LICQ ist auf $M$ erfüllt. \item Die Mangasarian-Fromoritz-Bedingung (MFCQ) ist in $\bar{x}\in M$ erfüllt, falls: \begin{enumerate} \item $Dh_{i}\left(x\right),\, i\in I$ linear unabhängig \item $\exists \xi \in R^{n}$ mit $Dh_{i}\left(\bar{x}\right)\xi =0,\, i\in I,\, Dg_{j}\left(\bar{x}\right)\xi >0,\, j\in J_{0}\left(\bar{x}\right)$ \end{enumerate} \end{enumerate} \item [Bemerkung~4.1]~ LICQ $\rightarrow $ MFCQ \item [Lemma~4.1]~ Wenn LICQ in $\bar{x}\in M$ erfüllt ist, so gibt es eine Umgebung $U$ von $\bar{x}$, so daß LICQ erfüllt ist $\forall x\in U\cap M$. \item [Satz~4.2]~ Es sei $h_{i},\, g_{j}\in C^{k}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$ mit $k>1$ und in $\bar{x}\in M$ die LICQ erfüllt ($J_{0}\left(\bar{x}\right)=\left\{ 1,\ldots ,p\right\} $). Dann existiert eine Umgebung $U$ von $\bar{x}$ und $V$ von $0\in \R ^{n}$ und ein $C^{k}$-Diffeomorphismus $\phi :U\rightarrow V$, so daß\[ \phi \left(\bar{x}\right)=0\textrm{ und }\phi \left(U\cap M\right)=V\cap \left(\left\{ 0_{m}\right\} \times \mathbb{H}^{p}\times \R ^{n-m-p}\right),\, 0_{m}\in \R ^{m}\] \[ \phi \left(x\right)=\left(\phi _{1}\left(x\right),\ldots ,\phi _{n}\left(x\right)\right),\, x\in \R ^{n},\, \phi _{i}\left(x\right)\in C^{k}\left(\R ^{n},\R \right),\, i=1,\ldots ,n\] \begin{description} \item [Bew.:]LICQ $\rightarrow \, D^{T}h_{i}\left(\bar{x}\right),i=1,\ldots ,m,\, D^{T}g_{j}\left(\bar{x}\right),j=1,\ldots ,p$ lin. unabh. und $m+p\leq n.$ Basisergänzungssatz $\rightarrow \, \exists \xi ^{m+p+1},\ldots ,\xi ^{n}\in \R ^{n},$ so daß wir zu einer Basis im $\R ^{n}$ ergänzen. $y=\phi \left(x\right),\phi \in C^{k}\left(\R ^{n},\R ^{m}\right)$ wie folgt:\begin{eqnarray*} y_{1}=h_{1}\left(x\right), & y_{m+1}=g_{1}\left(x\right), & y_{m+p+1}=\xi ^{m+p+1^{T}}\left(x-\bar{x}\right)\\ \vdots & \vdots & \vdots \\ y_{m}=h_{m}\left(x\right), & y_{m+p}=g_{p}\left(x\right), & y_{n}=\xi ^{n^{T}}\left(x-\bar{x}\right) \end{eqnarray*} Es gilt $\phi \left(\bar{x}\right)=0$ und die Jacobi-Matrix \[ D\phi \left(\bar{x}\right)=\left[\begin{array}{ccccccccc} D^{T}h_{1}\left(\bar{x}\right) & \cdots & D^{T}h_{m}\left(\bar{x}\right) & D^{T}g_{1}\left(\bar{x}\right) & \cdots & D^{T}g_{p}\left(\bar{x}\right) & \xi ^{m+p+1} & \cdots & \xi ^{n}\end{array} \right]^{T}\] ist regulär. Inversentheorem $\Rightarrow $ $\exists U,V$ von $\bar{x},0\in \R ^{n},$ so daß $\phi :U\rightarrow V$ ein $C^{k}$-Diff. Durch eventuelle Verkleinerung von $U$ kann man $J_{0}\left(x\right)\subseteq J_{0}\left(\bar{x}\right)\forall x\in U\cap M$ erreichen. $U\cap M$ wird in $y$-Koo. wie folgt beschrieben: \begin{eqnarray*} y_{1}=\ldots =y_{m} & = & 0\\ y_{m+1},\ldots ,y_{m} & > & 0\\ y_{m+p+1},\ldots ,y_{n} & \in & \R . \end{eqnarray*} \end{description} \item [Bemerkung~4.2]~ Den $C^{k}$-Diffeomorphismus $\phi $ berechnet man als Standard-Diffeomorphismus. Mit Hilfe von $\phi $ werden die nichtlinearen Restriktionen in lineare Restriktionen überführt. Der nichtlineare Teil von $M$ ist in $\phi $ versteckt. $\phi $ ist eine lokale Koordinatentransformation. \item [Lemma~4.2]~ Es sei $f\in C^{1}\left(\R ^{n},\R \right)$ und die LICQ in $\bar{x}\in M$ erfüllt, $\phi $ der Standarddiffeomorphismus. Dann existieren eindeutig bestimmte Zahlen $\bar{\lambda }_{i},\, i=1,\ldots ,m,\, \bar{\mu }_{j},\, j=1,\ldots ,p,\, \bar{\nu }_{r},\, r=p+1,\ldots ,m$ mit: \begin{enumerate} \item $Df\left(\bar{x}\right)=\sum _{i=1}^{m}\bar{\lambda }_{i}Dh_{i}\left(\bar{x}\right)+\sum _{j=1}^{p}\bar{\mu }_{j}Dg_{j}\left(\bar{x}\right)+\sum _{r=m+p+1}^{n}\bar{\nu }_{r}\xi ^{rT}$ \item $\bar{\lambda }_{i}=\frac{\partial }{\partial y_{i}}\left(f\circ \phi ^{-1}\left(0\right)\right),\, i=1,\ldots ,m$ $\bar{\mu }_{j-m}=\frac{\partial }{\partial y_{j}}\left(f\circ \phi ^{-1}\left(0\right)\right),\, j=m+1,\ldots ,p$ $\bar{\nu }_{r}=\frac{\partial }{\partial y_{r}}\left(f\circ \phi ^{-1}\left(0\right)\right),\, r=p+m+1,\ldots ,n$ \end{enumerate} \pagebreak \begin{description} \item [Bew.:]~ \begin{enumerate} \item $D^{T}h_{i}\left(\bar{x}\right),i=1,\ldots ,m,\, D^{T}g_{j}\left(\bar{x}\right),j=1,\ldots ,p,\, \xi ^{r},r=m+p+1,\ldots ,n$ bilden eine Basis. Daraus folgt insbesondere, daß die Zahlen $\bar{\lambda }_{i},\bar{\mu }_{j-m},\bar{\nu }_{r}$ eind. bestimmt sind. \item ~\begin{eqnarray*} \frac{\partial }{\partial y_{1}}\left(f\circ \phi ^{-1}\left(0\right)\right) & = & \left.\frac{\partial }{\partial y_{1}}\left(f\left(\phi _{1}^{-1}\left(y_{1},\ldots ,y_{n}\right),\ldots ,\phi _{n}^{-1}\left(y_{1},\ldots ,y_{n}\right)\right)\right)\right|_{y=0}\\ & = & Df\left(\bar{x}\right)\cdot D\phi ^{-1}\left(0\right)e^{1}\\ & = & Df\left(\bar{x}\right)\cdot \left(\begin{array}{ccc} \frac{\partial \phi _{1}^{-1}\left(0\right)}{\partial y_{1}} & \cdots & \frac{\partial \phi _{1}^{-1}\left(0\right)}{\partial y_{n}}\\ \vdots & & \vdots \\ \frac{\partial \phi _{n}^{-1}\left(0\right)}{\partial y_{1}} & \cdots & \frac{\partial \phi _{n}^{-1}\left(0\right)}{\partial y_{n}}\end{array} \right)\cdot \left(\begin{array}{c} 1\\ 0\\ \vdots \\ 0\end{array} \right)\\ & = & Df\left(\bar{x}\right)\cdot \left(\begin{array}{c} \frac{\partial \phi _{1}^{-1}\left(0\right)}{\partial y_{1}}\\ \vdots \\ \frac{\partial \phi _{n}^{-1}\left(0\right)}{\partial y_{1}}\end{array} \right)\\ & = & \sum _{i=1}^{n}\frac{\partial f\left(\bar{x}\right)}{\partial x_{i}}\cdot \frac{\partial \phi ^{-1}\left(0\right)}{\partial y_{1}} \end{eqnarray*} \end{enumerate} Wir setzen $D\phi ^{-1}\left(0\right)e^{1}=:\eta .$ Inversentheorem $\rightarrow \, e^{1}=D\phi \left(\bar{x}\right)\cdot \eta ,$ d.h. $Dh_{1}\left(\bar{x}\right)\eta =1,\, Dh_{2}\left(\bar{x}\right)\eta =0,\ldots ,\xi ^{n^{T}}\eta =0$\begin{eqnarray*} 1.\, \rightarrow \, Df\left(\bar{x}\right)\cdot \eta & = & \sum _{i=1}^{m}\bar{\lambda }_{i}Dh_{i}\left(\bar{x}\right)\cdot \eta +\sum _{j=1}^{p}\bar{\mu }_{j}Dg_{j}\left(\bar{x}\right)\cdot \eta +\sum _{r=m+p+1}^{n}\bar{\nu }_{r}\xi ^{r^{T}}\cdot \eta .\\ \rightarrow \, Df\left(\bar{x}\right)\cdot \eta & = & \bar{\lambda }_{1} \end{eqnarray*} Alle anderen Beziehungen analog. $\rightarrow $ Beh. \end{description} \item [Satz~4.3](Karush-Kuhn-Tucker-Satz) Es seien $f,h_{i},g_{j}\in C^{1}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$, LICQ in $\bar{x}\in M$ erfüllt, und $\bar{x}$ ein lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|x\in M\right.\right\} $. Dann gibt es $\bar{\lambda }_{i},\, \bar{\mu }_{j}\in \R ,\, i\in I,\, j\in J_{0}\left(\bar{x}\right)$, so daß \begin{enumerate} \item $Df\left(\bar{x}\right)=\sum _{i\in I}\bar{\lambda }_{i}Dh_{i}\left(\bar{x}\right)+\sum _{j\in J_{0}}\bar{\mu }_{j}Dg_{j}\left(\bar{x}\right)$ \item $\bar{\lambda }_{i},\, \bar{\mu }_{j}$ sind eindeutig bestimmt \item $\bar{\mu }_{j}\geq 0,\, j\in J_{0}\left(\bar{x}\right)$ \end{enumerate} \begin{description} \item [Bew.:]Standarddiff. $\phi \, \rightarrow \, \bar{x}$ lok. Min.pkt. für $\min \left\{ \left.f\left(x\right)\right|x\in M\right\} \, \Leftrightarrow \, 0=\phi \left(\bar{x}\right)$ lok. Min.pkt. für $\min \left\{ \left.f\circ \phi ^{-1}\left(y\right)\right|y\in \left\{ 0_{m}\right\} \times \mathbb{H}^{p}\times \R ^{n-m-p}\right\} .$ Nach Satz 3.3 gilt:\begin{eqnarray*} \frac{\partial }{\partial y_{r}}\left(f\circ \phi ^{-1}\left(0\right)\right) & = & 0,\, r=m+p+1,\ldots ,n\, \left(=\bar{\nu }_{r}\, \textrm{nach L}.4.2\right)\\ \frac{\partial }{\partial y_{j}}\left(f\circ \phi ^{-1}\left(0\right)\right) & \geq & 0,\, j=m+1,\ldots ,m+p\, \left(=\bar{\mu }_{j}\, \textrm{nach L}.4.2.\right) \end{eqnarray*} $\rightarrow \, \bar{\nu }_{r}=0,\bar{\mu }_{j}\geq 0.$ \end{description} \end{description} \pagebreak \begin{description} \item [KKT-System]~ Das System 4.3 a) und c) für beliebiges $x\in M$ heißt KKT-System und wird auch in folgender Weise geschrieben: \begin{lyxlist}{00.00.0000} \item [~]$Df\left(x\right)=\sum _{i\in I}\lambda _{i}Dh_{i}\left(x\right)+\sum _{j\in J}\mu _{j}Dg_{j}\left(x\right)$ \item [~]$h_{i}\left(x\right)=0,\, g_{j}\left(x\right)\geq 0,\, \mu _{j}\geq 0,\, i\in I,\, j\in J$ \item [~]$\mu _{j}g_{j}\left(x\right)=0,\, j\in J$ (Komplementaritätsbedingung) \end{lyxlist} \item [Definition~4.2]~ \begin{enumerate} \item $\left(\bar{x},\bar{\lambda },\bar{\mu }\right)$ bzw. $\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right),\, J_{0}=J_{0}\left(\bar{x}\right),\, \mu ^{J_{0}}=\left(\begin{array}{ccc} \bar{\mu }_{1} & \ldots & \bar{\mu }_{p}\end{array} \right)$ heißt KKT-Punkt. \item $\bar{x}\in M$ heißt stationärer Punkt, wenn $\left(\bar{\lambda },\bar{\mu }\right)\in \R ^{m}\times \R ^{s}$ bzw. $\left(\bar{\lambda },\bar{\mu }^{J_{0}}\right)\in \R ^{m}\times \R ^{q}$ existiert, so daß das KKT-System (s.o.) und 4.3 a) und c) erfüllt sind. \item $\bar{x}$ heißt kritischer Punkt, wenn $\bar{\lambda },\bar{\mu }\in \R ^{m}\times \R ^{s}$ das KKT-System ohne $\mu _{j}\geq 0$ erfüllen. \item $\mu _{j}$ heißen Lagrangemultiplikatoren. \item ~\begin{eqnarray*} L\left(x,\lambda ,\mu \right) & = & f\left(x\right)-\sum \lambda _{i}h_{i}\left(x\right)-\sum \mu _{j}g_{j}\left(x\right)\\ \textrm{bzw}.\, L^{J_{0}}\left(x,\lambda ,\mu ^{J_{0}}\right) & = & f\left(x\right)-\sum \lambda _{i}h_{i}\left(x\right)-\sum _{j\in J_{0}}\mu _{j}g_{j}\left(x\right) \end{eqnarray*} heißt Lagangefunktion. \end{enumerate} \item [Bemerkung~4.3]~ Für das freie Minimumproblem $\min \left\{ f\left(x\right)\left|x\in \R ^{n}\right.\right\} $ ist kritischer Punkt gleich stationärer Punkt. \item [Bemerkung~4.4]~ Wenn LICQ nicht erfüllt, dann muß ein lokaler Minimalpunkt nicht notwendig stationärer Punkt sein.\\ Die KKT-Bedingungen sind auch notwendige Bedingungen unter der schwächeren Vorraussetzung der MFCQ. \item [Satz~4.4]~ Es seien $f,h_{i},g_{j}\in C^{1}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$ und in $\bar{x}\in M$ sei die LICQ erfüllt. Weiterhin seien die folgenden Bedingungen erfüllt: \begin{enumerate} \item $\left|I\right|+\left|J_{0}\left(\bar{x}\right)\right|=n$ \item $Df\left(\bar{x}\right)=\sum _{i\in I}\bar{\lambda }_{i}Dh_{i}\left(\bar{x}\right)+\sum _{j\in J_{0}}\bar{\mu }_{j}Dg_{j}\left(\bar{x}\right)$ \item $\bar{\mu }_{j}>0,\, j\in J_{0}\left(\bar{x}\right)$ \end{enumerate} Dann ist $\bar{x}$ ein strikter lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\, |\, x\in M\right\} $. \item [Lemma~4.3]~ Es sei $f\in C^{2}\left(\R ^{n},\R \right),\, U,V$ Umgebungen von $\bar{x},\bar{y}\in \R ^{n}$ und $\phi :U\to V$ ein $C^{2}$-Diffeomorphismus mit $\phi \left(\bar{x}\right)=\bar{y}$. Wenn $Df\left(\bar{x}\right)=0$, so gilt:\[ D^{2}\left(f\circ \phi ^{-1}\left(\bar{y}\right)\right)=\left(D\phi ^{-1}\left(\bar{y}\right)\right)^{T}D^{2}f\left(\bar{x}\right)D\phi ^{-1}\left(\bar{y}\right)\] \begin{description} \item [Bew.:]Setze $g\left(y\right)=f\circ \phi ^{-1}\left(y\right),\, \phi ^{-1}:\R ^{n}\rightarrow \R ^{n}.$ $D\phi ^{-1}:\R ^{n}\rightarrow L\left(\R ^{n},\R ^{n}\right)$ lin. Raum der lin. beschränkten Operatoren. $D\left(D\phi ^{-1}\right):\R ^{n}\rightarrow L\left(\R ^{n},L\left(\R ^{n},\R ^{n}\right)\right).$\begin{eqnarray*} Dg\left(y\right) & = & Df\left(\phi ^{-1}\left(y\right)\right)\cdot D^{T}\phi ^{-1}\left(y\right)\\ D^{2}g\left(y\right) & = & D\left(D^{T}g\left(y\right)\right)\\ & = & D\left(D\phi ^{-1}\left(y\right)\cdot D^{T}f\left(\phi ^{-1}\left(y\right)\right)\right)\\ & = & D\left(D\phi ^{-1}\left(y\right)\right)\cdot D^{T}f\left(\phi ^{-1}\left(y\right)\right)+D\phi ^{-1}\left(y\right)\cdot D^{2}f\left(\phi ^{-1}\left(y\right)\right)\cdot D\phi ^{-1}\left(y\right) \end{eqnarray*} \end{description} \item [Lemma~4.4]~ Es seien $f,h_{i},g_{j}\in C^{2}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$, LICQ in $\bar{x}\in M$ erfüllt, $\bar{x}$ kritischer Punkt, $\phi $ Standard-Diffeomorphismus. Dann gilt: \begin{enumerate} \item $\frac{\partial f\circ \phi ^{-1}\left(0\right)}{\partial y_{j}}=0,\, j=m+p+1,\ldots ,n$ \item $\left(\frac{\partial ^{2}f\circ \phi ^{-1}\left(0\right)}{\partial y_{i}\partial y_{j}}\right)_{i,j=m+p+1,\ldots ,n}=\left(e^{iT}\left(D\phi ^{-1}\left(0\right)\right)^{T}D^{2}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)D\phi ^{-1}\left(0\right)e^{j}\right)$ \end{enumerate} \begin{description} \item [Bew.:]Es gilt \begin{enumerate} \item $DL^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }\right)=0$ \item $f\left(\bar{x}\right)=L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right),$ da $h_{i}\left(\bar{x}\right)=0,i\in I,\, g_{j}\left(\bar{x}\right)=0,j\in J_{0}\left(\bar{x}\right)$ \begin{eqnarray*} \rightarrow \, f\circ \phi ^{-1}\left(0,\ldots ,0,y_{m+p+1},\ldots ,y_{n}\right) & = & L^{J_{0}}\circ \phi ^{-1}\left(0,\ldots ,0,y_{m+p+1},\ldots ,y_{n}\right)\\ \frac{\partial }{\partial y_{j}}\left(f\circ \phi ^{-1}\left(y\right)\right) & = & \frac{\partial }{\partial y_{j}}L^{J_{0}}\circ \phi ^{-1}\left(0\right)\\ & \stackrel{\bar{x}=\phi ^{-1}\left(0\right)}{=} & \frac{\partial }{\partial x_{j}}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)\, \Rightarrow \, 1. \end{eqnarray*} \end{enumerate} Lemma 4.3 $\Rightarrow $ 2. \end{description} \item [Definition~4.3]~ Es sei $T\subseteq \R ^{n}$ ein linearer Unterraum des $\R ^{n}$ und $A$ eine symmetrische $(n\times n)$-Matrix. $A$ heißt positiv definit auf $T$, wenn $x^{T}Ax>0,\, \forall x\in T,\, x\neq 0$. $A$ heißt positiv semidefinit auf $T$, wenn $x^{T}Ax\geq 0,\, \forall x\in T$. D.h. $V^{T}AV$ ist positiv definit (semidefinit), wenn $V$ eine Matrix ist, die aus Basisvariablen von $T$ besteht.\\ \textbf{Bezeichnung:} $A|_{T}$, $A$ eingeschränkt auf $T$. \item [Definition~4.4]~ Es seien $h_{i},g_{j}\in C^{1}\left(\R ^{n},\R \right),\, i\in I,\, j\in J,\, \bar{x}\in M$.\[ T_{\bar{x}}M:=\left\{ \xi \in \R ^{n}\left|h_{i}\left(\bar{x}\right)\xi =0,\, i\in I,\, Dg_{j}\left(\bar{x}\right)\xi =0,\, j\in J_{0}\left(\bar{x}\right)\right.\right\} \] heißt Tangentialraum an $M$ im Punkt $\bar{x}\in M$. \item [Satz~4.5]~ Es seien $f,h_{i},g_{j}\in C^{1}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$, $\bar{x}$ lokaler Minimalpunkt für $\min \left\{ f\left(x\right)\left|x\in M\right.\right\} $, LICQ in $\bar{x}$ erfüllt, $\left(\bar{\lambda },\bar{\mu }^{J_{0}}\right)$ der zugehörige Lagrangemultiplikatorvektor. Dann gilt: \begin{enumerate} \item $D_{x}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)=0$ \item $D_{x}^{2}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)\left|_{T_{\bar{x}}M}\right.$ positiv semidefinit \end{enumerate} \pagebreak \begin{description} \item [Bew.:]~ \begin{enumerate} \item $\left(P\right)\, \min \left\{ f\left(x\right)\left|x\in M\left[h,g\right]\right.\right\} $ $\left(P^{*}\right)\, \min \left\{ f\circ \phi ^{-1}\left(y\right)\left|y\in \left\{ 0_{m}\right\} \times \mathbb{H}^{p}\times \R ^{n-m-p}\right.\right\} $ $\bar{x}$ ist lok. Min.pkt. für $\left(P\right)$ gdw. $0=\phi \left(\bar{x}\right)$ lok. Min.pkt. für $\left(P^{*}\right)$ ist. S.3.6 $\Rightarrow $ \[ \left(\frac{\partial ^{2}\left(f\circ \phi ^{-1}\left(0\right)\right)}{\partial y_{i}\partial y_{j}}\right)_{i,j=m+p+1,\ldots ,n}=\left(e^{i}D\phi ^{-1}\left(0\right)^{T}D^{2}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)D\phi ^{-1}\left(0\right)e^{j}\right)_{i,j=m+p+1,\ldots ,n}\] pos. semidef. $\rightarrow \, V^{T}D^{2}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)V$ pos. semidef. mit $\left(D^{T}\phi ^{-1}\left(0\right)e^{m+p+1},\ldots ,D^{T}\phi ^{-1}\left(0\right)e^{n}\right).$ \item $D\phi ^{-1}\left(0\right)e^{i},\, i=m+p+1,\ldots ,n$ Basis von $T_{\bar{x}}M.$ Es gilt\[ D\phi \left(\bar{x}\right)=\left[\begin{array}{ccccccccc} D^{T}h_{1}\left(\bar{x}\right) & \cdots & D^{T}h_{m}\left(\bar{x}\right) & D^{T}g_{1}\left(\bar{x}\right) & \cdots & D^{T}g_{p}\left(\bar{x}\right) & \xi ^{m+p+1} & \cdots & \xi ^{n}\end{array} \right]^{T}\, \textrm{reg}.\] \begin{eqnarray*} \dim T_{\bar{x}}M & = & n-m-p\\ D\phi ^{-1}\left(0\right)e^{i} & \in & T_{\bar{x}}M,\, i=m+p+1,\ldots ,n\, \textrm{lin}.\textrm{ unabh}.\rightarrow \, \textrm{Basis von }T_{\bar{x}}M \end{eqnarray*} \end{enumerate} \end{description} \item [Satz~4.6]~ Es seien $f,h_{i},g_{j}\in C^{2}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$, $\bar{x}$ kritischer Punkt für $\min \left\{ f\left(x\right)\left|x\in M\right.\right\} $, LICQ in $\bar{x}$ erfüllt, $\left(\bar{\lambda },\bar{\mu }^{J_{0}}\right)$ der zugehörige Lagrangemultiplikatorvektor mit folgenden Bedingungen: \begin{enumerate} \item $\bar{\mu }_{j}>0,\, j\in J_{0}\left(\bar{x}\right)$ (strikte Komplementaritätsbedingung) \item $\textrm{D}^{2}L^{J_{0}}\left(\bar{x},\bar{\lambda },\bar{\mu }^{J_{0}}\right)\left|_{T_{\bar{x}}M}\right.$ positiv definit \end{enumerate} Dann ist $\bar{x}$ ein strikter lokaler Minimalpunkt. \end{description} \subsection{Optimalitätsbedingungen für konvexe Optimierungsprobleme} \begin{description} \item [$(P)$]$\min \left\{ f\left(x\right)\left|x\in \R ^{n}\right.\right\} $ \item [Satz~4.7]~ Es sei $f\in C^{1}\left(\R ^{n},\R \right)$ und $f$ konvex auf $\R ^{n}$. Dann sind die folgenden Aussagen äquivalent: \begin{enumerate} \item $\bar{x}$ ist globaler Minimalpunkt \item $\bar{x}$ ist lokaler Minimalpunkt \item $\bar{x}$ ist stationärer Punkt \end{enumerate} \begin{description} \item [Bew.:]$1\, \Leftrightarrow \, 2:$ Satz 2.6 $2\, \Rightarrow \, 3:$ Satz 3.1 g.z.z.: $3\, \Rightarrow \, 2.$ Anwendung von Satz 2.3:\\ $f\left(x\right)$ ist konvex auf $\R ^{n}\, \Leftrightarrow \, \forall x,y\in \R ^{n}\, f\left(y\right)-f\left(x\right)\geq Df\left(x\right)\left(y-x\right)$. Sei $\bar{x}$ stat. Pkt., d.h. $Df\left(\bar{x}\right)=0\, \rightarrow \, f\left(y\right)-f\left(\bar{x}\right)\geq 0\, \forall y\in \R ^{n}\, \Rightarrow $ glob. Min.pkt. \end{description} \item [Bemerkung~4.5]~ $Df\left(x\right)=0$ ist notwendige und hinreichende Bedingung für konvexes $f\left(x\right)$. \item [$(P)$]$\min \left\{ f\left(x\right)\left|x\in M\right.\right\} ,\, M:=\left\{ x\in \R ^{n}\left|h_{i}\left(x\right)=0,\, g_{j}\left(x\right)\geq 0,\, i\in I,\, j\in J\right.\right\} $ \item [Satz~4.8]~ Es sei $f,\, h_{i},\, g_{j}\in C^{1}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$ und $f,-g_{j}$ konvex. $h_{i}\left(x\right):=a^{iT}x+b_{i},\, i\in I$. Dann gilt: Wenn $\bar{x}\in M$ ein stationärer Punkt ist, so ist $\bar{x}$ globaler Minimalpunkt. \begin{description} \item [Bew.:]Es seien $\bar{x}$ stat. Pkt. für $\left(P\right).$ Dann ex. Zahlen $\lambda _{i},i\in I,\, \mu _{j},j\in J_{0}\left(\bar{x}\right)$ mit \[ Df\left(\bar{x}\right)=\sum _{i\in I}\lambda _{i}Dh_{i}\left(\bar{x}\right)+\sum _{j\in J_{0}\left(\bar{x}\right)}\mu _{j}Dg_{j}\left(\bar{x}\right),\, \mu _{j}\geq 0,j\in J_{0}\left(\bar{x}\right).\] Es sei $\bar{x}\in M$ bel. Nach Satz 2.3. gilt $f\left(x\right)-f\left(\bar{x}\right)\geq Df\left(\bar{x}\right)\left(x-\bar{x}\right)$\begin{eqnarray*} \Rightarrow \, f\left(x\right)-f\left(\bar{x}\right) & \geq & \underbrace{\sum _{i\in I}\lambda _{i}Dh_{i}\left(\bar{x}\right)\left(x-\bar{x}\right)}_{=0\, \left(\textrm{Beh}.\, 1\right)}+\underbrace{\sum _{j\in J_{0}\left(\bar{x}\right)}Dg_{j}\left(\bar{x}\right)\left(x-\bar{x}\right)}_{\geq 0\, \left(\textrm{Beh}.\, 2\right)} \end{eqnarray*} Beh. 1: \begin{eqnarray*} i\in I,h_{i}\left(x\right)=h_{i}\left(\bar{x}\right) & = & 0\\ \Rightarrow \, a^{i^{T}}x+b_{i} & = & a^{i^{T}}\bar{x}+b_{i}\\ \Rightarrow \, a^{i^{T}}\left(x-\bar{x}\right) & = & 0\\ \Rightarrow \, Dh_{i}\left(\bar{x}\right)\left(x-\bar{x}\right) & = & 0 \end{eqnarray*} Beh. 2: Aus Satz 2.3. folgt ($-g_{j}\left(x\right)$ ist konvex)\begin{eqnarray*} -\underbrace{g_{j}\left(x\right)}_{\geq 0}-\underbrace{\left(-g_{j}\left(\bar{x}\right)\right)}_{=0} & \geq & -Dg_{j}\left(\bar{x}\right)\left(x-\bar{x}\right)\\ \Rightarrow \, Dg_{j}\left(\bar{x}\right)\left(x-\bar{x}\right) & \geq & 0 \end{eqnarray*} \end{description} \item [Bew.~Satz~2.4:]Es sei $f\in C^{2}\left(\R ^{n},\R \right).\, f$ ist konvex auf $\R ^{n},$ gdw. $D^{2}f\left(x\right)$ pos. semidef. $\forall x\in \R ^{n}.$ \begin{description} \item [$\left(\Rightarrow \right)$]Es seien $x\in \R ^{n}$ bel. und $F\left(x\right):=f\left(x\right)-Df\left(\bar{x}\right)\left(x-\bar{x}\right).$ Dann gilt: \begin{itemize} \item $F\left(\bar{x}\right)=f\left(\bar{x}\right)$ \item $F\left(\bar{x}\right)$ konvex auf $\R ^{n}$ (als Summe einer konvexen und einer affin-lin. Fkt.) \item $DF\left(x\right)=Df\left(x\right)-Df\left(\bar{x}\right)$ \end{itemize} $\Rightarrow \, DF\left(\bar{x}\right)=0\, \stackrel{S.4.7}{\Rightarrow }\, \bar{x}$ glob. Min.pkt. von $F.$ notw. Bed. 2. Ordnung (S.3.6) $\Rightarrow \, D^{2}F\left(\bar{x}\right)$ pos. semidef. $\stackrel{D^{2}F\left(x\right)=D^{2}f\left(x\right)}{\Rightarrow }\, D^{2}f\left(\bar{x}\right)$ ist pos. semidef. \end{description} \item [Bemerkung~4.6]~ \begin{enumerate} \item Die KKT-Bedingungen (Optimalitätsbedingungen 1. Ordnung) sind notwendige und hinreichende Bedingung für einen globalen Minimalpunkt $\bar{x}$, wenn die LICQ bzw. die schwachen MFCQ in $\bar{x}$ erfüllt sind. \item Anstelle von LICQ und MFCQ wird in der Literatur häufig eine andere Regularitätsbedingung benutzt, die sogenannte Slater-Bedingung:\[ \exists \hat{x}\in M:\, g_{j}\left(\hat{x}\right)>0,j\in J,\, h_{i}\left(x\right),i\in I\, \mbox {affinlinear}\] \item Die Slater-Bedingung ist für konvexe Restriktionsmengen äquivalent zur MFCQ. \end{enumerate} \end{description} \section{Trennungssätze für konvexe Mengen und der Satz von Farkas (\cite{1})} \subsection{Trennungssätze für konvexe Mengen } \begin{description} \item [Satz~5.1]~ Es sei $C\subseteq \R ^{n}$ nicht leer, konvex und abgeschlossen und $0\notin C$. Dann existiert ein $a\in \R ^{n},\, a\neq 0,\, \gamma \in \R $ mit $\gamma >0$ mit $a^{T}x\geq \gamma ,\, \forall x\in C$, d.h. es existiert eine Hyperebene $\left\{ x\in \R ^{n}\left|a^{T}x=\gamma \right.\right\} $ und $C\subseteq \left\{ x\in \R ^{n}\left|a^{T}x\geq \gamma \right.\right\} $ und $0\in \left\{ x\in \R ^{n}\left|a^{T}x<\gamma \right.\right\} $. \begin{description} \item [Bew.idee:]$B\left(0,r\right)=\left\{ x\in \R ^{n}\left|\left\Vert x-0\right\Vert \leq r\right.\right\} .$ Sei $r>0$ so gewählt, daß relint$\left(C\cap B\left(0,r\right)\right)\neq \emptyset ,$ d.h. ex. ein rel. innerer Pkt. $\bar{x}.$ $C\cap B\left(0,r\right)$ ist kompakt. $\left(P\right)\, \min \left\{ \left.\left\Vert x\right\Vert \right|x\in C\cap B\left(0,r\right)\right\} $ konv. Opt.problem. Nach dem Satz von Weierstraß ex. ein glob. Min.pkt. $x^{0},$ d.h. \[ \left\Vert x^{0}\right\Vert \leq \left\Vert x\right\Vert \, \forall x\in C\cap B\left(0,r\right),x^{0}\in C.\] Da $0\not \in C$ und $C$ abg., gilt $0\not \in C\cap B\left(0,r\right)\, \Rightarrow \, \left\Vert x^{0}\right\Vert >0.$ Da relint$\left(C\cap B\left(0,r\right)\right)\neq \emptyset ,$ gilt $r>\left\Vert x^{0}\right\Vert \, \Rightarrow \, x^{0}$ liegt auf Rand von $C.\, a:=x^{0}$ Beh.: $a^{T}x>0\, \forall x\in C.$ Da $C$ konvex, gilt $x^{0}+\lambda \left(x-x^{0}\right)\in C\, \forall x\in C,\lambda \in \left[0,1\right].$ \begin{eqnarray*} \Rightarrow \, \left\Vert x^{0}\right\Vert & \leq & \left\Vert x^{0}+\lambda \left(x-x^{0}\right)\right\Vert \, \forall x\in C,\lambda \in \left[0,1\right]. \end{eqnarray*} Es gilt \[ \left(x^{0}+\lambda \left(x-x^{0}\right)\right)^{T}\left(x^{0}+\lambda \left(x-x^{0}\right)\right)=\left\Vert x^{0}+\lambda \left(x-x^{0}\right)\right\Vert ^{2}\geq \left\Vert x^{0}\right\Vert =x^{0^{T}}x^{0}\, \forall x\in C,\lambda \in \left[0,1\right].\] Bin. Formel \begin{eqnarray*} \Rightarrow \, x^{0^{T}}x^{0}+\left[2\lambda \left(x-x^{0}\right)x^{0}+\lambda ^{2}\left(x-x^{0}\right)^{T}\left(x-x^{0}\right)\right]-x^{0^{T}}x^{0} & \geq & 0\, \forall x\in C,\lambda \in \left[0,1\right].\\ \lim _{\lambda \rightarrow 0^{+}}\left[2\left(x-x^{0}\right)^{T}x^{0}+\lambda \left(x-x^{0}\right)^{T}\left(x-x^{0}\right)\right] & \geq & 0\\ \rightarrow \, 2x^{T}x^{0}-2x^{0^{T}}x^{0} & \geq & 0\, \forall x\in C\\ \Rightarrow \, x^{T}x^{0} & \geq & \left\Vert x^{0}\right\Vert =:\gamma >0 \end{eqnarray*} \end{description} \item [Corollar~5.1]~ Sei $C\in \R ^{n}$ nicht leer, konvex und abgeschlossen und $x^{0}\notin C$. Dann existiert ein $a\in \R ^{n},\, a\neq 0,\, \gamma \in R$ mit $a^{T}x\geq \gamma >a^{T}x^{0},\, \forall x\in C$. \item [Satz~5.2](Allgemeiner Trennungssatz im $\R ^{n}$, siehe \cite{1}) Es seien $C_{1},C_{2}\subseteq \R ^{n}$ nicht leer, konvex mit $\textrm{relint}C_{1}\cap \textrm{relint}C_{2}=\emptyset $. Dann existiert ein $a\neq 0,\, a\in \R ^{n},\, \gamma \in \R $ und $a^{T}x\geq \gamma \geq a^{T}y,\, \forall x\in c\ell C_{1},\, \forall y\in c\ell C_{2}$ und es gilt:\[ \left\{ x\in \R ^{n}\left|a^{T}x=\gamma \right.\right\} \not \supseteq C_{1}\cup C_{2}\] \end{description} \subsection{Der Satz von Farkas} \begin{description} \item [Satz~5.3]~ Sei $A=\left(\begin{array}{ccc} a_{11} & \ldots & a_{1n}\\ \vdots & & \vdots \\ a_{m1} & \ldots & a_{mn}\end{array} \right)$ und $A^{T}=\left(a^{1},\ldots ,a^{m}\right),\, a^{i}\in \R ^{n}$. Dann gilt:\[ \left\{ x\in \R ^{n}\left|Ax\leq 0\right.\right\} \subseteq \left\{ x\in \R ^{n}\left|c^{T}x\leq 0\right.\right\} \quad \Leftrightarrow \quad \exists u\in \R ^{m}:u\geq 0,\, c=A^{T}u\, \left(*\right)\] \begin{description} \item [Bew.:]$\left(\Leftarrow \right):$ Sei $x$ mit $Ax<0$ und $u\geq 0\, \rightarrow \, 0\geq u^{T}Ax\stackrel{\left(*\right)}{=}c^{T}x$. \begin{description} \item [$\left(\Rightarrow \right):$]Es sei $K:=\left\{ x\in \R ^{n}\left|x=A^{T}u,u\geq 0\right.\right\} $ polyedrischer Kegel. $\left(*\right)\, \Leftrightarrow \, c\in K.$ Ann. 1: $c\not \in K,\, K\neq \emptyset ,$ konvex, abg. Cor. 5.1 $\Rightarrow \, \exists a\in \R ^{n},a\neq 0,\gamma \in \R $ mit \[ a^{T}x\geq \gamma \, \forall x\in K\, \Rightarrow \, a^{T}c<\inf _{x\in K}a^{T}x=:\alpha \, \left(**\right)\] Da $0\in K\, \Rightarrow \, \alpha \leq 0.$ Wir zeigen: $\alpha =0.$ Ann. 2: $\alpha <0\, \Rightarrow \, \exists \tilde{x}\in K:\, a^{T}\tilde{x}<0,\, \lambda \tilde{x}\in K\, \forall \lambda \geq 0$ $\Rightarrow \, \lambda a^{T}\tilde{x}<0\, \forall \lambda >0\, \Rightarrow \, \inf _{x\in K}a^{T}x=-\infty .$ Wid. zu $\left(**\right)\, \Rightarrow \, \alpha =0$ $\Rightarrow \, a^{T}c<0\leq a^{T}x\, \forall x\in K.$ Da $a^{i}\in K,i=1,\ldots ,m\, \Rightarrow \, a^{T}a^{i}\geq 0\, \forall a^{i}$ $\Rightarrow \, Aa\geq 0,\, c^{T}a<0$ $\Rightarrow \, A\left(-a\right)\leq 0,\, c^{T}\left(-a\right)>0$ Wid. zu $\left\{ x\in \R ^{n}\left|Ax\leq 0\right.\right\} \subseteq \left\{ x\in \R ^{n}\left|c^{T}x\leq 0\right.\right\} .$ \end{description} \end{description} \end{description} \section{Dualitätstheorie der nichtlin. Optimierung (\cite{6})} \subsection{Das Subdifferential} \begin{description} \item [Definition~6.1]~ Es sei $f:\R ^{n}\to \R $ \begin{enumerate} \item Ein Vektor $a\in \R ^{n}$ heißt Subgradient von $f$ in $\bar{x}$, wenn gilt:\[ f\left(x\right)\geq f\left(\bar{x}\right)+a^{T}\left(x-\bar{x}\right),\, \forall x\in \R ^{n}\] \item Das Subdifferential $\partial f\left(\bar{x}\right)$ ist die Menge aller Subgradienten von $f$ in $\bar{x}$. \item Wenn $\partial f\left(\bar{x}\right)\neq \emptyset $, so heißt $f$ subdifferenzierbar. \end{enumerate} \item [Bemerkung~6.1]~ Das Subdifferential ist auch für nichtkonvexe Funktionen definiert. \item [Geometrische~Interpretation]~ $\textrm{epi}\left(f\right)=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|f\left(x\right)\leq \mu \right\} $ $\textrm{Hyperebene im }\R ^{n+1}:\, H\left(a,\beta ,\alpha \right):=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|a^{T}x+\beta \mu =\alpha \right\} ,\, \left(\begin{array}{c} a\\ \beta \end{array} \right)\neq 0$ sei $\beta =-1$: $H\left(a,\alpha \right):=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|a^{T}x-\mu =\alpha \right\} $ $c\ell H^{+}\left(a,\alpha \right):=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|a^{T}x-\mu \geq \alpha \right\} $ $c\ell H^{-}\left(a,\alpha \right):=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|a^{T}x-\mu \leq \alpha \right\} $ \item [Definition~6.2]~ $H\left(a,\alpha \right)$ heißt nichtvertikale Stützhyperebene an $\textrm{epi}\left(f\right)$ durch $\left(\bar{x},f\left(\bar{x}\right)\right)$, wenn gilt: \begin{enumerate} \item $H\left(a,\alpha \right)=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|a^{T}x-\mu =a^{T}\bar{x}-f\left(\bar{x}\right)\right\} $ \item $\textrm{epi}\left(f\right)\subseteq c\ell H^{-}\left(a,\alpha \right)$ \end{enumerate} \item [Satz~6.1]~ $\partial f\left(\bar{x}\right)$ ist die Menge aller Vektoren $a$, für die $H\left(a,\alpha \right)=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|a^{T}x-\mu =\alpha \right\} $ eine nichtvertikale Stützhyperebene an $\textrm{epi}\left(f\right)$ im Punkt $\left(\bar{x}^{T},f\left(\bar{x}\right)\right)$ ist. \begin{description} \item [Bew.:]$\left(\Leftarrow \right):\, $Sei $H\left(a,\alpha \right)$ ein nichtvert. Stützhyperebene an epi$\left(f\right)$ durch $\left(\bar{x},f\left(\bar{x}\right)\right).$\begin{eqnarray*} \rightarrow \, a^{T}x-\mu & \leq & a^{T}\bar{x}-f\left(\bar{x}\right)\, \forall \left(\begin{array}{c} x\\ \mu \end{array} \right)\, \textrm{mit }\mu \geq f\left(x\right)\, \forall x\in \R ^{n}\\ \rightarrow \, a^{T}x-f\left(x\right) & \leq & a^{T}\bar{x}-f\left(\bar{x}\right)\, \forall x\in \R ^{n}\\ \rightarrow \, f\left(x\right)-f\left(\bar{x}\right) & \geq & a^{T}\left(x-\bar{x}\right)\, \forall x\in \R ^{n}\\ \rightarrow \, a & \in & \partial f\left(\bar{x}\right) \end{eqnarray*} \end{description} \item [Corollar~6.1]~ Es sei $f\in C^{1}\left(\R ^{n},\R \right)$ und konvex. Dann gilt: $\partial f\left(\bar{x}\right)=\left\{ Df\left(\bar{x}\right)\right\} ,\, \forall \bar{x}\in \R ^{n}$. \begin{description} \item [Bew.:]Aus S. 6.1 folgt: $Df\left(\bar{x}\right)\in \partial f\left(x\right).$ Wir benutzen die Eind. des Tangentialraumes $\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|Df\left(\bar{x}\right)x-\mu =0\right\} $ im Pkt. $\left(\bar{x},f\left(\bar{x}\right)\right).$ \end{description} \item [Satz~6.2]~ Es sei $f:\R ^{n}\to \R $ subdifferenzierbar in $\bar{x}$. Dann ist $\partial f\left(\bar{x}\right)$ eine kompakte und konvexe Menge. \item [Satz~6.3]~ Es sei $f:\R ^{n}\to \R $ konvex. Dann ist $f$ subdifferenzierbar $\forall x\in \R ^{n}$. \begin{description} \item [Bew.:]Wir konstruieren einen Subgradienten mit Hilfe des Trennungssatzes, d.h. eine nichtvertikale Stützhyperebene an den Epigraphen epi$\left(f\right)=\left\{ \left.\left(\begin{array}{c} x\\ \mu \end{array} \right)\in \R ^{n+1}\right|f\left(x\right)\leq \mu \right\} .$ Es gilt: $\left(\bar{x},f\left(\bar{x}\right)\right)\in \textrm{epi}\left(f\right)\setminus \textrm{intepi}\left(f\right).$ Nach dem Trennungssatz gibt es einen Vektor $\left(\begin{array}{c} \bar{a}\\ \bar{a}_{n+1}\end{array} \right)\in \R ^{n+1}\setminus \left\{ 0\right\} $ mit \begin{eqnarray*} \left(\begin{array}{c} \bar{a}\\ \bar{a}_{n+1}\end{array} \right)^{T}\left(\left(\begin{array}{c} x\\ \mu \end{array} \right)-\left(\begin{array}{c} \bar{x}\\ f\left(\bar{x}\right)\end{array} \right)\right) & \leq & 0\, \forall \left(\begin{array}{c} x\\ \mu \end{array} \right)\in \textrm{epi}\left(f\right),\\ \textrm{d}.\textrm{h}.\, \bar{a}^{T}\left(x-\bar{x}\right)+\bar{a}_{n+1}\left(\mu -f\left(\bar{x}\right)\right) & \leq & 0\, \forall x\in \R ^{n},\mu \geq 0.\, \left(*\right) \end{eqnarray*} Da $\mu $ bel. groß werden kann, muß $\bar{a}_{n+1}\leq 0$ sein. Beh.: $\bar{a}_{n+1}<0$ (nichtvertikale Stützhyperebene). Ann.: $\bar{a}_{n+1}=0\, \Rightarrow \, \bar{a}^{T}\left(x-\bar{x}\right)\leq 0\, \forall x\in \R ^{n}.$ Da $\bar{x}\in \R ^{n}$ ist \begin{eqnarray*} \bar{x}+\lambda \bar{a} & \in & \R ^{n}\, \forall \lambda \geq 0\\ \Rightarrow \, a^{T}\left(\bar{x}+\lambda \bar{a}-\bar{x}\right)=\lambda \bar{a}^{T}\bar{a} & \leq & 0\\ \Rightarrow \, \bar{a} & = & 0\\ \Rightarrow \, \left(\begin{array}{c} \bar{a}\\ \bar{a}_{n+1}\end{array} \right) & = & 0\, \textrm{Wid}.\\ \Rightarrow \, \bar{a}_{n+1} & < & 0\, \rightarrow \, \bar{a}_{n+1}=-\left|\bar{a}_{n+1}\right|.\\ \left(*\right)\, \Rightarrow \, \bar{a}^{T}\left(x-\bar{x}\right)-\left|\bar{a}_{n+1}\right|\left(\mu -f\left(\bar{x}\right)\right) & \leq & 0\, \forall x\in \R ^{n},\mu \geq f\left(x\right). \end{eqnarray*} Für $x\in \R ^{n}$ bel. und $\mu =f\left(x\right)$ folgt \begin{eqnarray*} \frac{1}{\left|\bar{a}_{n+1}\right|}\cdot a^{T}\left(x-\bar{x}\right)+f\left(\bar{x}\right) & \leq & f\left(x\right)\, \forall x\in \R ^{n}\\ \Rightarrow \, \frac{a}{\left|\bar{a}_{n+1}\right|} & \in & \partial f\left(\bar{x}\right). \end{eqnarray*} \end{description} \item [Satz~6.4]~ Es sei $f:\R ^{n}\to \R $ konvex. $\bar{x}\in \R ^{n}$ ist optimal für $\left\{ \left.f\left(x\right)\right|x\in \R ^{n}\right\} $ gdw. $0\in \partial f\left(\bar{x}\right)$. \begin{description} \item [Bew.:]$\left(\Rightarrow \right):\, \bar{x}$ ist opt., d.h. $f\left(\bar{x}\right)\leq f\left(x\right)\, \forall x\in \R ^{n}.\, \left(*\right)$ S. 6.3., $f$ konvex $\Rightarrow \, f$ ist subdiff.bar in $\bar{x}$, d.h. $f\left(\bar{x}\right)+a^{T}\left(x-\bar{x}\right)\leq f\left(x\right)\, \forall x\in \R ^{n}.$ $\stackrel{\left(*\right)}{\Rightarrow }\, a=0\in \partial f\left(\bar{x}\right).$ $\left(\Leftarrow \right):\, a^{T}\left(x-x^{0}\right)\leq f\left(x\right)-f\left(\bar{x}\right);\, a=0\, \Rightarrow $ Beh. \end{description} \end{description} \subsection{Dualitätssätze für allg. nichtlin. Optimierungsprobleme} Es seien $f,\, g_{j},\, j\in J$ Funktionen definiert auf $\R ^{n}$, $J:=\left\{ 1,\ldots ,s\right\} ,\, I=\emptyset $ \begin{description} \item [Primalproblem:]~ $(P)\, \inf \left\{ \left.f\left(x\right)\right|x\in M\right\} ,\, M:=\left\{ \left.x\in \R ^{n}\right|g_{j}\left(x\right)\geq 0,\, j\in J\right\} ,\, L\left(x,\mu \right):=f\left(x\right)-\sum _{j\in J}\mu _{j}g_{j}\left(x\right)$ \item [Dualproblem:]~ \begin{description} \item [$(D)$]$\sup \left\{ \left.h\left(\mu \right)\right|\mu \in \R _{+}^{s}\right\} ,\, \R _{+}^{s}:=\left\{ \left.\mu \in \R ^{s}\right|\mu \geq 0\right\} ,\, h\left(\mu \right):=\inf _{x\in \R ^{n}}L\left(x,\mu \right)$ oder \item [$(D)$]$\sup _{\mu \in \R _{+}^{s}}\inf _{x\in \R ^{n}}L\left(x,\mu \right)$ \end{description} \item [Lemma~6.1]~ Wenn $M\neq \emptyset $, so gilt $f\left(x\right)\geq h\left(\mu \right),\, \forall x\in M,\, \forall \mu \in \R _{+}^{s}$. Insbesondere gilt: \[ \varphi _{P}:=\inf _{x\in M}f\left(x\right)\geq \varphi _{D}:=\sup _{\mu \in \R _{+}^{s}}h\left(\mu \right)\] \begin{description} \item [Bew.:]Es gilt \[ \psi \left(x\right):=\sup _{\mu \in \R _{+}^{s}}L\left(x,\mu \right)=\left\{ \begin{array}{cc} f\left(x\right) & ,x\in M\\ \infty & ,x\not \in M\end{array} \right.\] $\left(\bar{P}\right)\, \inf \left\{ \left.\psi \left(x\right)\right|x\in \R ^{n}\right\} .$ Da $M\neq \emptyset ,$ sind $\left(P\right)$ und $\left(\bar{P}\right)$ äqu. im folgenden Sinne: die Lösungsmengen sind gleich und die Infima sind gleich. Es gilt für bel. $\bar{x}\in \R ^{n},\bar{\mu }\in \R _{+}^{s}$\[ \psi \left(\bar{x}\right)=\sup _{\mu \in \R _{+}^{s}}L\left(\bar{x},\mu \right)\geq L\left(\bar{x},\bar{\mu }\right)\geq \inf _{x\in \R ^{n}}L\left(x,\bar{\mu }\right)=h\left(\bar{\mu }\right)\] \[ \rightarrow \, \inf _{x\in M}f\left(x\right)=\inf _{x\in \R ^{n}}\psi \left(x\right)=\inf _{x\in \R ^{n}}\sup _{\mu \in \R _{+}^{s}}L\left(x,\mu \right)\geq \sup _{\mu \in \R _{+}^{s}}\inf _{x\in \R ^{n}}L\left(x,\mu \right)=\sup _{\mu \in \R _{+}^{s}}h\left(\mu \right)\] \end{description} \item [Bemerkung~6.2]~ $(P)$ und $(D)$ können auch in symmetrischer Form geschrieben werden:\[ (P)\quad \inf _{x\in \R ^{n}}\sup _{\mu \in \R _{+}^{s}}L\left(x,\mu \right)\qquad (D)\quad \sup _{\mu \in \R _{+}^{s}}\inf _{x\in \R ^{n}}L\left(x,\mu \right)\] \end{description} $M\left(y\right):=\left\{ \left.x\in \R ^{n}\right|g_{j}\left(x\right)\geq y_{j},j\in J\right\} \, \rightarrow $ param. Opt.problem $P\left(y\right):\, \inf \left\{ \left.f\left(x\right)\right|x\in M\left(y\right)\right\} ,\, \varphi \left(y\right)=\inf \left\{ \left.f\left(x\right)\right|x\in M\left(y\right)\right\} $ Extremalwertfkt. $\varphi :\R ^{s}\rightarrow \bar{\R }=\R \cup \left\{ +\infty ,-\infty \right\} ,\, \varphi \left(y\right)=+\infty ,$ falls $M\left(y\right)=0$ (Vereinbarung) Es gilt $P\left(0\right)=\left(P\right),\, \varphi \left(0\right)=\varphi _{P},\, M\left(0\right)=M.$ \begin{description} \item [Satz~6.5](starker Dualitätssatz) Sei $\varphi _{P}$ endlich ($(P)$ nicht notwendig lösbar), dann gilt: $\varphi _{P}=\varphi _{D}$ und $(D)$ hat einen globalen Maximalpunkt $\mu ^{0}$ gdw. $\varphi $ subdifferenzierbar in $0$ (und $\mu ^{0}\in \partial \varphi \left(0\right)$). \begin{description} \item [Bew.:]Vorbetrachtungen: $h\left(\mu \right)$ für $\mu \geq 0$\begin{eqnarray*} \left(*\right):\, h\left(\mu \right) & = & \inf _{x\in \R ^{n}}\left\{ f\left(x\right)-\sum _{j\in J}\mu _{j}g_{j}\left(x\right)\right\} \\ & \stackrel{\left(da\, g_{j}\geq y_{j}\right)}{=} & \inf _{x\in M\left(y\right)}\left\{ f\left(x\right)-\sum \mu _{j}y_{j}\right\} \\ & = & \inf _{y\in \R ^{s}}\inf _{x\in M\left(y\right)}\left\{ f\left(x\right)-\mu ^{T}y\right\} \\ & = & \inf _{y\in \R ^{s}}\left\{ \varphi \left(y\right)-\mu ^{T}y\right\} \end{eqnarray*} \begin{description} \item [$\left(\Rightarrow \right)$]Es gilt $\varphi _{P}=\varphi _{D}$ und $\left(D\right)$ hat einen glob. Max.pkt. $\mu ^{0},$ d.h. $h\left(\mu ^{0}\right)=\varphi _{D}$ und $\mu ^{0}\in \R _{+}^{s}$ \begin{description} \item [$\left(*\right)\, \rightarrow \, \varphi \left(y\right)-\mu ^{0^{T}}y\geq \varphi \left(0\right)=\varphi _{P}\, \forall y\in \R ^{s}$]~ \item [$\rightarrow \, \varphi \left(y\right)-\varphi \left(0\right)\geq \mu ^{0^{T}}y\, \forall y\in \R ^{s}\, \rightarrow \, \varphi $]ist subdiff.bar. in 0 und $\mu ^{0}\in \partial \varphi \left(0\right).$ \end{description} \item [$\left(\Leftarrow \right)$]$\varphi $ sei subdiff.bar in 0, d.h. $\exists \mu ^{0}\in \R ^{s}$ mit $\varphi \left(y\right)-\varphi \left(0\right)\geq \mu ^{0^{T}}y\, \forall y\in \R ^{s}.$ $\Rightarrow \, \varphi _{P}=\varphi \left(0\right)\leq \varphi \left(y\right)-\mu ^{0^{T}}y\, \forall y\in \R ^{+}\, \left(**\right)$ $\left(*\right)\Rightarrow \, h\left(\mu ^{0}\right)\geq \varphi _{P}\, \stackrel{L.4.1,\varphi _{P}\geq \varphi _{D}}{\rightarrow }\, h\left(\mu ^{0}\right)=\varphi _{P}\, \left(***\right)$ z.z.: $\mu ^{0}\in \R _{+}^{s}$ (d.h. zulässig) Sei $y\leq 0\, \Rightarrow \, g_{j}\left(y\right)\geq 0\geq y_{j},j\in J\, \Rightarrow \, M\left(0\right)\subseteq M\left(y\right)$ $\Rightarrow \, \inf _{x\in M\left(0\right)}f\left(x\right)\geq \inf _{x\in M\left(y\right)}f\left(x\right),$ d.h. $\varphi \left(y\right)-\varphi \left(0\right)\leq 0\, \stackrel{\left(**\right)}{\Rightarrow }\, \mu ^{0^{T}}y\leq 0\, \forall y\in \R _{-}^{s}.$ $\Rightarrow \, \mu ^{0}\geq 0,$ zusammen mit $\left(***\right)\, \Rightarrow \, \mu ^{0}$ ist glob. Max.pkt. für $\left(D\right).$ \end{description} \end{description} \item [Bemerkung~6.3]~ Wir haben $f,g_{j},j\in J$ als Fkt.en auf $\R ^{n}$ betrachtet. Analoges gilt auch für $X\subseteq \R ^{n},X\neq \emptyset ,\, f:X\rightarrow \R ,g_{j}:X\rightarrow \R ,j\in J.$ \item [Satz~6.6](Dualitätssatz für konvexe Probleme) Es sei $f:\R ^{n}\to \R $ konvex, $g_{j}:\R ^{n}\to \R $ konkav, $j\in J$ und die Slater-Bedingung sei erfüllt (d.h. $\exists \bar{x}\in \R ^{n}:g_{j}\left(\bar{x}\right)>0,\, j\in J$). Weiter sei $\varphi _{P}$ endlich. Dann ist $(D)$ lösbar und es gilt $\varphi _{P}=\varphi _{D}$. \begin{description} \item [Bew.:]Erfolgt mit Hilfe von Satz 6.5. Man kann zeigen: $\varphi $ subdiff.bar in 0. (siehe \cite{6}) \end{description} \item [Bemerkung~6.5]~ Man kann mit Hilfe des Dualitätssatzes der konvexen Opt. die KKT-Bedingungen herleiten. \item [Satz~6.7](Sattelpunkttheorem) Es sei $(P)$ ein konvexes Optimierungsproblem und es sei die Slater-Bedingung erfüllt. $\bar{x}\in \R ^{n}$ ist optimal für $(P)\, \Leftrightarrow \, \exists \bar{\mu }\geq 0$, so daß\[ L\left(\bar{x},\mu \right)\leq L\left(\bar{x},\bar{\mu }\right)\leq L\left(x,\bar{\mu }\right),\, \forall x\in \R ^{n},\, \forall \mu \geq 0\] \begin{description} \item [Bew.:]siehe \cite{6}: $\left(\Leftarrow \right)$ gilt allg. ohne Konvexität und Slater-Bedingung $\left(\Rightarrow \right)$ Wir benötigen den Trennungssatz. \end{description} \item [Definition~6.3]~ $\varphi :\R ^{m}\to \R $ heißt unterhalbstetig (uhs) in $\bar{y}$, wenn für jede Folge $\left\{ y^{t}\right\} ,\, y^{t}\to \bar{y}$ gilt:\[ \liminf _{t\to \infty }\varphi \left(y^{t}\right)\geq \varphi \left(\bar{y}\right)\] \item [Satz~6.8]~ Es sei $\varphi _{P}$ endlich. Dann gilt: \begin{enumerate} \item Falls $\varphi _{P}=\varphi _{D}$, so ist $\varphi $ unterhalbstetig in $0$. \item Ist $\varphi $ unterhalbstetig in $0$ und $(P)$ konvex, so gilt $\varphi _{P}=\varphi _{D}$. \end{enumerate} \item [Bemerkung~6.6]~ Man kann mit Hilfe von Satz 6.8 die Optimalitätssätze der linearen Optimierung herleiten. $\left(P\right)\, \max \left\{ \left.c^{T}x\right|Ax\leq b,x\geq 0\right\} =-\min \left\{ \left.-c^{T}x\right|Ax\leq b,x\geq 0\right\} ,\, X:=\left\{ \left.x\right|x\geq 0\right\} $ $P\left(y\right):\, \min \left\{ \left.-c^{T}x\right|Ax-b\leq y,x\in X\right\} .$ z.z.: $\varphi \left(y\right)$ ist uhs. in 0, sogar stetig in 0. $\left(D\right)\, \min \left\{ \left.b^{T}u\right|A^{T}u\geq c,u\geq 0\right\} $ \item [Satz~6.9]~ Wenn $M_{P}:=\left\{ \left.x\right|Ax\leq b,x\geq 0\right\} \neq \emptyset $ und $M_{D}:=\left\{ \left.u\right|A^{T}u\geq c,u\geq 0\right\} \neq \emptyset $, so haben $(P)$ und $(D)$ Optimalitätspunkte $\hat{x}$ und $\hat{u}$ und es gilt:\[ c^{T}\hat{x}=\max _{x\in M_{P}}c^{T}x=\min _{u\in M_{D}}b^{T}u=b^{T}\hat{u}\] \item [Satz~6.10]~ $(P)$ ist lösbar, gdw. $(D)$ lösbar ist und es gilt die Aussage von Satz 6.9. \end{description} \pagebreak \section{Morsetheorie (\cite{2})} \begin{description} \item [Satz~7.1]~ Es seien $k\geq 1,\, f\in C^{k}\left(\R ^{n},\R \right)$ und $Df\left(\bar{x}\right)\neq 0$. Dann existieren Umgebungen $U$ und $V$ von $\bar{x}$ und $0\in \R ^{n}$ und ein $C^{k}$-Diffeomorphismus $F:U\to V$ und $F\left(x\right)=y,\, F\left(\bar{x}\right)=0$ und $f\circ F^{-1}=f\left(\bar{x}\right)+y_{1}$. \begin{description} \item [Bew.:]Nach Vor. $Df\left(\bar{x}\right)\neq 0$ (o.B.d.A. $\frac{\partial F}{\partial x_{1}}\left(\bar{x}\right)\neq 0$). Def. von $F$ wie folgt: \begin{eqnarray*} y & = & F\left(x\right)\\ y_{1} & = & f\left(x\right)-f\left(\bar{x}\right)\\ y_{j} & = & x_{j}-\bar{x}_{j},\, j=2,\ldots ,n \end{eqnarray*} $F$ hat folgende Eigenschaften: \begin{enumerate} \item $F\in C^{k}\left(\R ^{n},\R ^{n}\right)$ \item $DF\left(\bar{x}\right)=\left(\begin{array}{cccc} \frac{\partial f}{\partial x_{1}}\left(\bar{x}\right) & \frac{\partial f}{\partial x_{2}}\left(\bar{x}\right) & \cdots & \frac{\partial f}{\partial x_{n}}\left(\bar{x}\right)\\ 0 & 1 & \cdots & 0\\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & 1\end{array} \right)$ hat Rang $n$ (wegen $\frac{\partial f}{\partial x_{1}}\left(\bar{x}\right)\neq 0$) \end{enumerate} Inversentheorem $\Rightarrow \, \exists $ Umgebungen $U,V$ von $\bar{x},0\in \R ^{n},$ so daß $F:U\rightarrow V$ ein $C^{k}$-Diff., und es gilt $F\left(\bar{x}\right)=0$ und $f\circ F^{-1}\left(y_{1},\ldots ,y_{n}\right)=y_{1}+f\left(\bar{x}\right).$ \end{description} \item [Bemerkung~7.1]~ $\bar{x}$ mit $Df\left(\bar{x}\right)\neq 0$ ist kein Kandidat für einen lokalen Minimalpunkt. \item [Bemerkung~7.2]~ Spezialfall: $f\left(0\right)=0,\, \textrm{D}f\left(0\right)\neq 0\, \Rightarrow \, f\circ F^{-1}\left(y\right)=y_{1}$. Sei $f\in C^{2}\left(\R ^{n},\R \right)\, \Rightarrow \, D^{2}f\left(x\right)$ ist symmetrisch $\Rightarrow $ relle Eigenwerte. \item [Definition~7.1]~ \begin{enumerate} \item Ein stationärer (kritischer) Punkt $\bar{x}\in \R ^{n}$ von $f\left(x\right)\, \left(\min \left\{ f\left(x\right)\left|x\in \R ^{n}\right.\right\} \right)$ heißt nichtentartet, wenn $D^{2}f\left(\bar{x}\right)$ regulär. \item $QI:=QI\left(D^{2}f\left(\bar{x}\right)\right)$ ist die Anzahl der negativen Eigenwerte von $D^{2}f\left(\bar{x}\right)$ und heißt quadratischer Index (Morse-Index). \item $QCI:=QCI\left(D^{2}f\left(\bar{x}\right)\right)$ ist die Anzahl der positiven Eigenwerte und heißt quadratischer Co-Index. \end{enumerate} \item [Bemerkung~7.3]~ Sei $\bar{x}$ ein nichtentarteter stationärer Punkt von $f\left(x\right)$. Wenn $QI=0$, so ist $\bar{x}$ lokaler Minimalpunkt. Wenn $QI=n$, so ist $\bar{x}$ ein lokaler Maximalpunkt. Wenn $00\right\} \right|$ heißt linearer Co-Index. \item $QI:=QI\left(D^{2}f\left(\bar{x}\right)\right)$ Anzahl der neg. Eigenwerte von $D_{x}^{2}L^{J_{0}}$, heißt quadratischer Index. \item $QCI:=QCI\left(D^{2}f\left(\bar{x}\right)\right)$ Anzahl der pos. Eigenwerte von $D_{x}^{2}L^{J_{0}}$, heißt quadratischer Co-Index. \end{enumerate} \item [Satz~7.3]~ Seien $f,h_{i},g_{j}\in C^{3}\left(\R ^{n},\R \right),\, i\in I,\, j\in J$ und $\bar{x}$ ein nichtentarteter kritischer Punkt mit $LI\left(\bar{x}\right)=k_{1}$, $QI\left(\bar{x}\right)=k_{2}$ und $J_{0}\left(\bar{x}\right)=\left\{ 1,\ldots ,p\right\} $. Dann existieren Umgebungen $U,V$ von $\bar{x},0\in \R ^{n}$ und ein Diffeomorphismus $F:U\to V$ ($F\in C^{1}\left(U,V\right)$), $y=F\left(x\right)$, $F\left(\bar{x}\right)=0$ und es gilt: \begin{enumerate} \item $y_{m+1}\geq 0,\, y_{m+p}\geq 0$ \item $f\circ F^{-1}\left(0,\ldots ,0,y_{m+1},\ldots ,y_{n}\right)=$\[ f\left(\bar{x}\right)=\sum _{i_{1}=m+1}^{m+k_{1}}y_{i_{1}}+\sum _{i_{2}=m+k_{1}+1}^{m+p}y_{i_{2}}-\sum _{i_{3}=m+p+1}^{m+p+k_{2}}y_{i_{3}}^{2}+\sum _{i_{4}=m+p+k_{2}+1}^{n}y_{i_{4}}^{2}\] \end{enumerate} \item [Bemerkung~7.6]~ Aus den Optimalitätsbedingungen in Kapitel 3 folgt: \begin{enumerate} \item Wenn $LI\left(\bar{x}\right)=0$, so ist $\bar{x}$ ein stationärer Punkt. \item Wenn $LI\left(\bar{x}\right)=0$ und $QI\left(\bar{x}\right)=0$, so ist $\bar{x}$ ein lokaler Minimalpunkt. \item Wenn $LI\left(\bar{x}\right)=0$ und $QI\left(\bar{x}\right)=n$, so ist $\bar{x}$ ein lokaler Maximalpunkt in der Menge der stationären Punkte. \item Wenn $00,\, j\in J,\, L\left(x,\mu \right)=f\left(x\right)-\sum _{j\in J}\mu _{j}g_{j}\left(x\right)$ \item [Satz~8.1]~ Es sei $(P)$ ein konvexes Optimierungsproblem, Slaterbedingung erfüllt. $\bar{x}\in \R ^{n}$ ist optimal für $(P)$, gdw. $\exists \bar{\mu }\geq 0$, so daß $L\left(\bar{x},\mu \right)\leq L\left(\bar{x},\bar{\mu }\right)\leq L\left(x,\bar{\mu }\right)\, \forall x\in \R ^{n},\, \forall \mu \geq 0$ \end{description} Dieses Minimax-Prinzip soll verallgemeinert werden:\\ Es seien $X\subseteq \R ^{n},\, Y\subseteq \R ^{n},\, X\neq \emptyset ,\, Y\neq \emptyset $ und konvex. $\psi \left(x,y\right)$ sei eine Funktion mit $x\in X$, $y\in Y$, die für jeden Punkt $y\in Y$ konvex auf $X$ und für jeden Punkt $x\in X$ konkav ist. \begin{description} \item [Ziel:]Existenzsätze für Sattelpunkte bzw. Minimax-Punkte, d.h.\[ \psi \left(x,\bar{y}\right)\leq \psi \left(\bar{x},\bar{y}\right)\leq \psi \left(\bar{x},y\right),\, \forall x\in X,\, \forall y\in Y.\] \item [Geometrische~Interpretation:]$x\in X,y\in Y$, betrachten für jeden Punkt \underbar{}$y\in Y$ den Epigraph \[ \mathrm{E}_{\psi }\left(y\right):=\left\{ \left(x,z\right)\in \R ^{n}\times \R \left|z\geq \psi \left(x,y\right),\, \forall x\in X\right.\right\} \] und für jedes $x\in X$ den Hypograph \[ h_{\psi }\left(x\right):=\left\{ \left(y,z\right)\in \R ^{n}\times \R \left|z\leq \psi \left(x,y\right),\, \forall y\in Y\right.\right\} \] Epigraph über $X\times Y$: \[ \mathrm{E}_{\psi }:=\left\{ \left(x,y,z\right)\in \R ^{n}\times \R ^{m}\times \R \left|z\geq \psi \left(x,y\right),\, \left(x,y\right)\in X\times Y\right.\right\} \] Hypograph über $X\times Y$: \[ h_{\psi }:=\left\{ \left(x,y,z\right)\in \R ^{n}\times \R ^{m}\times \R \left|z\leq \psi \left(x,y\right),\, \left(x,y\right)\in X\times Y\right.\right\} \] Weiterhin betrachten man zwei lineare Unterräume von $\R ^{n+m+1}$ \begin{eqnarray*} L\left(\tilde{y}\right) & := & \left\{ \left.\left(x,y,z\right)\in \R ^{n+m+1}\right|y=\tilde{y}\right\} \\ L\left(\tilde{x}\right) & := & \left\{ \left.\left(x,y,z\right)\in \R ^{n+m+1}\right|x=\tilde{x}\right\} \end{eqnarray*} Offenbar gilt: $\mathrm{E}_{\psi }\left(\tilde{y}\right)=\mathrm{E}\cap L\left(\tilde{y}\right)$ und $h_{\psi }\left(\tilde{x}\right)=h_{\psi }\cap L\left(\tilde{x}\right)$. Für einen festen Punkt $y\in Y$ nennt man deshalb die Menge $\mathrm{E}_{\psi }\left(y\right)$ einen $y$-Schnitt des Epigraphen $\mathrm{E}_{\psi }$ und für $x\in X$ $h_{\psi }\left(x\right)$ einen $x$-Schnitt des Hypographen $h_{\psi }$, der auf $X\times Y$ definierten Funktion $\psi \left(x,y\right)$. \end{description} Für jedes Punktepaar $y\in Y,\, x\in X$ existieren Punkte $x_{y}\in X,\, y_{x}\in Y$ derart, daß \begin{eqnarray*} \psi \left(x_{y},y\right) & = & \min _{x\in X}\psi \left(x,y\right),\\ \psi \left(x,y_{x}\right) & = & \max _{y\in Y}\psi \left(x,y\right). \end{eqnarray*} Dann folgt mit obiger Definition des Epigraphen und Hypographen: \begin{eqnarray*} z_{y}:=\psi \left(x_{y},y\right)=\min _{x\in X}\psi \left(x,y\right) & \leq & \psi \left(x,y\right)\leq z\, \forall \left(x,z\right)\in \mathrm{E}_{\psi }\left(y\right)\\ z_{x}:=\psi \left(x,y_{x}\right)=\max _{y\in Y}\psi \left(x,y\right) & \geq & \psi \left(x,y\right)\geq z\, \forall \left(y,z\right)\in h_{\psi }\left(x\right) \end{eqnarray*} Wenn es einen Punkt $y^{0}\in Y$ derart gibt, daß $z_{y^{0}}\geq z_{y},\, \forall y\in Y$ gilt, dann nennt man $\mathrm{E}_{\psi }\left(y^{0}\right)$ einen höchsten $y$-Schnitt von $\mathrm{E}_{\psi }$. Wenn es einen Punkt $x^{0}\in X$ mit $z_{x^{0}}\leq z_{x},\, \forall x\in X$ gibt, dann bezeichnet man $h_{\psi }\left(x^{0}\right)$ einen tiefsten $x$-Schnitt des Hypographen. Seien nun $x^{0}\in X,\, y^{0}\in Y$ Punkte mit diesen Eigenschaften, so gilt: \begin{eqnarray*} z_{y^{0}}=\psi \left(x_{y^{0}},y^{0}\right) & = & \max _{y\in Y}\min _{x\in X}\psi \left(x,y\right)\\ z_{x^{0}}=\psi \left(x^{0},x_{x^{0}}\right) & = & \min _{x\in X}\max _{y\in Y}\psi \left(x,y\right)\\ \Rightarrow \, z_{y^{0}}=\psi \left(x_{y^{0}},y^{0}\right) & \leq & \psi \left(x^{0},y^{0}\right)\leq \psi \left(x^{0},y_{x^{0}}\right)=z_{x^{0}}\\ \Rightarrow \, \max _{y\in Y}\min _{x\in X}\psi \left(x,y\right) & \leq & \psi \left(x^{0},y^{0}\right)\leq \min _{x\in X}\max _{y\in Y}\psi \left(x,y\right) \end{eqnarray*} Wenn $z_{y^{0}}=z_{x^{0}}$, d.h. wenn \[ \max _{y\in Y}\min _{x\in X}\psi \left(x,y\right)=\psi \left(x^{0},y^{0}\right)=\min _{x\in X}\max _{y\in Y}\psi \left(x,y\right)\] gilt, hat $\left(x^{0},y^{0}\right)$ die Eigenschaft, daß der entsprechende $y^{0}$-Schnitt ein höchster $y$-Schnitt des Epigraphen $\mathrm{E}_{\psi }$ $(y\in Y)$ ist und der entsprechende $x^{0}$-Schnitt ein tiefster $x$-Schnitt des Hypographen $h_{\psi }$ $(x\in X)$ ist. \begin{description} \item [Lemma~8.1]~ Es seien $f_{1}\left(x\right),\ldots ,f_{k}\left(x\right)$ konvexe Funktionen definiert auf einer nichtleeren konvexen Teilmenge $X\subseteq \R ^{n}$. Dann ist die Menge \[ M':=\left\{ \left.x\in X\right|f_{j}\left(x\right)<0,\, j=1,\ldots ,k\right\} \] leer, gdw. es einen Punkt $\tilde{\mu }\in \R _{+}^{k}$ mit $\tilde{\mu }\neq 0$ gibt, so daß gilt: \[ \sum _{j=1}^{k}\tilde{\mu }_{j}f_{j}\left(x\right)\geq 0,\, \forall x\in X.\] \begin{description} \item [Bew.:]Vorbetrachtungen: $\forall x\in \R ^{k}$ ist die Menge $M'\left(x\right)$ konvex. \begin{description} \item [Beh.:]Die Menge $A:=\left\{ \left.r\in \R ^{k}\right|M'\left(r\right)\neq \emptyset \right\} $ ist konvex und $k$-dimensional. \begin{enumerate} \item Konvexität: Es seien $x^{0}\in X$ und $r_{j}^{0}>f_{j}\left(x^{0}\right),j=1,\ldots ,k.$ Wegen $x^{0}\in M'\left(r^{0}\right)$ ist $M'\left(r^{0}\right)\neq \emptyset $ und daher auch $A\neq \emptyset .$ Für bel. Punkte $v^{1},v^{2}$ der Menge $A$ gilt $M\left(r^{i}\right)\neq \emptyset ,i=1,2.$ $\Rightarrow \, \exists x^{i}\in X$ mit $f_{j}\left(x^{i}\right)\leq r_{j}^{i},j=1,\ldots ,k,i=1,2$ Konv. $\Rightarrow $ Sei $\lambda _{1},\lambda _{2}\geq 0$ mit $\lambda _{1}+\lambda _{2}=1:$\[ f_{j}\left(\lambda _{1}x^{1}+\lambda _{2}x^{2}\right)\leq \lambda _{1}f\left(x^{1}\right)+\lambda _{2}f\left(x^{2}\right)\leq \lambda _{1}r_{j}^{1}+\lambda _{2}r_{j}^{2},\, j=1,\ldots ,k\] $\lambda _{1}x^{1}+\lambda _{2}x^{2}\in X$ konvex $\Rightarrow \, M'\left(\lambda _{1}r^{1}+\lambda _{2}r^{2}\right)\neq \emptyset \, \Rightarrow \, \lambda _{1}r^{1}+\lambda _{2}r^{2}\in A.$ \item $k$-dimensional: Zu jedem $v^{0}\in A$ gibt es ein Pkt. $x^{0}\in X$ mit $f_{j}\left(x^{0}\right)0$ ex. Wegen $\left(*\right)$ liegen für $j_{0}\in \left\{ 1,\ldots ,k\right\} $ die Halbgeraden \[ P_{j_{0}}:=\left\{ \left.v\in \R ^{n}\right|v_{j}=\tilde{v}_{j},j\in \left\{ 1,\ldots ,k\right\} \setminus \left\{ j_{0}\right\} ,v_{j_{0}}=\tilde{v}_{j_{0}}+t,t\geq 0\right\} \] in der Menge $A.$ \[ \Rightarrow \, \tilde{u}^{T}\tilde{v}+\tilde{u}_{j_{0}}t\geq 0\, \forall t\geq 0\, \Rightarrow \, \tilde{u}_{j_{0}}\geq 0\, \forall j_{0}\in \left\{ 1,\ldots ,k\right\} .\, \left(**\right)\] Es seien $\hat{x}\in X$ bel. fix und $t>0$ bel. fix. Weiter sei $v\left(\hat{x},t\right)$ ein Pkt. mit den Koo. $v_{j}\left(\hat{x},t\right):=f_{j}\left(\hat{x}\right)+t,j=1\ldots ,k$ in $\R ^{k}.$ \begin{eqnarray*} \Rightarrow \, f_{j}\left(\hat{x}\right) & < & v_{j}\left(\hat{x},t\right),j=1,\ldots ,k.\\ \Rightarrow \, v\left(\hat{x},t\right) & \in & A\\ \stackrel{\left(**\right)}{\Rightarrow }\, \tilde{u}^{T}v\left(\hat{x},t\right) & \geq & 0,\, \hat{x}\in X,t>0\\ \Rightarrow \, \sum _{j=1}^{k}\tilde{u}_{j}f_{j}\left(x\right)+t\cdot \sum _{j=1}^{k}\tilde{u}_{j}\geq 0,\, x\in X,t & > & 0 \end{eqnarray*} Da $t>0$ bel. $\Rightarrow $ Beh. \end{description} $\left(\Leftarrow \right)$ Ann.: Sei $M'\neq \emptyset $ und $x'\in M'$ bel., dann gilt für jedes $u\in \R _{+}^{k}$ mit $u\neq 0$ die Ungl. $\sum _{j=1}^{k}\mu _{j}f_{j}\left(x'\right)<0.$ Wid. zur Vor. \end{description} \item [Bezeichnung~8.1]~ Eine eindeutige Abbildung von $\R ^{n}$ in $\R ^{*}=\R \cup \left\{ -\infty ,\infty \right\} $ heißt verallgemeinerte Funktion. \item [Bezeichnung~8.2]~ Es sei $f$ eine über einer nichtleeren Menge $M\subseteq \R ^{n}$ definierte Funktion bzw. verallgemeinerte Funktion. Dann nennt man $\underline{f}\left(x\right):=\underline{\lim _{\varepsilon \rightarrow 0}}\left\{ \left.f\left(z\right)\right|z\in U\left(x,\varepsilon \right)\cap M\right\} ,\, x\in c\! \ell M$ die der verallgemeinerten Funktion $f\left(x\right)$ zugeordnete verallgemeinerte Funktion. \item [Lemma~8.2]~ Es sei $f\left(x\right)$ eine auf $M\subseteq \R ^{n},\, M\neq \emptyset $ definierte Funktion.Dann besitzt $\underline{f}\left(x\right)$ die folgenden Eigenschaften: \begin{enumerate} \item $\underline{f}\left(x\right)\leq f\left(x\right),\, \forall x\in M$ \item für jedes $x\in M$ und für jede Punktfolge $\left\{ x^{i}\right\} _{i=1}^{\infty },\, x^{i}\in M\, \left(i=1,2,\ldots \right)$ mit $\lim _{i\to \infty }x^{i}=x$ gilt: $\underline{f}\left(x\right)=\underline{\lim _{i\to \infty }f\left(x^{i}\right)}$ \end{enumerate} \item [Definition~8.1]~ Es sei $f\left(x\right)$ eine auf $M\subseteq \R ^{n},\, M\neq \emptyset $ definierte Funktion und $\underline{f}\left(x\right)$ mit $\bar{x}\in c\! \ell M$ die ihr gemäß Bezeichnung 8.2 zugeordnete verallgemeinerte Funktion. $f\left(x\right)$ heißt in $x^{0}\in M$ unterhalbstetig (uhs), wenn $\underline{f}\left(x^{0}\right)=f\left(x^{0}\right)$. $f\left(x\right)$ heißt uhs auf $M$, wenn $f\left(x\right)$ uhs $\forall x\in M$, d.h. $\underline{f}\left(x\right)=f\left(x\right),\, \forall x\in M.$ \item [Lemma~8.3]~ Sei $M$ eine nichtleere und abgeschlossene Menge im $\R ^{n}$ und $f$ eine auf $M$ definierte Funktion. Dann sind folgende Aussagen äquivalent: \begin{enumerate} \item $f\left(x\right)$ ist uhs auf $M$ \item der Epigraph $\mathrm{E}_{f}:=\left\{ \left.\left(x,x_{n+1}\right)\in \R ^{n+1}\right|x_{n+1}\geq f\left(x\right),\, x\in M\right\} $ ist eine abgeschlossene Menge \item für jede Zahl $\alpha \in \R $ ist die obere Niveaumenge $M_{\alpha }:=\left\{ \left.x\in \R ^{n}\right|f\left(x\right)\leq \alpha ,\, x\in M\right\} $ abgeschlossen im $\R ^{n}.$ \end{enumerate} \begin{description} \item [Bew.:]~ \begin{description} \item [1$\Rightarrow $2:]Sei $f\left(x\right)$ uhs. auf $M,$ und es sei $\left(x^{0},x_{n+1}^{0}\right)$ ein bel. HP in $\mathrm{E}_{f}.$ Dann gibt es eine Pkt.folge $\left\{ \left(x^{i},x_{n+1}^{i}\right)\right\} \in \mathrm{E}_{f}$ mit \begin{eqnarray*} \lim _{i\rightarrow \infty }x^{i} & = & x^{0},\\ \lim _{i\rightarrow \infty }x_{n+1}^{i} & = & x_{n+1}^{0}. \end{eqnarray*} \begin{eqnarray*} \stackrel{2}{\Rightarrow }\, x_{n+1}^{i} & \geq & f\left(x^{i}\right)\\ \Rightarrow \, \underline{\lim }_{i\rightarrow \infty }x_{n+1}^{i}=\lim _{i\rightarrow \infty }x_{n+1}^{i}=x_{n+1}^{0} & \geq & \lim _{i\rightarrow \infty }f\left(x^{i}\right) \end{eqnarray*} L.8.2,uhs. $\Rightarrow \, x_{n+1}^{0}\geq \underline{f}\left(x^{0}\right)=f\left(x^{0}\right)\, \Rightarrow \, \left(x^{0},x_{n+1}^{0}\right)\in \mathrm{E}_{f}.$ \item [2$\Rightarrow $3:]Sei $\mathrm{E}_{f}$ eine in $\R ^{n+1}$ abg. Menge. Sei $\alpha \in \R $ bel. \begin{eqnarray*} R_{\alpha } & := & \left\{ \left.\left(x,x_{n+1}\right)\in \R ^{n+1}\right|x\in \R ^{n},x_{n+1}=\alpha \right\} \\ \Rightarrow \, R_{\alpha }\cap \mathrm{E}_{f} & = & \left\{ \left.\left(x,x_{n+1}\right)\in \R ^{n+1}\right|\alpha \geq f\left(x\right),x\in M,x_{n+1}=\alpha \right\} \end{eqnarray*} ist als Durchschnitt abg. Mengen ebenfalls abgeschlossen. \item [3$\Rightarrow $1:]Ann.: $\exists x^{0}\in M$ mit $\underline{f}\left(x^{0}\right)0$ derart, daß $\inf \left\{ \left.f\left(x\right)\right|x\in U\left(x^{0},\varepsilon \right)\cap M\right\} <\alpha ,\, \varepsilon \in \left(0,\varepsilon _{0}\right).$ Für bel. Folge $\left\{ \varepsilon _{k}\right\} $ mit $0<\varepsilon _{k+1}<\varepsilon _{k}<\varepsilon _{0}$ gilt daher \[ \inf \left\{ \left.f\left(x\right)\right|x\in U\left(x^{0},\varepsilon _{k}\right)\cap M\right\} <\alpha .\] $\Rightarrow \, \exists \left\{ x^{k}\right\} $ mit \begin{itemize} \item $x^{k}\in U\left(x^{0},\varepsilon _{k}\right)\cap M,\, \lim _{k\rightarrow 0}x^{k}=x^{0}$ \item $\inf \left\{ \left.f\left(x\right)\right|x\in U\left(x^{0},\varepsilon _{k}\right)\cap M\right\} \leq f\left(x^{k}\right)<\alpha .$ \end{itemize} $\stackrel{2}{\Rightarrow }\left(x^{k},\alpha \right)\in \mathrm{E}_{f};\, \lim _{k\rightarrow \infty }\left(x^{k},\alpha \right)=\left(x^{0},\alpha \right)\, \Rightarrow \, \left(x^{k},\alpha \right)\in R_{\alpha }\cap \mathrm{E}_{f}.$ Nach Vor. ist $M_{\alpha }$ abg. $\Rightarrow \, \lim _{k\rightarrow \infty }\left(x^{k},\alpha \right)=\left(x^{0},\alpha \right)\in R_{\alpha }\cap E_{f}\, \Rightarrow \, \left(x^{0},\alpha \right)\in \mathrm{E}_{f}.$ Wid. zu $\left(*\right)$ $\Rightarrow \, f\left(x^{0}\right)\geq f\left(x\right)\, \forall x\in M.$ L.8.2a $\Rightarrow \, \underline{f}\left(x\right)=f\left(x\right)\: \forall x\in M\, \Rightarrow \, f\left(x\right)$ ist uhs. auf $M\, \Rightarrow $ 1. \end{description} \end{description} \item [Lemma~8.4]~ Es sei $X$ eine nichtleere, konvexe und kompakte Menge in $\R ^{n}$, $Y$ eine nichtleere Menge in $\R ^{m}$ und $\psi \left(x,y\right)$ eine auf $X\times Y$ definierte Funktion, die in jedem Punkt $y\in Y$ uhs und konvex auf $X$ ist. Es sei $\Phi =\left\{ \left.x\in X\right|\psi \left(x,y\right)\leq 0,\, y\in Y\right\} $. Dann gibt es Punkte $y_{k}^{j}\in Y_{k}\, \left(j=1,\ldots ,k\right)$ und einen Punkt $\tilde{u}\in \R _{+}^{k}$ mit $\tilde{u}\neq 0$, $\sum _{j=1}^{k}\tilde{u}_{j}\psi \left(x,y^{j}\right)>0,\, x\in X$. \begin{description} \item [Bew.:]Es seien $y\in Y$ und $\varepsilon >0$ bel. fix. Sei \[ C\left(y,\varepsilon \right):=\left\{ \left.x\in X\right|\psi \left(x,y\right)\leq \varepsilon \right\} .\] Nach S. 2.2 ist $\psi \left(\cdot ,y\right)$ uhs. auf $X$ und $X$ kompakt. L.8.3c $\Rightarrow \, C\left(y,\varepsilon \right)$ kompakt. Wir betrachten $C^{*}\left(y,\varepsilon \right):=\R ^{n}\setminus C\left(y,\varepsilon \right)$ offen und zsh. Beh.: $\bigcap _{y\in Y,\varepsilon >0}C\left(y,\varepsilon \right)=\emptyset .$ Ann.: $\bigcap _{y\in Y,\varepsilon >0}C\left(y,\varepsilon \right)\neq \emptyset \, \Rightarrow \, \exists \hat{x}\in X$ mit $\psi \left(\hat{x},x\right)\leq \varepsilon \, \forall y\in Y\forall \varepsilon >0\, \Rightarrow \psi \left(\hat{x},y\right)\leq 0\, \forall y\in Y$ Wid. $\Rightarrow \, \forall x\in X\, \exists y_{x}\in Y,\varepsilon _{x}>0:\, x\in C^{x}\left(y_{x},\varepsilon _{x}\right)$ $\Rightarrow $ Das Sys. $\left\{ \left.C^{*}\left(y,\varepsilon \right)\right|y\in Y,\varepsilon >0\right\} $ offener Mengen im $\R ^{n}$ überdeckt die kompakte Menge $X.$ Nach dem Borrelschen Überdeckungssatz gibt es endl. viele Mengen dieses Systems, die ebenfalls $X$ überdecken. Es seien dies die Mengen $C^{*}\left(y_{j},\varepsilon _{j}\right)\, \left(j=1,\ldots ,k\right).$ \[ \Rightarrow \, \bigcap _{j=1}^{k}C\left(y_{j},\varepsilon _{j}\right)=\emptyset \, \Rightarrow \, \left\{ \left.x\in X\right|\psi \left(x,y_{j}\right)<\varepsilon _{j},j=1,\ldots ,k\right\} =\emptyset \] L. 8.1 (hier benötigen wir Konvexivität) $\Rightarrow \, \exists \tilde{u}\in \R _{+}^{k}$ mit $\tilde{u}\neq 0$, \[ \sum _{j=1}^{k}\tilde{u}_{j}\left(\psi \left(x,y_{j}\right)-\varepsilon _{j}\right)\geq 0,\, x\in X.\] Wegen $\varepsilon _{j}>0$ folgt \[ \sum _{j=1}^{k}\tilde{u}_{j}\psi \left(x,y_{j}\right)\geq \sum _{j=1}^{k}\tilde{u}_{j}\varepsilon _{j}>0,\, x\in X\, \Rightarrow \, \textrm{Beh}.\] \end{description} \item [Lemma~8.5]~(Verallg. des Satzes von Weierstraß) Es sei $f\left(x\right)$ eine auf einer nichtleeren kompakten Menge $M\subseteq \R ^{n}$ definierte Funktion, die uhs (bzw. ohs) auf dieser Menge ist. Dann gibt es einen Punkt $x^{1}\in M$ (bzw. $x^{2}\in M$), so daß:\[ f\left(x^{1}\right)=\min _{x\in M}f\left(x\right)\, \, (\textrm{bzw}.\, f\left(x^{2}\right)=\max _{x\in M}f\left(x\right))\] \item [Satz~8.1](Minimax-Prinzip) Es seinen $X\subseteq \R ^{n},\, Y\subseteq \R ^{m}$ nichtleere kompakte und konvexe Mengen; weiter sei $\psi \left(x,y\right)$ eine auf $X\times Y$ definierte Funktion mit folgenden Eigenschaften: \begin{enumerate} \item Für jeden Punkt $y\in Y$ ist sie uhs und konvex auf $X$. \item Für jeden Punkt $x\in X$ ist sie ohs und konkav auf $Y$. \end{enumerate} Dann existiert ein Sattelpunkt $\left(x^{0},y^{0}\right)\in X\times Y$ der Funktion $\psi \left(x,y\right)$ auf $X\times Y$, und es gilt:\[ \max _{y\in Y}\min _{x\in X}\psi \left(x,y\right)=\psi \left(x^{0},y^{0}\right)=\min _{x\in X}\max _{y\in Y}\psi \left(x,y\right)\] \begin{description} \item [Bew.:]Anw. von Lemma 8.5:\begin{eqnarray*} f\left(x\right):=\sup _{y\in Y}\psi \left(x,y\right) & = & \max _{y\in Y}\psi \left(x,y\right)\, \forall x\in X\\ g\left(y\right):=\inf _{x\in X}\psi \left(x,y\right) & = & \min _{x\in X}\psi \left(x,y\right)\, \forall y\in Y \end{eqnarray*} Offenbar gilt: $f\left(x\right)$ ist auf $X$ konvex und $g\left(y\right)$ auf $Y$ konkav. Nach Lemma 8.3 folgt \begin{eqnarray*} \mathrm{E}_{\psi }\left(y\right) & = & \left\{ \left.\left(x,z\right)\in \R ^{n}\times \R \right|z\geq \psi \left(x,y\right),x\in X\right\} ,y\in Y,\\ h\left(x\right) & = & \left\{ \left.\left(x,z\right)\in \R ^{n}\times \R \right|z\leq \psi \left(x,y\right),y\in Y\right\} ,x\in X \end{eqnarray*} abg. und konvex.\begin{eqnarray*} \rightarrow \, \mathrm{E}_{f}:=\bigcap _{y\in Y}\mathrm{E}_{\psi }\left(y\right) & = & \left\{ \left.\left(x,z\right)\in \R ^{n}\times \R \right|z\geq \max _{y\in Y}\psi \left(x,y\right),x\in X\right\} \\ h_{g}:=\bigcap _{x\in X}h_{\psi }\left(x\right) & = & \left\{ \left.\left(x,z\right)\in \R ^{n}\times \R \right|z\leq \min _{x\in X}\psi \left(x,y\right),y\in Y\right\} \end{eqnarray*} abg. und konvex. L.8.3. $\rightarrow \, f\left(x\right)$ uhs. auf $X$ und $g\left(y\right)$ ohs. auf $Y$. $\left(*\right)$ Nach L. 8.5 ex. Zahlen $\mu _{1},\mu _{2}$ mit \begin{eqnarray*} \mu _{1}:=\inf _{x\in X}f\left(x\right)=\min _{x\in X}f\left(x\right) & = & \min _{x\in X}\max _{y\in Y}\psi \left(x,y\right)\\ \mu _{2}:=\sup _{y\in Y}g\left(y\right)=\max _{y\in Y}g\left(y\right) & = & \max _{y\in Y}\min _{x\in X}\psi \left(x,y\right) \end{eqnarray*} Es seien $x^{0},y^{0}$ Pkt. mit $f\left(x^{0}\right)=\mu _{1}=\min _{x\in X}f\left(x\right),\, g\left(y^{0}\right)=\mu _{2}=\max _{y\in Y}g\left(y\right)$ \begin{eqnarray*} \Rightarrow \, \mu _{1}=f\left(x^{0}\right)=\max _{y\in Y}\psi \left(x^{0},y\right) & \geq & \psi \left(x^{0},y^{0}\right)\\ \mu _{2}=g\left(y^{0}\right)=\min _{x\in X}\psi \left(x,y^{0}\right) & \leq & \psi \left(x^{0},y^{0}\right)\\ \Rightarrow \, \mu _{2}\leq \psi \left(x^{0},y^{0}\right) & \leq & \mu _{1} \end{eqnarray*} z.z.: $\mu _{2}=\mu _{1}.$ $\left(*\right)\, \Rightarrow \, \max _{y\in Y}\psi \left(x,y\right)\geq \mu _{1},\, x\in X$ Für bel. $y\in Y$ und bel. $\varepsilon >0$ def. wir \begin{eqnarray*} C'\left(y,\varepsilon \right) & := & \left\{ \left.x\in X\right|\psi \left(x,y\right)-\mu _{1}+\varepsilon \leq 0\right\} \\ C'_{\varepsilon } & := & \bigcap _{y\in Y}C'\left(y,\varepsilon \right) \end{eqnarray*} Beh.: $C'_{\varepsilon }=\emptyset .$ Ann.: $C'_{\varepsilon }\neq \emptyset .$ $\Rightarrow \, \exists x_{\varepsilon }\in X:\psi \left(x_{\varepsilon },y\right)-\mu _{1}+\varepsilon \leq 0\, \forall y\in Y$ $\Rightarrow \, \exists y_{x_{\varepsilon }}\in Y:\, \max _{y\in Y}\psi \left(x_{\varepsilon },y\right)=\psi \left(x_{\varepsilon },y_{x_{\varepsilon }}\right)<\mu _{1}$ Wid. Nach Lemma 8.4 gibt es Pkt.e $y^{j}\in Y\, \left(j=1,\ldots ,k\right)$ und $\tilde{u}\in \R _{+}^{k}$ mit \[ \tilde{u}\neq 0,\, \sum _{j=1}^{k}\tilde{u}_{j}\left[\psi \left(x,y^{j}\right)-\mu _{j}+\varepsilon _{j}\right]>0,x\in X.\] Da o.B.d.A. $\sum _{j=1}^{n}\tilde{u}_{j}=1$ vorausgesetzt werden kann, und da für $x\in X\, \psi \left(x,y\right)$ konkav auf $Y$ ist, gilt (mit Jensen's Ungl.) \[ \sum _{j=1}^{n}\tilde{u}_{j}\psi \left(x,y^{j}\right)\leq \psi \left(x,\sum _{j=1}^{k}\tilde{u}_{j}y^{j}\right)=\psi \left(x,\tilde{y}\right),\, x\in X\] Dabei gilt $\tilde{y}:=\sum _{j=1}^{k}\tilde{u}_{j}y^{j}\in Y\, \Rightarrow \, \psi \left(x,\tilde{y}\right)-\mu _{1}+\varepsilon >0\, \forall x\in X$ \begin{eqnarray*} \stackrel{\left(*\right)}{\Rightarrow }\, \mu _{2}=\max _{y\in Y}\min _{x\in X}\psi \left(x,y\right) & \geq & \min _{x\in X}\psi \left(x,\tilde{y}\right)\geq \mu _{1}+\varepsilon \end{eqnarray*} $\varepsilon >0$ bel. $\Rightarrow \, \mu _{2}\geq \mu _{1}\, \Rightarrow \, \mu _{2}=\psi \left(x^{0},y^{0}\right)=\mu _{1}\, \Rightarrow $ Beh. \end{description} \item [Bemerkung~8.2]~ Die Aussage des Satzes bleibt erhalten, wenn wir die Konvex- bzw. Konkavität von $\psi \left(x,y\right)$ leicht abschwächen. (Satz von Soin-K...) \item [Definition~8.2]~ \begin{enumerate} \item $F\left(x\right)$ heißt quasikonvex auf einer konvexen Menge $M$, wenn $\left\{ \left.x\in \R ^{n}\right|F\left(x\right)\leq \lambda \right\} $ konvex $\forall \lambda \in \R $. \item $F\left(x\right)$ heißt quasikonkav auf einer konvexen Menge $M$, wenn $\left\{ \left.x\in \R ^{n}\right|F\left(x\right)\leq \lambda \right\} $ konkav $\forall \lambda \in \R $. \end{enumerate} \item [Bemerkung~8.3]~ Unter gewissen zusätzlichen Bed. läßt sich der Satz auch für nicht kompakte Mengen anwenden. \item [Satz~8.2](Minimax-Satz von J. v. Neumann in der Spieltheorie) Es seien $\psi \left(x,y\right):=\sum _{i=1}^{n}\sum _{j=1}^{m}a_{ij}x_{i}y_{j}$,\\ $X:=\left\{ \left.x\in \R ^{n}\right|x_{i}\geq 0,\, i=1,\ldots ,n,\, \sum x_{i}=1\right\} $\\ $Y:=\left\{ \left.y\in \R ^{n}\right|y_{j}\geq 0,\, j=1,\ldots ,m,\, \sum y_{j}=1\right\} $\\ Dann existiert ein Punkt $\left(x^{0},y^{0}\right)\in X\times Y$ mit:\[ \max _{y\in Y}\min _{x\in X}\left\{ \sum _{i=1}^{n}\sum _{j=1}^{m}a_{ij}x_{i}y_{j}\right\} =\sum _{i=1}^{n}\sum _{j=1}^{m}a_{ij}x_{i}^{0}y_{j}^{0}=\min _{x\in X}\max _{y\in Y}\left\{ \sum _{i=1}^{n}\sum _{j=1}^{m}a_{ij}x_{i}y_{j}\right\} \] \end{description} \begin{thebibliography}{1} \bibitem[1]{1}Nozicka, Grygerva, Lommetzsch; Geometrie konvexer Mengen und konvexer Analysis, Akademie-Verlag, 1988 \bibitem[2]{2}Jougen, Jonker: ??? \bibitem[3]{3}Bank, Guddat, Klatte, Kummer, Taromer: Nonlinear parametric Optimization, Akademie Verlag, Berlin 1982 \bibitem[4]{4}Nozicka, Guddat,...: Linear parametric Optimization, Akademie-Verlag, 1974 \bibitem[5]{5}Guddat: Parametric optimization: singularities, pathfollowing and jumps, Teubner 1990 \bibitem[6]{6}Elster et.al.: Einführung in die nichtlineare Optimierung, Leipzig 1977\end{thebibliography} \end{document}