Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars
| | Speaker: | 邵嗣烘 副教授，北京大学
| | Inviter: | 于海军 研究员 | Title:
| Lovász extension and graph cut | Time & Venue:
| 2021.11.17 14:00-15:00 腾讯会议ID：468 217 763入会密码：123456 | Abstract:
| 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.
| |
| |
优惠券领取后72小时内有效，10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材，产品类型包含电子书、题库、全套资料以及视频，无论您是考研复习、考证刷题，还是考前冲刺等，不同类型的产品可满足您学习上的不同需求。 ...考试优惠券 本站小编 Free壹佰分学习网 2022-09-19