2018/07/19 by Areesh Mittal, Grani A. Hanasusanto, Mittal, Areesh +1
Decision Sciences · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Mathematical Programming #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1807.07507
openalex publication_date 2018/07/19 · openalex created_date 2022/11/30 · openalex updated_date 2026/07/28
We study the problem of finding the Lowner-John ellipsoid, i.e., an ellipsoid\nwith minimum volume that contains a given convex set. We reformulate the\nproblem as a generalized copositive program, and use that reformulation to\nderive tractable semidefinite programming approximations for instances where\nthe set is defined by affine and quadratic inequalities. We prove that, when\nthe underlying set is a polytope, our method never provides an ellipsoid of\nhigher volume than the one obtained by scaling the maximum volume inscribed\nellipsoid. We empirically demonstrate that our proposed method generates\nhigh-quality solutions faster than solving the problem to optimality.\nFurthermore, we outperform the existing approximation schemes in terms of\nsolution time and quality. We present applications of our method to obtain\npiecewise-linear decision rule approximations for dynamic distributionally\nrobust problems with random recourse, and to generate ellipsoidal\napproximations for the set of reachable states in a linear dynamical system\nwhen the set of allowed controls is a polytope.\n