Kakutani fixed point theorem

基本概念

拓扑学是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的学科。它只考虑物体间的位置关系而不考虑它们的形状和大小。在拓扑学里,重要的拓扑性质包括连通性与紧致性 ——百度百科

拓扑学也被称为橡皮泥几何学 ,拓扑学不是很在意空间的距离或物体的长度,而是更重视空间的形态,比如在拓扑学家眼中,骰子和台球可以归类到一种物体,但是他们两个和面包圈却不是同一种物体,我们通过拉伸,挤压等“温和操作”,可以把骰子“捏”成台球,所以拓扑学认为他俩是一种东西,但是面包圈有一个洞,只有通过撕裂,钻孔,粘合等“暴力操作”,才能把没洞的台球变成有洞的面包圈,所以拓扑学认为他俩是两种东西。

因此只要是一个“胚子”捏出来的形状,在拓扑学中就是同一种东西,这种概念叫做 同胚,也可以叫做 拓扑等价

两个物体是否同胚,要看在拓扑变换后,点、线、体的数目和原来是不是一样。一般来说,对于任意形状的闭曲面,只要不把曲面撕裂或割破,它的变换就可以算作是拓扑变换,变换后的各种形态都是拓扑等价的。

不动点算法

所谓不动点,是指将一个给定的区域A,经某种变换ƒ(x),映射到A时,使得x=ƒ(x)成立的那种点。最早出现的不动点理论是布劳威尔定理(1912):设A为Rn中的一紧致凸集, ƒ为将A映射到A的一连续函数,则在A中至少存在一点x,使得x=ƒ(x)。其后,角谷静夫于1941年将此定理推广到点到集映射上去。设对每一x∈A ,ƒ(x)为A的一子集。若ƒ(x)具有性质:对A上的任一收敛序列xi→x0,若yi∈ƒ(xi)且yi→y0,则有y0∈ƒ(x0),如此的ƒ(x)称为在A上半连续,角谷静夫定理:设A为Rn中的一紧致凸集,对于任何x∈A,若ƒ(x)为A的一非空凸集,且ƒ(x)在A上为上半连续,则必存在x∈A,使x∈ƒ(x)。J.P.绍德尔和J.勒雷又将布劳威尔定理推广到巴拿赫空间。

不动点定理在代数方程、微分方程、积分方程、数理经济学等学科中皆有广泛的应用。例如,关于代数方程的基本定理,要证明ƒ(x)=0必有一根,只须证明在适当大的圆│x│≤R 内函数ƒ(x)+x有一不动点即可;在运筹学中,不动点定理的用途至少有二:一为对策论中用来证明非合作对策的平衡点的存在和求出平衡点;一为数学规划中用来寻求数学规划的最优解。对于一个给定的凸规划问题:min{ƒ(x)│gi(x)≤0,i=1,2,…,m},在此,ƒ和g1,g2,…,gm皆为Rn中的凸函数。通过适当定义一个函数φ,可以证明:若上述问题的可行区域非空,则φ的不动点即为该问题的解。

H.斯卡夫的证明是基于一种所谓本原集,后来的各种发展皆基于某种意义下的三角剖分。对每一i, 将区间0≤xi≤1依次分为m1,m2…等分,m1<m2<…,mi→,是给定的一列正整数。对于固定的i,过分点依次作平行于xi=0的平面。 这些平面将Sn分成若干同样大小的n维三角形。它们的全体作成的集 Gi,称为Sn的一三角剖分。设ƒ(x)为 Sn→Sn的一连续函数,x=(x1,x2,…,xn+1),ƒ(x)=(ƒ1(x),ƒ2(x),…,ƒn+1(x))。定义。由于ƒ(x)和x皆在Sn上,若有则显然有ƒ(x)=x,即x为ƒ(x)的一不动点。

对每一点y∈Sn赋与标号l(y)=k=min{j│y∈Cj,且yj>0}。由著名的施佩纳引理,在Gi中必存在一三角形σi,它的n+1个顶点yi(k)的标号分别为k(k=1,2,…,n+1)于是可得一列正数ij(j→),使得(k)→yk,k=1,2,…,n+1。根据σi的作法,当ij→时,收敛成一个点x。故yk=x,k=1,2,…,n+1。因 (k)的标号为k,故yk∈Ck,因而即x为所求的不动点。因此,求ƒ(x):Sn→Sn 的不动点问题就化为求 σi(i=1,2,…) 的问题。为了计算上的效果,除了上述的标号法之外,还有标准整数标号法、向量标号法等等。关于如何求σi,有变维算法、三明治法、同伦算法、变维重始法等等,通过适当定义,可将上之Sn改为Rn或Rn中之一凸集。求一凸函数在一凸集上的极值问题也可化为求不动点问题。一般说来,这条途径适用于维数不高但问题中出现的函数较为复杂的情况。

Fixed point theory and its applications -Prof. Yuguang Xu (徐裕光 教授)

不动点理论研究的内容属于数学的非线性泛函分析和一般拓扑学范畴。研究出的结果被广泛应用于分析数学,力学,微分方程,控制理论,最优化理论,非线性规划,数理经济学和博弈论等应用性学科。

(一).不动点理论的发展进程

• 一个简单的不动点问题(微积分中);

• 1909 年, Brouwer 的著名的 不动点定理 及一系列的论文创立了不动点理论;

• 1922 年 , 波兰著名数学家 S. Banach 给出了一个既简单又实用的 压缩映射原理, 它也是一个不动点定理。在简单的条件下, Banach 压缩映射原理不仅指出了映射不动点的存在性和唯一性,还提供了一种逼近不动点的方法;

• 1967 年,美国数学家 H. E. Scarf 找到了计算单纯形连续映射不动点的组合拓扑有限算法,这也就是 Brouwer 不动点定理的构造性证明;

• 1941 年,日本数学家角谷静夫( Kakutani )的集值不动点定理为博弈论建立在数学基础上作了理论准备;

• 1968 年的 Fan - Browder 不动点定理, 1972 年的 Himmelberg 不动点定理以及 Tarafdar 在 1987 年和 1992 年分别在拓扑线性空间和 H -空间建立的不动点定理;

• 美国数学家 Michael ( 1956 年), Deutsch 和 Kenderov ( 1983 年),应用集值分析中的连续选择原理在拓扑空间建立集值不动点定理和几乎不动点定理;

• 1990 年以后,关于不动点理论的研究达到一个高潮,在各种映射或空间条件下,讨论不动点,随机不动点,几乎不动点等,每年有上百篇论文发表,新的不动点定理和各种迭代逼近方法不断涌现。

(二).不动点理论的四个研究方向

  1. 在拓扑空间研究“不动点性质”(使用同伦群),不动点的有限算法(组合拓扑);

• 丹麦数学家 Nielsen 研究不动点的个数( Nielsen 数),开创不动点类理论的研究,大陆数学家的工作;

• 一般度量空间或拓扑向量空间的连续映射的不动点问题

不动点的存在性问题研究 映射的连续性,紧性,空间的紧性,凸性,单值或集值
不动点的迭代逼近问题研究 多种迭代方法,收敛性(强,弱),收敛速度,误差分析,稳定性

• 应用集值分析中的连续选择原理在拓扑空间建立集值不动点定理和几乎不动点定理并应用于博弈论研究。

(三). 不动点理论主流方向的研究现状,及研究前沿期待解决的问题

“ 一般度量空间或拓扑向量空间映射的不动点问题”是研究的主流。近 20 年来的研究发展主线:

• 迭代逼近算法的研究(从 Mann 迭代到杂交迭代等);

• 强伪压缩映射的不动点,强增生算子方程的迭代解(两者的联系);

• 迭代误差分析和稳定性研究;

• 有待解决的几个问题(一般情况下的收敛性问题, 迭代收敛的等价性问题,不动点存在性和迭代逼近的条件的协调性问题,关于 Schauder 猜想)。

其次为“应用连续选择原理建立集值不动点定理和几乎不动点定理”的研究。

现有的最好结果和需要解决的问题:

a ) 上(下)半连续集值映射与其不动点存在性的拓扑同伦关系;

b) 具备弱于上(下)半连续性的集值映射与其不动点的存在唯一性的充要条件;

c) 探索几乎均衡解与几乎不动点存在性的关系。

维基百科中关于 Kakutani fixed point theorem

Mathematician John Nash used the Kakutani fixed point theorem to prove a major result in game theory. Stated informally, the theorem implies the existence of a Nash equilibrium in every finite game with mixed strategies for any number of players. This work would later earn him a Nobel Prize in Economics.

In this case, S is the set of tuples of mixed strategies chosen by each player in a game. The function φ(x) gives a new tuple where each player’s strategy is her best response to other players’ strategies in x. Since there may be a number of responses which are equally good, φ is set-valued rather than single-valued. Then the Nash equilibrium of the game is defined as a fixed point of φ, i.e. a tuple of strategies where each player’s strategy is a best response to the strategies of the other players. Kakutani’s theorem ensures that this fixed point exists.