单纯不动点算法

出处：按学科分类—自然科学总论 北京出版社《现代科技综述大辞典上》第123页（3710字）

自20世纪初布劳维尔(Brouwer)不动点定理出现以来，各种不动点定理成为应用数学领域许多问题解的存在性讨论的有力工具。

不动点定理的条件一般都比较弱，而结论却很强，从而得到赞赏。许多应用问题都可以方便地表述为等价的不动点问题，更使不动点定理在应用领域大受欢迎。然而，从计算的角度看，除了收缩映射的不动点定理以外，各种不动点定理的用处还是很有限的，因为它们并不告诉怎样把肯定存在的不动点找出来，不动点的数值求解还是要借助某些迭代过程，但这些迭代方法通常要对问题提出比较苛刻的条件才能保证计算收敛。

这种情况在60年代末期发生了根本的变化。

1967年美国斯卡夫(H．E．Scarf)发表论文，提出计算单形上连续自映射的不动点的一种在有限步内必定成功的算法，开创了不动点有效算法发展的新篇章。

1928年，德国斯派奈(E．Sperner)曾经证明过一个通称斯派奈引理的定理。

欧氏空间中p+1个仿射无关的点的凸包，称作是一个p维单形(simplex)。在二维的情形，因为二维的单形就是三角形，该定理可以叙述如下：如果把一个大三角形按照单纯剖分(simplicial triangulation)的要求规则地分成规则相处的许多小三角形，然后往小三角形的每个顶点上随便丢下0、1、2三个号码中的一个，那么只要大三角形的底边上没有2，左侧边上没有1，右侧边上没有0，就一定有一个小三角形，它的三个顶点分别带有0、1、2全部三种标号，称为全标三角形。

设S=｛(x，y，z)∈R³：x，y，z≥1；x+y+z=1｝是所说的大三角形(二维单形)，

E：S→S，f(x，y，z)=(f_x(x，y，z)，f_y(x，y，z)，f_z(x，y，z))是S的连续自映射，那么符合F(x，y，z)=(x，y，z)即符合f_x(x，y，z)=x，f_y(x，y，z)=y，f_x(x，y，z)=z的一点(x，y，z)∈S，因为在映射f之下保持不动，就叫做f的一个不动点(fixed point)。

在数理经济学经济均衡理论中，p维单形上的讨论相应于p+1种商品的纯交换经济模型的讨论。现在p=2，表示有p+1=3种商品，x，y，z分别是这3种商品的价格，而f表示该纯交换经济中供不应求的商品价格上升、供大于求的商品价格下降的价格调节机制。所以，不动点就相应于供不应求则商品价格上升、供大于求则价格下降的市场调节之下保持不动的一组价格，它们正好使得市场供求关系取得平衡，所以称为均衡价格(equilibrium prices)，有关的讨论也就属于经济均衡理论(economic equi-librium theory)。

现在按照下述的规则确定小三角形顶点的标号，就容易证明只要小三角形足够小，全标小三角形的任一顶点都可以作为f的数值不动点。标号规则是：若顶点(x，y，z)符合

f_x(x，y，z)≤x＞0，f_y(x，y，z)≥y，就赋予标号0；否则，若符合

f_y(x，y，z)≤y＞0，f_z(x，y，z)≥z，就赋予标号1；

在所有其余情况，都赋予标号2。

斯卡夫已经引进了上述标号法，它所导出的顶点标号，完全符合斯派奈引理的条件，于是应用斯派奈引理，就知道一定存在数值不动点。斯卡夫的贡献，在于发明了一种可行的算法去确定数值不动点的位置。

后来，经过库恩(H．W．Kuhn)的改进，这种算法可以简述如下。

大三角形已经单纯剖分成规则相处的许多小三角形，这些小三角形的边都称为单纯剖分的棱。

因为大三角形的底边上没有2，所以底边上的顶点的标号只有0和1两种。又因为左侧边上没有1，右侧边上没有0，所以底边左端顶点的标号一定是0，右端顶点的标号一定是1，从而在底边上一定有一条棱，其左端标号为0，右端标号为1。

从这个棱出发，按照遇到一端标号为0二端标号为1的棱就穿过去的规则向大三角形里面走，并且保持在穿越时标号0的顶点在左、标号1的顶点在右，那么一定可以在有限步内到达作为数值不动点的全标小三角形。这一描述具有鲜明的组合特征。事实上，略早于斯卡夫的论文，樊畿的《从一个定向n维伪流形到八角剖分的m维球的单纯映射》的论文，就已经在更广泛的意义上奠定了上述算法的组合框架。也许因为论文本身没有显现数理经济学的背景，所以除了斯派奈生前的被推崇以外，这篇重要论文似乎长期未能受到足够重视。

主要因为把大单形单纯剖分为许多规则相处的小单形是上述计算的基础，所以这类算法通称单纯不动点算法(simplicial fixed point algorithms)。

上面二维演示的算法有一个缺点，即每一轮计算必须从大单形的边沿开始，从而如果一轮计算的结果的精度达不到要求而必须在更精细的单纯剖分的基础上开始新一轮的计算时，先前计算所获得的信息不能发挥作用。为克服这一缺点，伊夫斯(B．C．Eaves)和莫里尔(O．H．Merrill)在1972年分别将同伦引入算法，把计算S的自映射的不动点的问题放在高一维的空间［0，1］×S中去考虑，从人为辅助映射的已知不动点出发，随着同伦参数t从1走向0，过渡到目标映射的不动点。莫里尔方法从1直接走到0，程序实施方便，但每一轮计算的精度改进有限，所以要重复执行多次。伊夫斯方法则从1经过1／2、1／4、1／8、1／16、…趋向0，使用随着同伦参数变小而越分越细的渐细单纯剖分，计算在达到精度要求时中止，但是剖分的程序实施比较复杂。

范德兰(G．van der Laan)和台尔曼(A．J．J．Talman)在1979年提出不须使用辅助维，但是可以从大单形的单纯剖分的内部任一顶点开始的算法，较好地解决了每一轮计算充分利用先前计算所获得的信息的问题。

经济学讨论中常常有这样的情况：面对一定的环境，存在一组最优的决策。这就导致集值映射(set-valued mapping)的概念。

说F是S的一个集值自映射，指的是对每个x∈S，F(x)是S的一个子集而不是一个点。

集值映射的不动点的特征是x∈F(x)，称为角谷(Kakutani)不动点，而原来单值映射的以x=f(x)为标志的不动点，称为布劳维尔不动点。前述赋每个顶点以一个整数的标号法称为整数标号法，而计算集值映射的角谷不动点，原则上必须采用向量标号法，例如赋每个顶点x∈S以向量y－x，其中y∈F(x)。

由于单纯剖分在单纯不动点算法中的重要性，围绕单纯剖分的效率，有过许多重要的工作。

新近出现的D剖分，按各种效率度量，都优于先前的剖分法。关于向量标号算法道路的二维翼状结构的讨论，从几何上论证了算法的无例外可行性。

除了多项式方程组数值解的讨论以外，当前的研究更多地集中在计算复杂性讨论和数理经济学应用的开拓上。

。【参考文献】：

1 Ky Fan. JComb Theory, 1967,2：588～602

2 Scarf HE. SIAM J Appl Math,1967,15:1328～1341

3 Todd,M J. Springer Lecture Notes in Econ,and Math Sys-tems,1976,124

4 van der Laan G, Talman A J J. Math Prog, 1979,17:74～ 84

5 Eaves BC, Yorke J A. Math,Op Res,1984,9:363～375

6 王则柯．单纯不动点算法基础．广州：中山大学出版社，1986

7 王则柯．数学年刊(A辑)，1990，11：399～406

8 Dang C．Math Op Res，1991，16：148～161

(中山大学王则柯教授撰)