Optimization Online


Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection

Jianzhe Zhen (J.Zhen***at***tilburguniversity.edu)
Dick den Hertog (d.denhertog***at***tilburguniversity.edu)

Abstract: We introduce a novel scheme based on a blending of Fourier-Motzkin elimination (FME) and adjustable robust optimization techniques to compute the maximum volume inscribed ellipsoid (MVE) in a polytopic projection. It is well-known that deriving an explicit description of a projected polytope is NP-hard. Our approach does not require an explicit description of the projection, and can easily be generalized to find a maximally sized convex body of a polytopic projection. Our obtained MVE is an inner approximation of the projected polytope, and its center is a centralized relative interior point of the projection. Since FME may produce many redundant constraints, we apply an LP-based procedure to keep the description of the projected polytopes at its minimal size. Furthermore, we propose an upper bounding scheme to evaluate the quality of the inner approximations. We test our approach on a simple polytope and a color tube design problem, and observe that as more auxiliary variables are eliminated, our inner approximations and upper bounds converge to optimal solutions.

Keywords: Fourier-Motzkin elimination; maximum volume inscribed ellipsoid; polytopic projection; chebyshev center; removing redundant constraints; adjustable robust optimization

Category 1: Robust Optimization

Citation: INFORMS Journal on Computing, 31(1):31-42.


Entry Submitted: 01/23/2015
Entry Accepted: 01/23/2015
Entry Last Modified: 11/16/2017

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