Generalized ellipsoids

Abstract

We introduce a family of symmetric convex bodies called generalized ellipsoids of degree d (GE-ds), with ellipsoids corresponding to the case of d = 0. Generalized ellipsoids (GEs) retain many geometric, algebraic, and algorithmic properties of ellipsoids. We show that the conditions that the parameters of a GE must satisfy can be checked in strongly polynomial time and that one can search for GEs of a given degree by solving a semidefinite program whose size grows only linearly with dimension. We give an example of a GE that does not have a second-order cone representation, but we show that every GE has a semidefinite representation whose size depends linearly on both its dimension and its degree. In terms of expressiveness, we prove that for any integer m >= 2, every symmetric full-dimensional polytope with 2m facets and every intersection of m cocentered ellipsoids can be represented exactly as a GE-d with d <= 2m - 3. Using this result, we show that every symmetric convex body can be approximated arbitrarily well by a GE-d, and we quantify the quality of the approximation as a function of the degree d. Finally, we present applications of GEs to several areas, such as time-varying portfolio optimization, stability analysis of switched linear systems, robust-to-dynamics optimization, and robust polynomial regression.