Computing the maximum volume inscribed ellipsoid of a polytopic projection

Jianzhe Zhen, Dick den Hertog

Research output: Contribution to journalArticleScientificpeer-review

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
Pages (from-to)31-42
JournalINFORMS Journal on Computing
Volume30
Issue number1
Early online dateOct 2017
DOIs
Publication statusPublished - Jan 2018

Fingerprint

Color
Approximation
Optimization techniques
Optimal solution
Robust optimization
Upper bound
Tube
NP-hard

Keywords

  • Fourier-Motzkin elimination
  • maximum volume inscribed ellipsoid
  • polytopic projection
  • Chebyshev center; removing redundant constraints
  • adjustable robust optimization

Cite this

@article{c345833d9adc47d3b87decbe0d6fb63c,
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 = "Fourier-Motzkin elimination, maximum volume inscribed ellipsoid, polytopic projection, Chebyshev center; removing redundant constraints, adjustable robust optimization",
author = "Jianzhe Zhen and {den Hertog}, Dick",
year = "2018",
month = "1",
doi = "10.1287/ijoc.2017.0763",
language = "English",
volume = "30",
pages = "31--42",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

Computing the maximum volume inscribed ellipsoid of a polytopic projection. / Zhen, Jianzhe; den Hertog, Dick.

In: INFORMS Journal on Computing, Vol. 30, No. 1, 01.2018, p. 31-42.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Computing the maximum volume inscribed ellipsoid of a polytopic projection

AU - Zhen, Jianzhe

AU - den Hertog, Dick

PY - 2018/1

Y1 - 2018/1

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 - Fourier-Motzkin elimination

KW - maximum volume inscribed ellipsoid

KW - polytopic projection

KW - Chebyshev center; removing redundant constraints

KW - adjustable robust optimization

U2 - 10.1287/ijoc.2017.0763

DO - 10.1287/ijoc.2017.0763

M3 - Article

VL - 30

SP - 31

EP - 42

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 1

ER -