Optimization and complexity

Measures of problem difficulty appear throughout computational mathematics. Convex optimization has its own complexity theory. A particularly nice feature of the subject is that along with the known "hardness bounds", one can in a variety of contexts present algorithms with matching efficiency estimates. In this sense, such algorithms are optimal for the problem class. I will discuss various aspects of this subject, motivated by large-scale data science applications.