Lovasz extension and graph cut
计算数学报告
报告题目(Title)：Lovasz extension and graph cut
报告人(Speaker)：邵嗣烘 （北京大学）
地点(Place)：教八207
时间(Time)：2019年4月24日 下午1:30-3:30
邀请人(Inviter)：陈华杰
报告摘要
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. 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.
主讲人简介
邵嗣烘，男，1982年10月生，江西都昌人，中共党员，2010年 5月起入职北京大学数学科学学院，现任副教授。先后于 2003 年7月和 2009 年1月毕业于北京大学数学科学院并分别获得理学学士和博士学位。 2007 年 8 月至 2008 年 7 月被公派到美国北卡罗莱那大学夏洛特分校数学统计系访问学习。2009 年 2 月至 2010 年 8 月在香港科技大学的 The Joint KAUST-HKUST Micro/Nanofluidics Laboratory 工作。作为访问学者，先后到访过美国普林斯顿大学、西班牙塞维利亚大学和香港中文大学等。主要在计算量子力学，脑科学，图谱理论和微分方程数值解等领域开展可计算建模、数学分析和算法设计等研究工作，得到国家自然科学基金连续资助：青年科学基金项目（2011），面上项目（2014）和优秀青年科学基金项目（2018）。曾获中国计算数学学会优秀青年论文一等奖（2005），北京大学学术类创新奖（2005，2006，2008），北京大学优秀博士学位论文三等奖（2011），宝洁教师奖（2015）和北京大学优秀班主任（2013，2017）等。
