Optimization Online


Finding Minimum Volume Circumscribing Ellipsoids Using Copositive Programming

Areesh Mittal (areeshmittal***at***utexas.edu)
Grani Hanasusanto (grani.hanasusanto***at***utexas.edu)

Abstract: We study the problem of finding 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 when the set is defined by affine and quadratic inequalities. We prove that our proposed method always provides an ellipsoid of lower volume than the well-known S-procedure. We empirically demonstrate that our method generates high-quality solutions faster than solving the problem to optimality.

Keywords: minimum volume ellipsoid problem; copositive programming; semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 07/17/2018
Entry Accepted: 07/17/2018
Entry Last Modified: 08/13/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society