Optimization beyond convexity, with a bit of geometry

Seminar in Mathematics

Abstract:
Pretty much any computational task can be framed as an optimization problem. But of course, with great generality comes great complexity. Accordingly, it is fruitful to focus on problem classes which enjoy some structure. A particularly nice structure is convexity: this is well understood by now. Absent convexity, optimization problems can be arbitrarily hard. Yet, as it happens, some non-convex problems can be solved numerically in reasonable time. How do we recognize them? How do we exploit their structure? And if a problem of interest fails to have such good properties, what can we do about it? I will present some results and directions my group and I are exploring.