Set by Ky Fan

In the theory of convex functions , a branch of mathematics between functional analysis and numerical mathematics , was the of Neumann's Minimax Theorem ( English Von Neumann minimax theorem ) generalized by various authors and in many ways and modified. The results of this work are called Minimaxsätze ( English minimax theorems ). One of the much-mentioned minimax theorems is the theorem which was presented by the mathematician Ky Fan in 1953 and which is also known as the theorem of Ky Fan . Heinz König delivered a minimax set very similar to Ky Fan's in 1968.

Formulation of the sentence

Following on from Peter Kosmol's monograph, Ky Fan's sentence can be formulated as follows:

Let a non-empty set and a non-empty compact topological space as well as a real-valued function be given . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f\colon X\times Y\to \mathbb {R} }$

Let the function be F-concave with respect to and F-convex with respect to . ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$

In addition, everybody has an ongoing function . ${\displaystyle f(x_{0},{\cdot })\colon Y\to \mathbb {R} \;,\;y\mapsto f(x_{0},y)\;,\;}$ ${\displaystyle x_{0}\in X}$

Then applies

${\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's Minimax Theorem

Ky Fan's theorem leads directly to the following version of Von Neumann's Minimax theorem:

Given are non-empty, compact , convex subsets and a continuous function . ${\displaystyle X\subseteq \mathbb {R} ^{m}\;(m\in \mathbb {N} )}$ ${\displaystyle Y\subseteq \mathbb {R} ^{n}\;(n\in \mathbb {N} )}$ ${\displaystyle f\colon X\times Y\to \mathbb {R} }$

For each is a convex functional and each is a concave functional. ${\displaystyle x_{0}\in X}$ ${\displaystyle f(x_{0},{\cdot })\colon Y\to \mathbb {R} }$ ${\displaystyle y_{0}\in Y}$ ${\displaystyle f({\cdot },y_{0})\colon X\to \mathbb {R} }$

Then there is a saddle point of and it applies ${\displaystyle ({\hat {x}},{\hat {y}})}$ ${\displaystyle f}$

${\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)}}$.

More common than this version of Von Neumann's Minimax theorem is one in which the above functional is directly dependent on a real square matrix and which, according to Beckenbach / Bellmann, is to be formulated as follows:

The real simplex and a matrix are given . ${\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\}}$ ${\displaystyle A\in {\mathbb {R} }^{n\times n}}$

Then the inequality holds

${\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)}}$.

General background

The minimax theorem is based on a general theorem of order theory:

Given are non-empty sets and as well as a numerical function . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f\colon X\times Y\to {\bar {\mathbb {R} }}}$

Then applies

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

If there are two one element with all and all , so even applies ${\displaystyle ({\hat {x}},{\hat {y}})\in X\times Y}$ ${\displaystyle f(x,{\hat {y}})\leq {f({\hat {x}},{\hat {y}})}\leq {f({\hat {x}},y)}}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$

${\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)}}$.

Inequality of Ky Fan

In connection with the above minimax theorem by Ky Fan, an inequality is worth mentioning, which was presented by Ky Fan in 1972 and which has not only proven to be equivalent to Brouwer's Fixed Point Theorem , but also leads to a number of existence theorems of nonlinear functional analysis . These Ky Fan'sche inequality ( English Ky Fan's inequality ) can be as specify the following:

A Hausdorff topological vector space and a non-empty, compact, convex subset and a real-valued function are given . ${\displaystyle H}$ ${\displaystyle X\subseteq H}$ ${\displaystyle f\colon X\times X\to \mathbb {R} }$

Let every functional be sub-semi-continuous and every functional be quasi-concave . ${\displaystyle f(x_{0},{\cdot })\colon X\to \mathbb {R} \;(x_{0}\in X)}$ ${\displaystyle f({\cdot },y_{0})\colon X\to \mathbb {R} \;(y_{0}\in X)}$

Then the inequality holds

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

and thereby is even a point in space with ${\displaystyle {\hat {y}}\in X}$

${\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)}}$.

Explanations and Notes

• A function is called F-concave with respect to if it has the following property: ${\displaystyle f\colon X\times Y\to \mathbb {R} }$ ${\displaystyle X}$

There is always one , so that the inequality is satisfied for each . ${\displaystyle x_{1}\in X\;,\;x_{2}\in X\;,\;\kappa \in [0,1]}$ ${\displaystyle x_{0}\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle f(x_{0},y)\geq \kappa f(x_{1},y)+(1-\kappa )f(x_{2},y)}$

• A function is called F-convex with respect to if it has the following property: ${\displaystyle f\colon X\times Y\to \mathbb {R} }$ ${\displaystyle Y}$

There is always one , so that for each the inequality is fulfilled for each . ${\displaystyle y_{1}\in Y\;,\;y_{2}\in Y\;,\;\lambda \in [0,1]}$ ${\displaystyle y_{0}\in Y}$ ${\displaystyle x\in X}$ ${\displaystyle f(x,y_{0})\leq \lambda f(x,y_{1})+(1-\lambda )f(x,y_{1})}$

• Peter Kosmol uses the terms F-concave and F-convex to show that the function has features that are reminiscent of convexity and concavity and even generalize them according to the approach chosen by Ky Fan. With this approach, it is not necessary that the underlying space be linear. ${\displaystyle f}$
• Every continuous real-valued function is also subcontinuous.
• An element which satisfies the inequalities listed in the above general background theorem with regard to a numerical function is also called the saddle point of . ${\displaystyle ({\hat {x}},{\hat {y}})\in X\times Y}$ ${\displaystyle f\colon X\times Y\to {\bar {\mathbb {R} }}}$ ${\displaystyle f}$
• When proving the general background theorem, it turns out that the extended real numbers form a complete lattice . The background sentence can therefore also be extended in a corresponding manner to the case that the function there maps into such a function . ${\displaystyle {\bar {\mathbb {R} }}}$ ${\displaystyle f}$
• The above first version of Von Neumann's Minimax Theorem (or an essentially equivalent version of it) is given by Philippe G. Ciarlet in his monograph Linear and Nonlinear Functional Analysis with Applications as Ky Fan-Sion theorem ( German  sentence by Ky Fan and Sion ) again.
• The above second version of Von Neumann's Minimax theorem obviously follows from the first, since the functional is obviously a bilinear mapping . ${\displaystyle (x,y)\mapsto f(x,y)=\sum _{i,j=1}^{n}\left(x_{i}\cdot a_{ij}\cdot y_{j}\right)}$
• That the inequality was presented by Ky Fan in 1972 is shown by Jean-Pierre Aubin in his monograph Optima and Equilibria , apparently referring to the year of publication of the proceedings of the Inequalities - III . The conference itself took place in September 1969.
• It is easy to prove that Ky Fan’s inequality leads to Brouwer’s fixed point theorem. Subsequent to Aubin's representation in Optima and Equilibria , the real-valued function by is fixed for a continuous self-mapping given on the unit sphere , where the real standard scalar product is. Then is obviously continuous and for each there is an affine map. With that the prerequisites underlying the inequality of Ky Fan are fulfilled and there is a with . This implies and eventually . ${\displaystyle X=D^{n}\subseteq \mathbb {R} ^{n}\;(n\in \mathbb {N} )}$ ${\displaystyle \phi \colon D^{n}\to D^{n}}$ ${\displaystyle f\colon D^{n}\times D^{n}\to \mathbb {R} }$ ${\displaystyle D^{n}\times D^{n}\ni (x,y)\mapsto f(x,y):={\langle y-x,y-\phi (y)\rangle }}$ ${\displaystyle \langle {\cdot },{\cdot }\rangle \colon \mathbb {R} ^{n}\times \mathbb {R} ^{n}\to \mathbb {R} ,}$ ${\displaystyle f}$ ${\displaystyle y_{0}\in D^{n}}$ ${\displaystyle f({\cdot },y_{0})\colon D^{n}\to \mathbb {R} }$ ${\displaystyle {\hat {y}}\in D^{n}}$ ${\displaystyle \sup _{x\in X}{\langle {\hat {y}}-x,{\hat {y}}-\phi ({\hat {y}})\rangle }\leq 0}$ ${\displaystyle {\langle {\hat {y}}-\phi ({\hat {y}}),{\hat {y}}-\phi ({\hat {y}})\rangle }={\|{\hat {y}}-\phi ({\hat {y}})\|}^{2}\leq 0}$ ${\displaystyle \phi ({\hat {y}})={\hat {y}}}$

literature

• Jean-Pierre Aubin : Optima and Equilibria . An introduction to nonlinear analysis. Translated from the French by Stephen Wilson (=  Graduate Texts in Mathematics . Volume 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 (=  results of mathematics and their border areas . Volume 30 ). 4th edition. 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 . tape 34 , 1986, pp. 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 . Volume 1 ). North-Holland Publishing Company, Amsterdam, Oxford 1976 ( MR0463994 ).
• Ky Fan: Minimax theorems . In: Proc. Nat. Acad. Sci. USA band 39 , 1953, pp. 42-47 ( MR0055678 ).
• Rudolf A. Hirschfeld: On a minimax theorem of K. Fan . In: Nederl. Akad. Wetensch. Proc. Indag. Math. Band 20 , 1958, pp. 470-474 ( MR0099014 ).
• Hansgeorg Jeggle: Nonlinear Functional Analysis . Existence of solutions to non-linear equations (=  Teubner study books: mathematics ). BG Teubner Verlag, Stuttgart 1979, ISBN 3-519-02057-2 ( MR0533478 ).
• Jürgen Kindler: Minimax theorems and the integral representation problem . In: Manuscripta Mathematica . tape 29 , 1979, pp. 277-294 ( MR0545045 ).
• Heinz König: About von Neumann's Minimax Theorem . In: Archives of Mathematics . tape 19 , 1968, p. 482-487 ( MR0240600 ).
• Heinz König, Michael Neumann: Mathematical Economic Theory. With an introduction to convex analysis (=  Mathematical Systems in Economics . Volume 100 ). Anton Hain, Königstein 1986, ISBN 3-445-02393-X ( MR0842432 ).
• Peter Kosmol: Optimization and Approximation (=  De Gruyter Studies ). 2nd Edition. Walter de Gruyter & Co., Berlin 2010, ISBN 978-3-11-021814-5 ( MR2599674 ).
• J. von Neumann: On the theory of parlor games . In: Mathematical Annals . tape 100 , 1928, pp. 295-320 ( MR1512486 ).
• John von Neumann, Oskar Morgenstern : Game theory and economic behavior . With the assistance of F. Docquier. Edited by F. Sommer. Translated by M. Leppig. Physica-Verlag, Würzburg 1961 ( MR0127419 ).
• A. Wayne Roberts, Dale E. Varberg: Convex Functions (  Pure and Applied Mathematics . Volume 57 ). Academic Press, New York, San Francisco, London 1973 ( MR0442824 ).
• R. Tyrrell Rockafellar : Convex Analysis (=  Princeton Mathematical Series . Volume 28 ). Princeton University Press , Princeton, NJ 1970 ( MR0274683 ).
• Oved Shisha (Ed.): 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, pp. 103-113 ( MR0341029 ).
• Maurice Sion : On general minimax theorems . In: Pacific Journal of Mathematics . tape 8 , 1958, pp. 171-176 ( MR0097026 ).
• Anton Ştefănescu: The minimax theorem without vector space structures . In: Rev. Roumaine Math. Pures Appl. tape 44 , 1999, pp. 307-313 ( MR1837337 ).
• Josef Stoer , Christoph Witzgall : Convexity and Optimization in Finite Dimensions. I. (=  The basic teachings of the mathematical sciences in individual representations . Volume 163 ). Springer Verlag , Berlin, Heidelberg, New York 1970 ( MR0286498 ).
• Frederick A. Valentine : Convex Sets . Translation from English by E. Heil (=  BI university paperbacks . Volume 402 / 402a). Bibliographisches Institut, Mannheim 1968 ( MR0226495 ).

See also

• Min-Max Theorem

Individual evidence

1. ↑ Peter Kosmol: Optimization and Approximation. 2010, p. 446 ff., P. 450.
2. ^ Jean-Pierre Aubin: Optima and Equilibria. 1998, Kar. 7, 8, 12.
3. ^ R. Tyrrell Rockafellar: Convex Analysis. 1970, p. 388 ff.
4. ^ A. Wayne Roberts, Dale E. Varberg: Convex Functions. 1973, pp. 128-138.
5. ^ Josef Stoer, Christoph Witzgall: Convexity and Optimization in Finite Dimensions. I. 1970, p. 230 ff.
6. ↑ Frederick A. Valentine: Convex sets. 1968, p. 250 ff.
7. ↑ Heinz König: About von Neumann's Minimax Theorem. Archive of Mathematics 19, pp. 273–288
8. ↑ Kosmol, op.cit., P. 450.
9. ↑ Roberts / Varberg, op.cit., P. 131, p. 138.
10. ^ Edwin F. Beckenbach, Richard Bellman: Inequalities. 1983, pp. 120-121.
11. ↑ Roberts / Varberg, op.cit., P. 130.
12. ↑ Ivar Ekeland, Roger Temam: Convex analysis and variational problems. 1976, pp. 166-167.
13. ^ Ky Fan: A minimax inequality and applications. In: Oved Shisha: Inequalities - III. 1972, pp. 103-113
14. ↑ Jean-Pierre Aubin, Ivar Ekeland: Applied Nonlinear Analysis 1984, p. 325 ff., P. 330
15. ↑ Aubin, op. Cit., P. 140, pp. 125–141, p. 145 ff.
16. ↑ Compared to the representation by Aubin and Aubin / Ekeland, the roles of the two components are reversed here.
17. ^ Philippe G. Ciarlet: Linear and Nonlinear Functional Analysis with Applications. 2013, pp. 572-573
18. ↑ Aubin, op.cit., P. 125
19. ↑ Aubin, op.cit., P. 141