Generalized Ellipsoids

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\ge 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\le 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.

Funding: A. A. Ahmadi was partially supported by the Air Force Office of Scientific Research [Grant MURI], the Sloan Fellowship, and Princeton [AI Lab Seed Grant and SEAS Innovation Grant]. A. Chaudhry was partially supported by the Air Force Office of Scientific Research [Grant MURI].