Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming
Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming
复制标题
DOI：
10.1287/opre.2021.2156
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Areesh Mittal;G. A. Hanasusanto
中科院分区：
文献类型：
--
作者：
Areesh Mittal;G. A. Hanasusanto
我们研究寻找洛纳 - 约翰椭球（即包含给定凸集且体积最小的椭球）的问题。我们将该问题重新表述为一个广义余正规划，并利用这种重新表述，针对由仿射和二次不等式定义的集合实例，推导出易于处理的半定规划近似。我们证明，当基础集合是一个多面体时，我们的方法所得到的椭球体积绝不会比通过缩放最大内切体积椭球所得到的体积更大。我们通过实验证明，我们所提出的方法能产生高质量的解，并且比求解该问题至最优解的速度要快得多。此外，我们在求解时间和质量方面都优于现有的近似方案。我们给出了我们的方法在以下方面的应用：为具有随机补偿的动态分布鲁棒问题获取分段线性决策规则近似，以及当允许控制集是一个多面体时，为线性动态系统中的可达状态集生成椭球近似。
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.