不动点理论作为分析学和拓扑学的重要分支, 已经在工程、经济等领域的实际问题中发挥了重要作用, Krasnosel'skiĭ-Mann (KM) 不动点迭代为逼近非扩张算子的不动点提供了简单有效的计算方法. 本文简述了 KM 定理及其与凸优化问题的联系, 阐释了 KM 定理的数学原理及其在实际问题中的应用示例. 并详细介绍了定理的两位创立者 Mark Aleksandrovich Krasnosel'skiĭ 和 William Robert Mann 的个人背景和他们显著的学术成就.

引言

不动点理论是数学分析和拓扑学的一个重要领域. 不动点的数学定义为: 对于一个算子 , 若  满足 , 则称  为算子  的不动点. 关于不动点理论的研究主要分为两个分支: 一是不动点的存在性, 在这方面数学家们发展出了一系列著名的不动点定理, 如 Brouwer 不动点定理、Banach 不动点定理、Schauder 不动点定理、Kakutani 不动点定理等等, 这些不动点定理在拓扑学、微分方程、经济学等领域得到了广泛应用; 二是不动点的逼近计算. 最早的关于不动点的逼近计算是 Picard 迭代:

相比于 Picard 迭代, KM 迭代可以保证当算子  非扩张时迭代点列的收敛性, 这就是著名的 KM 定理. 到了近代, 数学家们发现了凸优化问题与算子不动点问题之间的有趣联系, 也发现了 KM 定理能为许多著名优化算法的构造和分析提供简洁坚实的理论基础.

KM 定理及意义

KM 定理是不动点理论的重要组成部分, 本节首先介绍该定理的主要内容, 再介绍由该定理衍生出的优化算法.

KM 定理

首先我们介绍非扩张算子. 对于实 Hilbert 空间  中的算子 , 若对于任意的 , 有

一个自然的想法是, 如果点  是  的不动点, 那么有 . 所以是否可以选一个初始点 , 再通过递归  生成一系列的点  去近似  的不动点? 这种递归的方式就是著名的 Picard 迭代, 然而, 这个迭代仅对压缩算子有效, 但它仍然解决了许多重要问题, 是现代数值分析教材的标准内容. 后来数学家 Mark A. Krasnosel'skiĭ和 W. Robert Mann 提出了著名的 KM 迭代:

令  是 Hilbert 空间  上的非扩张算子,  是非空闭凸集.  则由 (1) 定义的序列 , 在  且  的情况下, 满足: 

(i)  ;
(ii) 序列  弱收敛于算子  的某个不动点.

对于一个非扩张算子 ,  单步的 KM 迭代就是算子  的 Picard 迭代, 其中  是恒等算子, 具有这种形式的算子后来也被称为 -平均算子. 特别地, 当  时, 其被称为稳定非扩张算子.

接下来, 我们从几何的观点来考察 KM 迭代序列的几何性质. 如图1所示, 若  是算子  的不动点, 那么不同系数的平均算子作用在  上所得到的  会分别落在图 1中所示的各个圆内. 因此, 可以看出 KM 迭代生成的点列  到不动点集合的距离随着迭代的进行会逐渐变小, 这种性质也被称为 Fejér单调性, 这是 KM 定理的关键所在.

图1：非扩张算子、稳定非扩张算子和 -平均算子所得到的  的范围

接下来我们将简要介绍一下凸优化问题与不动点问题之间的联系, 以及 KM 迭代和几个著名优化算法之间的关系.

KM 迭代算法及不动点迭代格式设计

先考虑一块的凸优化问题:

根据凸分析的知识, 适当闭凸函数 的邻近算子 是稳定非扩张的. 所以 是上述问题的最优解等价于 . 也就是说问题 (2) 可以转化为邻近算子 的不动点问题. 又因为邻近算子是稳定非扩张的, 所以我们可以用 KM 迭代来逼近问题 (2) 的最优解：

这就是著名的邻近点算法.

接着, 我们考虑两块的情况:

所以, 利用邻近算子 的定义我们可以得到,

于是, 问题 (3) 可以转化为算子  的不动点问题. 可以证明当 时, 算子 是非扩张的. 因此, 我们还可以用 KM 迭代来逼近问题 (3) 的解:

这就是著名的向前向后分裂算法, 也被称为邻近梯度法或者 ISTA.

如果问题 (3) 中  也是非光滑的, 在一定条件下, 问题 (3) 的一阶最优性条件为

若想把问题 (3) 和某个算子的不动点问题联系起来, 那么我们需要构造一个单值的算子, 而此时  不一定是单值算子, 所以这里类似于向前向后分裂算法的分析不再适用.  但是通过前面的介绍, 我们知道, 能和次微分算子联系起来的单值算子是邻近算子, 因此我们要想办法构造出这两个函数的邻近算子. 从一阶最优性条件出发, 存在  和  使得问题 (3) 满足如下等价性

其中 . 令

注意到

根据邻近算子的定义, 我们有

于是, 通过引进中间变量 , 两块的非光滑凸优化问题可以转化为寻找如下算子  的不动点问题:

可以证明, 对于 , 这个算子总是稳定非扩张的. 所以, 我们依然可以用 KM 迭代求解原来的优化问题:

这就是著名的 Douglas-Rachford 分裂算法.

最后, 如果把这三类方法分别用于求解带线性等式约束的凸优化问题的对偶问题, 我们可以得到著名的增广拉格朗日方法 (ALM)、交替极小化方法 (AMA) 和交替方向乘子法 (ADMM). 可见 KM 定理为许多著名优化算法的收敛性分析提供了全新的视角.

正如前面所说, KM 定理背后的收敛原理是: 迭代点列到解点集的距离单调递减, 也就是著名的 Fejér单调性. 因此 KM 定理的意义不仅仅在于它的直接应用, 它还提供了对算法收敛性分析的一种框架和工具 (Fejér单调). 对于不能被直接视为 KM 迭代的算法, 可以从 KM 定理背后的原理--Fejér 单调中得到启发. 例如, 郭科、韩德仁等人对于 DR 分裂算法在“强凸+弱凸”形式问题上的收敛性证明[2] 中, 虽然无法直接利用 KM 定理, 但是沿着与 KM 定理相似的路径也可以得到点列关于不动点集的 Fejér单调性, 从而证明算法的收敛性.

贡献者生平

Mark Aleksandrovich Krasnosel'skiĭ：非线性分析的先驱与不动点理论的奠基者[1]

Mark Aleksandrovich Krasnosel'skiĭ, 1920年4月27日生于乌克兰的 Starokostiantyniv 镇, 是20世纪著名的数学家之一. 他的父亲 Alexander Jakovlevich 是一位建筑工程师, 母亲 Fanny Moiseevna 是一名小学俄语教师. 哥哥 Iosiph 后来成为冶金工程领域的知名专家. Krasnosel'skiĭ 于1938年高中毕业, 并进入基辅大学物理数学系学习.

图2：Mark Aleksandrovich Krasnosel'skiĭ

第二次世界大战爆发后, 基辅大学被疏散至哈萨克斯坦, 成为联合乌克兰大学. 1942年,Krasnosel'skiĭ 从该校毕业, 并加入苏联红军, 在梁赞炮兵学校教授数学. 战争结束后, 他于1946年退役, 开始了他在乌克兰科学院数学研究所的科研生涯. 1950年, 他完成了高等学位博士论文, 主题是非线性分析中的拓扑方法. 1953年,  他在沃罗涅日大学担任泛函分析方向的主任, 期间他接触到了 N. N. Bogoliubov、A. N. Kolmogorov、M. G. Krein 等著名数学家, 这为他后来的学术成就奠定了坚实的基础.

Krasnosel'skiĭ 的科学兴趣涵盖了现代数学的多个领域. 在非线性分析和算子理论方面, 他早期的工作集中在自共轭算子和非自共轭算子的分数次幂的研究上, 这些成果后来被广泛应用于偏微分方程、流体动力学等领域. 此外, 他与 M. G. Krein 合作发展了正算子理论, 提出了关于光谱间隙的估计, 解决了许多几何问题. 这些工作为现代数学物理中的算子理论奠定了基础.

Krasnosel'skiĭ在不动点迭代领域的贡献尤为重要. 他与 W. Robert Mann 共同开发了 KM 迭代, 为计算不动点提供了简单有效的迭代算法. 随着近代应用数学的发展, 该方法广泛应用于优化、控制理论和其他领域. 此外, Krasnosel'skiĭ 提出的不动点定理为非线性方程解的存在性提供了理论基础. 他的工作不仅在数学理论上具有重要意义, 还在实际应用中发挥了关键作用. 例如, 自动控制系统、振荡问题以及经济学中的市场模型等等.

Krasnosel'skiĭ还培养了众多杰出的学生. 超过30名学生在他的指导下获得了博士学位, 成为各自领域的领军人物. 其中包括诸如 Perov、Zabreĭko、Sobolevskiĭ、Borisovich 和 Sadovskiĭ等著名数学家[5], 他们在不动点理论、非线性分析、拓扑和微分方程等领域取得了突出成就. 他的科研热情和乐观精神激励了无数年轻的数学家, 推动了多个数学分支的进一步发展.

1997年2月13日, 他在莫斯科的办公桌前去世, 结束了他长达半个世纪的科学生涯. 在他的一生中, Krasnosel'skiĭ 撰写了14本专著和300多篇论文, 为现代数学的发展做出了巨大贡献.

William Robert Mann: Mann迭代的提出者

William Robert Mann, 1920年9月21日生南卡罗来纳州安德森县哈尼帕斯镇(Honea Path, Anderson, South Carolina), 逝世于2006年1月20日, 是一位来自北卡罗来纳大学教堂山分校(University of North Carolina at Chapel Hill(UNC))的数学家[4]. 1949年, 他博士毕业于加州大学伯克利分校[6], 他的工作主要在非线性分析和不动点理论方面, 提出了著名的 Mann 迭代方法.

图3：William Robert Mann

Mann 是捷克数学家 Frantisek Wolf 的学生[6], 两人共同研究了许多不动点理论中的问题, 合作探讨了迭代算法在不同背景下的应用, 推动了相关算法的发展. 在数学领域, 他的研究主要集中在迭代算法和不动点理论上. Mann 提出的 Mann 迭代法是一种用于求解不动点问题的迭代算法[3]. 在此基础上, Mann 与 Krasnosel'skiĭ 共同发展了 KM 定理, 成为解决不动点问题的有效工具. 被广泛应用于优化、控制理论等领域. Mann 迭代和 KM 定理在现代优化理论中具有重要地位, 也为处理复杂的数学和工程问题提供了强有力的工具. 此外, 他还与 Angus Ellis Taylor 合著了教科书《Advanced Calculus》的第二和第三版[7], 该书被广泛用作美国大学数学课程的教材. 

除了数学贡献外, 他积极支持北卡罗来纳大学及教堂山地区的种族融合, 参与推动大学接受非裔学生的努力, 并支持无歧视的招生政策. 他代表学校间种族团结组织在北卡罗来纳州议会发言, 积极参与教堂山学校的去隔离计划, 并支持公共住宿法的合宪性, 帮助推动当地企业的种族融合[8].

总结

总的来说, 通过对算子 结构的设计, KM 迭代可以衍生出一系列优化算法, 例如邻近点算法、向前向后分裂算法和 Douglas-Rachford 分裂算法. 同时, KM 定理也为这些优化算法提供了统一的分析框架, 这也显示出 KM 定理在迭代算法设计和理论分析中的重要地位. 而且 KM 定理还启发了数学家们对算法性能的深入理解, 例如如何选择迭代参数以及如何处理不同算子的特性等等.

作者简介

蔡邢菊, 南京师范大学数学科学学院教授, 博士生导师. 主要从事最优化理论与算法、变分不等式、数值优化方面的研究工作. 主持多项国家基金, 获江苏省科技进步奖一等奖一项. 担任中国运筹学会副秘书长、算法软件与应用分会秘书长、数学规划分会常务理事, 江苏省运筹学会理事长.

胡乐宇, 北京航空航天大学数学科学学院博士研究生, 导师为韩德仁教授. 研究兴趣为分裂算法的收敛性分析, 相关文章发表在 IPI 等期刊上.

王茂然, 南京师范大学数学科学学院博士研究生, 导师为蔡邢菊教授. 研究兴趣为单调算子的分裂算法及其应用.

参考文献