Date/Time:02 Oct 2019 16:00Venue: S17 #05-11 SR5Speaker: SHAO Sihong, Peking UniversityLovász extension and graph cutA 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. 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$.Add to calendar:
