Generalized Ellipsoids
\(\)
We introduce a family of symmetric convex bodies called generalized ellipsoids of degree \(d\) (GE-\(d\)s), 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 which does not have a second-order cone representation, but show that every GE has a semidefinite representation whose size depends linearly on both its dimension and degree. In terms of expressiveness, we prove that for any integer \(m\geq 2\), every symmetric full-dimensional polytope with \(2m\) facets and every intersection of \(m\) co-centered ellipsoids can be represented exactly as a GE-\(d\) with \(d \leq 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.