从平方和到模之和: 理论与算法

主讲人：邵嗣烘 北京大学博雅特聘教授

时间：2025年10月18日8：30

地点：徐汇校区三号楼332室

举办单位：数理学院

主讲人介绍：邵嗣烘，北京大学博雅特聘教授，主讲《高维数值方法》，《理论计算机科学与离散数学选讲》，《组合最优化算法》，《谱方法》，《数学分析I-III》，《数学模型》和《计算流体力学》等课程。主要开展面向智能、量子和计算的交叉融合研究，落脚点在基础的数学理论和高效的算法设计，强调离散数学结构的设计、分析和应用。具体研究领域包括：高维数值方法、离散建模与组合优化、计算量子力学、图谱理论及算法、微分方程数值解和计算复杂性等。2019年入选北京智源人工智能研究院“智源青年科学家”。2020年获北京大学优秀博士学位论文指导老师。2025年获北京大学优秀本科毕业论文指导教师和北京大学兴证全球基金奖教金杰出青年学者奖。曾获中国计算数学学会优秀青年论文一等奖，北京大学黄廷芳/信和青年杰出学者奖，北京大学学术类创新奖，宝洁教师奖和北京大学优秀班主任等荣誉。

内容介绍：现代社会建立于数据之上，数据驱动着世界的发展。数据是离散的，连接这些离散数据的数学模型往往天然具有NP难的特征，例如复杂的组合优化问题，这迫使我们越来越重视离散数学工具的发展。另一方面，相较于离散的研究对象，连续的数学模型往往会呈现更多的结构信息，如凸性、对称性等，进而为产生更丰富的处理手段提高可能。于是一个合理的想法是将离散的基于数据的组合优化问题“嵌入”到连续问题来进行理论和算法的发展。沿着这条思路，传统的连续嵌入尝试往往遵循松弛-凑整的研究路径去讨论收敛性和估计近似比，但这样的分析极不平凡，多需要配合精心设计的凑整策略。即便如此，松弛和凑整这两个模块互相独立导致这种嵌入方式下重构的可行解依旧不够准确。为此，本报告将从多种NP难的图割问题出发来说说如何尝试构建一套离散到连续的准确嵌入方式，进而发展等价的非线性图谱理论和简单连续迭代算法，并通过启发式算法的高质量参考解来进行验证。