Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection

J. Zhen, D. den Hertog

Research output: Working paperDiscussion paperOther research output

154 Downloads (Pure)

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.
Original languageEnglish
Place of PublicationTilburg
PublisherCentER, Center for Economic Research
Number of pages28
Volume2015-004
Publication statusPublished - 21 Jan 2015

Publication series

NameCentER Discussion Paper
Volume2015-004

Fingerprint

Color

Keywords

  • Maximum volume inscribed ellipsoid
  • chebyshev center
  • polytopic projection
  • adjustable robust optimization

Cite this

Zhen, J., & den Hertog, D. (2015). Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection. (CentER Discussion Paper; Vol. 2015-004). Tilburg: CentER, Center for Economic Research.
Zhen, J. ; den Hertog, D. / Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection. Tilburg : CentER, Center for Economic Research, 2015. (CentER Discussion Paper).
@techreport{4a51526ec7f0436faeaaf5f3eed56d5a,
title = "Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection",
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 = "Maximum volume inscribed ellipsoid, chebyshev center, polytopic projection, adjustable robust optimization",
author = "J. Zhen and {den Hertog}, D.",
year = "2015",
month = "1",
day = "21",
language = "English",
volume = "2015-004",
series = "CentER Discussion Paper",
publisher = "CentER, Center for Economic Research",
type = "WorkingPaper",
institution = "CentER, Center for Economic Research",

}

Zhen, J & den Hertog, D 2015 'Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection' CentER Discussion Paper, vol. 2015-004, CentER, Center for Economic Research, Tilburg.

Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection. / Zhen, J.; den Hertog, D.

Tilburg : CentER, Center for Economic Research, 2015. (CentER Discussion Paper; Vol. 2015-004).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection

AU - Zhen, J.

AU - den Hertog, D.

PY - 2015/1/21

Y1 - 2015/1/21

N2 - 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.

AB - 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.

KW - Maximum volume inscribed ellipsoid

KW - chebyshev center

KW - polytopic projection

KW - adjustable robust optimization

M3 - Discussion paper

VL - 2015-004

T3 - CentER Discussion Paper

BT - Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Zhen J, den Hertog D. Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection. Tilburg: CentER, Center for Economic Research. 2015 Jan 21. (CentER Discussion Paper).