Complexity Analysis beyond Convex Optimization
|Room:||Mathematics and Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1