Satz von Ky Fan

In der Theorie der konvexen Funktionen, einem Teilgebiet der Mathematik zwischen Funktionalanalysis und numerischer Mathematik, wurde das Von Neumann'sche Minimax-Theorem (englisch Von Neumann minimax theorem) von verschiedenen Autoren und auf vielfache Weise verallgemeinert und abgewandelt. Die dabei gewonnenen Resultate nennt man Minimaxsätze (englisch minimax theorems). Einer der vielgenannten Minimaxsätze ist derjenige Lehrsatz, welcher von dem Mathematiker Ky Fan im Jahre 1953 vorgelegt wurde und den man auch als Satz von Ky Fan bezeichnet. Einen dem Ky Fan'schen sehr ähnlichen Minimaxsatz hat Heinz König im Jahre 1968 geliefert.

Formulierung des Satzes

An die Monographie von Peter Kosmol anschließend lässt sich der Ky Fan'sche Satz wie folgt formulieren:

Gegeben seien eine nichtleere Menge $X$ und ein nichtleerer kompakter topologischer Raum $Y$ sowie eine reellwertige Funktion $f\colon X\times Y\to \mathbb {R}$.

Die Funktion $f$ sei F-konkav bezüglich $X$ und F-konvex bezüglich $Y$.

Zudem sei $f(x_{0},{\cdot })\colon Y\to \mathbb {R} \;,\;y\mapsto f(x_{0},y)\;,\;$ für jedes $x_{0}\in X$ eine unterhalbstetige Funktion.

Dann gilt

$\sup _{x\in X}\inf _{y\in Y}{f(x,y)}=\inf _{y\in Y}\sup _{x\in X}{f(x,y)}$.

Von Neumann'sches Minimax-Theorem

Der Satz von Ky Fan führt direkt zu der folgenden Version des Von Neumann'schen Minimax-Theorems:

Gegeben seien nichtleere kompakte, konvexe Teilmengen $X\subseteq \mathbb {R} ^{m}\;(m\in \mathbb {N} )$ und $Y\subseteq \mathbb {R} ^{n}\;(n\in \mathbb {N} )$ sowie eine stetige Funktion $f\colon X\times Y\to \mathbb {R}$.

Für jedes $x_{0}\in X$ sei $f(x_{0},{\cdot })\colon Y\to \mathbb {R}$ ein konvexes Funktional und für jedes $y_{0}\in Y$ sei $f({\cdot },y_{0})\colon X\to \mathbb {R}$ ein konkaves Funktional.

Dann gibt es einen Sattelpunkt $({\hat {x}},{\hat {y}})$ von $f$ und es gilt

$\max _{x\in X}\min _{y\in Y}{f(x,y)}=f({\hat {x}},{\hat {y}})=\min _{y\in Y}\max _{x\in X}{f(x,y)}$.

Geläufiger als diese Version des Von Neumann'schen Minimax-Theorems ist indes eine, bei der das obige Funktional direkt abhängig ist von einer reellen quadratischen Matrix und die nach Beckenbach/Bellmann folgendermaßen zu formulieren ist:

Gegeben seien das reelle Simplex $\Delta =\{x\in \mathbb {R} ^{n}\colon x_{i}\geq 0\,(i=1,\ldots ,n)\ {\text{und}}\ \sum _{i=1}^{n}{x_{i}}=1\}$ sowie eine Matrix $A\in {\mathbb {R} }^{n\times n}$.

Dann gilt die Ungleichung

$\max _{x\in \Delta }\min _{y\in \Delta }{\sum _{i,j=1}^{n}\left(x_{i}\cdot a_{ij}\cdot y_{j}\right)}=\min _{y\in \Delta }\max _{x\in \Delta }{\sum _{i,j=1}^{n}\left(x_{i}\cdot a_{ij}\cdot y_{j}\right)}$.

Allgemeiner Hintergrund

Dem Minimaxsatz liegt ein allgemeiner Satz der Ordnungstheorie zugrunde:

Gegeben seien nichtleere Mengen $X$ und $Y$ sowie eine numerische Funktion $f\colon X\times Y\to {\bar {\mathbb {R} }}$.

Dann gilt

$\sup _{x\in X}\inf _{y\in Y}{f(x,y)}\leq \inf _{y\in Y}\sup _{x\in X}{f(x,y)}$.

Gibt es dabei ein Element $({\hat {x}},{\hat {y}})\in X\times Y$ mit $f(x,{\hat {y}})\leq {f({\hat {x}},{\hat {y}})}\leq {f({\hat {x}},y)}$ für alle $x\in X$ und alle $y\in Y$, so gilt sogar

$\sup _{x\in X}\inf _{y\in Y}{f(x,y)}=f({\hat {x}},{\hat {y}})=\inf _{y\in Y}\sup _{x\in X}{f(x,y)}$.

Ungleichung von Ky Fan

Im Zusammenhang mit dem obigen Minimaxsatz von Ky Fan ist eine Ungleichung erwähnenswert, die von Ky Fan im Jahre 1972 vorgestellt wurde und die sich nicht nur als gleichwertig mit dem Fixpunktsatz von Brouwer erwiesen hat, sondern überdies eine Reihe von Existenzsätzen der Nichtlinearen Funktionalanalysis nach sich zieht. Diese Ky Fan'sche Ungleichung (englisch Ky Fan's inequality) lässt sich wie folgt angeben:

Gegeben seien ein hausdorffscher topologischer Vektorraum $H$ und darin eine nichtleere, kompakte, konvexe Teilmenge $X\subseteq H$ sowie eine reellwertige Funktion $f\colon X\times X\to \mathbb {R}$.

Es sei jedes Funktional $f(x_{0},{\cdot })\colon X\to \mathbb {R} \;(x_{0}\in X)$ unterhalbstetig und jedes Funktional $f({\cdot },y_{0})\colon X\to \mathbb {R} \;(y_{0}\in X)$ sei quasikonkav.

Dann gilt die Ungleichung

$\inf _{y\in X}\sup _{x\in X}{f(x,y)}\leq \sup _{x\in X}{f(x,x)}$

und dabei gibt sogar einen Raumpunkt ${\hat {y}}\in X$ mit

$\sup _{x\in X}{f(x,{\hat {y}})}=\min _{y\in X}\sup _{x\in X}{f(x,y)}\leq \sup _{x\in X}{f(x,x)}$.

Erläuterungen und Anmerkungen

• Eine Funktion $f\colon X\times Y\to \mathbb {R}$ heißt F-konkav bezüglich $X$, wenn sie folgende Eigenschaft hat:

Es gibt für $x_{1}\in X\;,\;x_{2}\in X\;,\;\kappa \in [0,1]$ stets ein $x_{0}\in X$, so dass für jedes $y\in Y$ die Ungleichung $f(x_{0},y)\geq \kappa f(x_{1},y)+(1-\kappa )f(x_{2},y)$ erfüllt ist.

• Eine Funktion $f\colon X\times Y\to \mathbb {R}$ heißt F-konvex bezüglich $Y$, wenn sie folgende Eigenschaft hat:

Es gibt für $y_{1}\in Y\;,\;y_{2}\in Y\;,\;\lambda \in [0,1]$ stets ein $y_{0}\in Y$, so dass für jedes für jedes $x\in X$ die Ungleichung $f(x,y_{0})\leq \lambda f(x,y_{1})+(1-\lambda )f(x,y_{1})$ erfüllt ist.

• Die Bezeichnungen F-konkav und F-konvex benutzt Peter Kosmol, um darzustellen, dass die Funktion $f$ nach der von Ky Fan gewählten Herangehensweise Merkmale hat, die an Konvexität und Konkavität erinnern und diese dabei sogar verallgemeinern. Es ist nach dieser Herangehensweise nicht notwendig, dass der zugrunde liegende Raum ein linearer Raum ist.
• Jede stetige reellwertige Funktion ist auch unterhalbstetig.
• Ein Element $({\hat {x}},{\hat {y}})\in X\times Y$, welches die in dem obigen allgemeinen Hintergrundsatz aufgeführten Ungleichungen in Bezug auf eine numerische Funktion $f\colon X\times Y\to {\bar {\mathbb {R} }}$ erfüllt, wird auch Sattelpunkt von $f$ genannt.
• Beim Beweis des allgemeinen Hintergrundsatz erweist sich als ausschlaggebend, dass die erweiterten reellen Zahlen ${\bar {\mathbb {R} }}$ einen vollständigen Verband bilden. Der Hintergrundsatz lässt sich also in entsprechender Weise auch auf den Fall ausdehnen, dass die dortige Funktion $f$ in einen solchen abbildet.
• Die obige erste Version des Von Neumann'schen Minimax-Theorems (bzw. eine im Wesentlichen gleichwertige Fassung davon) gibt Philippe G. Ciarlet in seiner Monographie Linear and Nonlinear Functional Analysis with Applications als Ky Fan-Sion theorem (deutsch Satz von Ky Fan und Sion) wieder.
• Die obige zweite Version des Von Neumann'schen Minimax-Theorems folgt offenbar aus der ersten, da das Funktional $(x,y)\mapsto f(x,y)=\sum _{i,j=1}^{n}\left(x_{i}\cdot a_{ij}\cdot y_{j}\right)$ offenbar eine bilineare Abbildung ist.
• Dass die Ungleichung von Ky Fan im Jahre 1972 vorgestellt wurde, weist Jean-Pierre Aubin in seiner Monographie Optima and Equilibria aus, wobei er offenbar Bezug auf das Erscheinungsjahr des Tagungsbandes der Inequalities - III nimmt. Die Tagung selbst fand im September 1969 statt.
• Der Nachweis, dass die Ungleichung von Ky Fan den Brouwer'schen Fixpunktsatz nach sich zieht, ist leicht zu führen. An Aubins Darstellung in Optima and Equilibria anschließend setzt man dazu für eine auf der Einheitskugel $X=D^{n}\subseteq \mathbb {R} ^{n}\;(n\in \mathbb {N} )$ gegebene stetige Selbstabbildung $\phi \colon D^{n}\to D^{n}$ die reellwertige Funktion $f\colon D^{n}\times D^{n}\to \mathbb {R}$ durch $D^{n}\times D^{n}\ni (x,y)\mapsto f(x,y):={\langle y-x,y-\phi (y)\rangle }$ fest, wobei $\langle {\cdot },{\cdot }\rangle \colon \mathbb {R} ^{n}\times \mathbb {R} ^{n}\to \mathbb {R} ,$ das reelle Standardskalarprodukt ist. Dann ist $f$ offenbar stetig und für jedes $y_{0}\in D^{n}$ ist $f({\cdot },y_{0})\colon D^{n}\to \mathbb {R}$ eine affine Abbildung. Damit sind die der Ungleichung von Ky Fan zugrundeliegenden Voraussetzungen erfüllt und es gibt ein ${\hat {y}}\in D^{n}$ mit $\sup _{x\in X}{\langle {\hat {y}}-x,{\hat {y}}-\phi ({\hat {y}})\rangle }\leq 0$. Dies impliziert ${\langle {\hat {y}}-\phi ({\hat {y}}),{\hat {y}}-\phi ({\hat {y}})\rangle }={\|{\hat {y}}-\phi ({\hat {y}})\|}^{2}\leq 0$ und schließlich $\phi ({\hat {y}})={\hat {y}}$.

Literatur

• Jean-Pierre Aubin: Optima and Equilibria. An introduction to nonlinear analysis. Translated from the French by Stephen Wilson (= Graduate Texts in Mathematics. Band 140). Springer Verlag, Berlin 1998, ISBN 3-540-64983-2 (MR1729758). 
• Jean-Pierre Aubin, Ivar Ekeland: Applied Nonlinear Analysis (= Pure and Applied Mathematics (New York). A Wiley-Interscience Series of Texts, Monographs, & Tracts). John Wiley & Sons, Inc., New York 1984, ISBN 0-471-05998-6 (englisch, MR0749753). 
• Edwin F. Beckenbach, Richard Bellman: Inequalities (= Ergebnisse der Mathematik und ihrer Grenzgebiete. Band 30). 4. Auflage. Springer Verlag, Berlin, Heidelberg, New York, Tokyo 1983, ISBN 3-540-03283-5. 
• Jonathan Michael Borwein, Deming Micheal Zhuang: On Fan’s minimax theorem. In: Mathematical Programming. Band 34, 1986, S. 232–234 (MR0838482). 
• Philippe G. Ciarlet: Linear and Nonlinear Functional Analysis with Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA 2013, ISBN 978-1-61197-258-0 (MR3136903). 
• Ivar Ekeland, Roger Temam: Convex analysis and Variational Problems. Translated from the French (= Studies in Mathematics and its Applications. Band 1). North-Holland Publishing Company, Amsterdam, Oxford 1976 (MR0463994). 
• Ky Fan: Minimax theorems. In: Proc. Nat. Acad. Sci. U. S. A. Band 39, 1953, S. 42–47 (MR0055678). 
• Rudolf A. Hirschfeld: On a minimax theorem of K. Fan. In: Nederl. Akad. Wetensch. Proc. Indag. Math. Band 20, 1958, S. 470–474 (MR0099014). 
• Hansgeorg Jeggle: Nichtlineare Funktionalanalysis. Existenz von Lösungen nichtlinearer Gleichungen (= Teubner Studienbücher: Mathematik). B. G. Teubner Verlag, Stuttgart 1979, ISBN 3-519-02057-2 (MR0533478). 
• Jürgen Kindler: Minimaxtheoreme und das Integraldarstellungsproblem. In: Manuscripta Mathematica. Band 29, 1979, S. 277–294 (MR0545045). 
• Heinz König: Über das von Neumannsche Minimax-Theorem. In: Archiv der Mathematik. Band 19, 1968, S. 482–487 (MR0240600). 
• Heinz König, Michael Neumann: Mathematische Wirtschaftstheorie. Mit einer Einführung in die konvexe Analysis (= Mathematical Systems in Economics. Band 100). Anton Hain, Königstein 1986, ISBN 3-445-02393-X (MR0842432). 
• Peter Kosmol: Optimierung und Approximation (= De Gruyter Studium). 2. Auflage. Walter de Gruyter & Co., Berlin 2010, ISBN 978-3-11-021814-5 (MR2599674). 
• J. von Neumann: Zur Theorie der Gesellschaftsspiele. In: Mathematische Annalen. Band 100, 1928, S. 295–320 (MR1512486). 
• John von Neumann, Oskar Morgenstern: Spieltheorie und wirtschaftliches Verhalten. Unter Mitwirkung von F. Docquier. Herausgegeben von F. Sommer. Übersetzt von M. Leppig. Physica-Verlag, Würzburg 1961 (MR0127419). 
• A. Wayne Roberts, Dale E. Varberg: Convex Functions (= Pure and Applied Mathematics. Band 57). Academic Press, New York, San Francisco, London 1973 (MR0442824). 
• R. Tyrrell Rockafellar: Convex Analysis (= Princeton Mathematical Series. Band 28). Princeton University Press, Princeton, NJ 1970 (MR0274683). 
• Oved Shisha (Hrsg.): Inequalities - III. Proceedings of the Third Symposium on Inequalities. Held at The University of California, Los Angeles, September 1–9, 1969. Dedicated to the memory of Theodore S. Motzkin. Academic Press, New York, London 1972, S. 103–113 (englisch, MR0341029). 
• Maurice Sion: On general minimax theorems. In: Pacific Journal of Mathematics. Band 8, 1958, S. 171–176 (MR0097026). 
• Anton Ştefănescu: The minimax theorem without vector space structures. In: Rev. Roumaine Math. Pures Appl. Band 44, 1999, S. 307–313 (MR1837337). 
• Josef Stoer, Christoph Witzgall: Convexity and Optimization in Finite Dimensions. I. (= Die Grundlehren der Mathematischen Wissenschaften in Einzeldarstellungen. Band 163). Springer Verlag, Berlin, Heidelberg, New York 1970 (MR0286498). 
• Frederick A. Valentine: Konvexe Mengen. Übersetzung aus dem Englischen durch E. Heil (= BI-Hochschultaschenbücher. Band 402/402a). Bibliographisches Institut, Mannheim 1968 (MR0226495). 

Siehe auch

• Min-Max-Theorem