Generalized Ellipsoids

• 成果类型: Article; Early Access
• 署名作者: Ahmadi, Amir Ali; Chaudhry, Abraar; Dibek, Cemil
• 署名单位: Princeton University; University System of Georgia; Georgia Institute of Technology; Koc University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0643
• 发表日期: 2026-01-30
• 关键词: Ellipsoids; convex bodies; conic optimization; semidefinite representations; polynomial matrices; semidefinite; squares; SUM; convexity; matrices

摘要

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.