Seminar - Yinyu Ye

Complexity Analysis beyond Convex Optimization

Abstract:

A powerful approach to solving difficult optimization problems is convex relaxation. In a typical application, the problem is first formulated as a cardinality-constrained linear program (LP) or rank–constrained semidefinite program (SDP), where the cardinality or rank corresponds to the target support size or dimension. Then, the non–convex cardinality or rank constraint is either dropped or replaced by a convex surrogate, thus resulting in a convex optimization problem. In this talk, we explore the use of a non–convex surrogate of the cardinality or rank function, namely the so–called Schatten quasi–norm. Although the resulting optimization problem is non–convex, we show, for many cases, that a first and second order critical point can be approximated to arbitrary accuracy in polynomial time. We also generalize and summarize our complexity analysis results to more general non-convex optimization, which recently becomes a popular research topic and has wide applications.