Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming

Areesh Mittal () and Grani A. Hanasusanto ()
Additional contact information
Areesh Mittal: Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, Austin, Texas 78712
Grani A. Hanasusanto: Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, Austin, Texas 78712

Operations Research, 2022, vol. 70, issue 5, 2867-2882

Abstract: We study the problem of finding the Löwner–John ellipsoid (i.e., an ellipsoid with minimum volume that contains a given convex set). We reformulate the problem as a generalized copositive program and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, when the underlying set is a polytope, our method never provides an ellipsoid of higher volume than the one obtained by scaling the maximum volume-inscribed ellipsoid. We empirically demonstrate that our proposed method generates high-quality solutions and can be solved much faster than solving the problem to optimality. Furthermore, we outperform the existing approximation schemes in terms of solution time and quality. We present applications of our method to obtain piecewise linear decision rule approximations for dynamic distributionally robust problems with random recourse and to generate ellipsoidal approximations for the set of reachable states in a linear dynamical system when the set of allowed controls is a polytope.

Keywords: Optimization; minimum volume ellipsoids; copositive programming; semidefinite programming; distributionally robust optimization (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2156 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:5:p:2867-2882

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().