Complexity of Optimization Problems

The complexity theory of numerical optimization problems deals with the question of determining the computational cost for solving an optimization problem as a function of its input size. Different complexity models can be formulated, depending on the type of conceptual computer one assumes available (what type of numbers can it operate on, and what are the operations?) and on whether one is interested in the worst-case or average-case behaviour (in the latter case, an appropriate family of distributions has to be chosen for the random input data). Our research focuses on two aspects of this theory: Investigation of the most general class of convex optimization problems that are tractable, and investigation of the most general family of input distributions for which an average-case or smoothed analysis is possible.