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

时  间:2019年2月22日  上午10:30--11:30

地  点:理科楼 LA106

摘  要:A firm bridge between discrete data world and continuous math field should be tremendously helpful in data analysis. Along this direction, the Lovasz 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 Lovasz 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 Lovasz extension,  but also works for the Cheeger cut and maxcut problems. In particular, the set-pair Lovasz extension enlarges the feasible region of resulting equivalent continuous optimization problems from a half space (resulted from the Lovasz 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. Preliminary results on G-set demonstrate that the ratio between the best cut values achieved by the simple algorithm without any local breakout techniques and the best known ones is of at least  $0.986$. In fact, equipped with some intuitive local breakout techniques, our simple maxcut algorithm may achieve the best cut values. Finally, we conduct a general discussion on graph k-cut problems.

报告人简介: 邵嗣烘，北京大学数学科学学院副教授。先后主持国家自然基金青年基金、面上项目和优秀青年基金。主要研究领域：计算量子力学、微分方程数值解和图谱理论及应用等。

学院联系人:曾 芳

欢迎广大师生积极参与！