报告人：邵嗣烘（北京大学）

时间：2024年06月17日 16：00-

地址：理科楼LA106

摘要：A firm bridge between discrete data world and continuous math field should be tremendously helpful in data analysis. Along this direction, the Lovász extension provides a both explicit and equivalent continuous optimization problem for a discrete optimization problem, for instance, the Cheeger cut problem. In this talk, we report a set-pair Lovász extension which provides not only an answer to the dual Cheeger cut, anti-Cheeger cut, and max 3-cut problems, all of which cannot be handled by the Lovász extension, but also works for the Cheeger cut and maxcut problems. In particular, the set-pair Lovász extension enlarges the feasible region of resulting equivalent continuous optimization problems from a half space (resulted from the Lovász extension) to the entire space for the Cheeger cut and maxcut problems. On the other hand, it provides new possibilities for designing continuous optimization algorithms for combination problems on the practical side, too. As an illustration, we propose a simple continuous iterative algorithm for the maxcut problem which converges to a local optimum in finite steps. Here ‘simple’ means the inner subproblem is solved analytically and thus no optimization solver is called. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by the simple iterative algorithm and the best known ones are at least 0.986 and can be further improved to at least 0.997 by a preliminary attempt to break out of local optima.

简介：邵嗣烘，北京大学博雅特聘教授，毕业于北京大学数学科学学院并获得理学学士和博士学位，先后到访过北卡罗莱那大学夏洛特分校，香港科技大学，普林斯顿大学、塞维利亚大学和香港中文大学等。主讲《数学分析I-III》，《数学模型》，《高维数值方法》，《组合最优化算法》，《谱方法》和《计算流体力学》等课程。主要开展面向智能、量子和计算的交叉融合研究，落脚点在基础的数学理论和高效的算法设计，强调离散数学结构的设计、分析和应用。具体研究领域包括：高维数值方法、离散建模与组合优化、计算量子力学、图谱理论及算法、微分方程数值解和计算复杂性等，获国家自然科学基金杰青、优青、面上和青年等项目资助。2019年入选北京智源人工智能研究院“智源青年科学家”。2020年获北京大学优秀博士学位论文指导老师。2021年获北京大学黄廷芳/信和青年杰出学者奖。曾获中国计算数学学会优秀青年论文一等奖，北京大学学术类创新奖，北京大学优秀博士学位论文三等奖，宝洁教师奖和北京大学优秀班主任等。

邀请人：温罗生

欢迎广大师生积极参与！