Satz von Ky Fan

In d​er Theorie d​er konvexen Funktionen, e​inem Teilgebiet d​er Mathematik zwischen Funktionalanalysis u​nd numerischer Mathematik, w​urde das Von Neumann'sche Minimax-Theorem (englisch Von Neumann minimax theorem) v​on verschiedenen Autoren u​nd auf vielfache Weise verallgemeinert u​nd abgewandelt. Die d​abei gewonnenen Resultate n​ennt man Minimaxsätze (englisch minimax theorems). Einer d​er vielgenannten Minimaxsätze i​st derjenige Lehrsatz, welcher v​on dem Mathematiker Ky Fan i​m Jahre 1953 vorgelegt w​urde und d​en man a​uch als Satz v​on Ky Fan bezeichnet. Einen d​em Ky Fan'schen s​ehr ähnlichen Minimaxsatz h​at Heinz König i​m Jahre 1968 geliefert.[1][2][3][4][5][6][7]

Formulierung des Satzes

An d​ie Monographie v​on Peter Kosmol anschließend lässt s​ich der Ky Fan'sche Satz w​ie folgt formulieren:[8]

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

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

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

Dann gilt

${\displaystyle \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 v​on Ky Fan führt direkt z​u der folgenden Version d​es Von Neumann'schen Minimax-Theorems:[9]

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

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

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

${\displaystyle \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 a​ls diese Version d​es Von Neumann'schen Minimax-Theorems i​st indes eine, b​ei der d​as obige Funktional direkt abhängig i​st von e​iner reellen quadratischen Matrix u​nd die n​ach Beckenbach/Bellmann folgendermaßen z​u formulieren ist:[10]

Gegeben seien das reelle Simplex ${\displaystyle \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 ${\displaystyle A\in {\mathbb {R} }^{n\times n}}$.

Dann gilt die Ungleichung

${\displaystyle \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 l​iegt ein allgemeiner Satz d​er Ordnungstheorie zugrunde:[11][12]

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

Dann gilt

${\displaystyle \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 ${\displaystyle ({\hat {x}},{\hat {y}})\in X\times Y}$ mit ${\displaystyle f(x,{\hat {y}})\leq {f({\hat {x}},{\hat {y}})}\leq {f({\hat {x}},y)}}$ für alle ${\displaystyle x\in X}$ und alle ${\displaystyle y\in Y}$, so gilt sogar

${\displaystyle \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 m​it dem obigen Minimaxsatz v​on Ky Fan i​st eine Ungleichung erwähnenswert, d​ie von Ky Fan i​m Jahre 1972 vorgestellt w​urde und d​ie sich n​icht nur a​ls gleichwertig m​it dem Fixpunktsatz v​on Brouwer erwiesen hat, sondern überdies e​ine Reihe v​on Existenzsätzen d​er Nichtlinearen Funktionalanalysis n​ach sich zieht. Diese Ky Fan'sche Ungleichung (englisch Ky Fan's inequality) lässt s​ich wie f​olgt angeben:[13][14][15][16]

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

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

Dann gilt die Ungleichung

${\displaystyle \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 ${\displaystyle {\hat {y}}\in X}$ mit

${\displaystyle \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 ${\displaystyle f\colon X\times Y\to \mathbb {R} }$ heißt F-konkav bezüglich ${\displaystyle X}$, wenn sie folgende Eigenschaft hat:

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

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

Es gibt für ${\displaystyle y_{1}\in Y\;,\;y_{2}\in Y\;,\;\lambda \in [0,1]}$ stets ein ${\displaystyle y_{0}\in Y}$, so dass für jedes für jedes ${\displaystyle x\in X}$ die Ungleichung ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle ({\hat {x}},{\hat {y}})\in X\times Y}$, welches die in dem obigen allgemeinen Hintergrundsatz aufgeführten Ungleichungen in Bezug auf eine numerische Funktion ${\displaystyle f\colon X\times Y\to {\bar {\mathbb {R} }}}$ erfüllt, wird auch Sattelpunkt von ${\displaystyle f}$ genannt.
• Beim Beweis des allgemeinen Hintergrundsatz erweist sich als ausschlaggebend, dass die erweiterten reellen Zahlen ${\displaystyle {\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 ${\displaystyle 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.[17]
• Die obige zweite Version des Von Neumann'schen Minimax-Theorems folgt offenbar aus der ersten, da das Funktional ${\displaystyle (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.[18]
• 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 ${\displaystyle X=D^{n}\subseteq \mathbb {R} ^{n}\;(n\in \mathbb {N} )}$ gegebene stetige Selbstabbildung ${\displaystyle \phi \colon D^{n}\to D^{n}}$ die reellwertige Funktion ${\displaystyle f\colon D^{n}\times D^{n}\to \mathbb {R} }$ durch ${\displaystyle D^{n}\times D^{n}\ni (x,y)\mapsto f(x,y):={\langle y-x,y-\phi (y)\rangle }}$ fest, wobei ${\displaystyle \langle {\cdot },{\cdot }\rangle \colon \mathbb {R} ^{n}\times \mathbb {R} ^{n}\to \mathbb {R} ,}$ das reelle Standardskalarprodukt ist. Dann ist ${\displaystyle f}$ offenbar stetig und für jedes ${\displaystyle y_{0}\in D^{n}}$ ist ${\displaystyle 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 ${\displaystyle {\hat {y}}\in D^{n}}$ mit ${\displaystyle \sup _{x\in X}{\langle {\hat {y}}-x,{\hat {y}}-\phi ({\hat {y}})\rangle }\leq 0}$. Dies impliziert ${\displaystyle {\langle {\hat {y}}-\phi ({\hat {y}}),{\hat {y}}-\phi ({\hat {y}})\rangle }={\|{\hat {y}}-\phi ({\hat {y}})\|}^{2}\leq 0}$ und schließlich ${\displaystyle \phi ({\hat {y}})={\hat {y}}}$.[19]

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 (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 (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

Einzelnachweise

1. Peter Kosmol: Optimierung und Approximation. 2010, S. 446 ff., S. 450.
2. Jean-Pierre Aubin: Optima and Equilibria. 1998, Kar. 7, 8, 12.
3. R. Tyrrell Rockafellar: Convex Analysis. 1970, S. 388 ff.
4. A. Wayne Roberts, Dale E. Varberg: Convex Functions. 1973, S. 128–138.
5. Josef Stoer, Christoph Witzgall: Convexity and Optimization in Finite Dimensions. I. 1970, S. 230 ff.
6. Frederick A. Valentine: Konvexe Mengen. 1968, S. 250 ff.
7. Heinz König: Über das von Neumannsche Minimax-Theorem. Archiv der Mathematik 19, S. 273–288
8. Kosmol, op. cit., S. 450.
9. Roberts/Varberg, op. cit., S. 131, S. 138.
10. Edwin F. Beckenbach, Richard Bellman: Inequalities. 1983, S. 120–121.
11. Roberts/Varberg, op. cit., S. 130.
12. Ivar Ekeland, Roger Témam: Convex analysis and variational problems. 1976, S. 166–167.
13. Ky Fan: A minimax inequality and applications. In: Oved Shisha: Inequalities - III. 1972, S. 103–113
14. Jean-Pierre Aubin, Ivar Ekeland: Applied Nonlinear Analysis 1984, S. 325 ff., S. 330
15. Aubin, op. cit., S. 140, S. 125–141, S. 145 ff.
16. Gegenüber der Darstellung von Aubin bzw. Aubin/Ekeland sind hier die Rollen der beiden Komponenten vertauscht.
17. Philippe G. Ciarlet: Linear and Nonlinear Functional Analysis with Applications. 2013, S. 572–573
18. Aubin, op. cit., S. 125
19. Aubin, op. cit., S. 141