Computing the maximum volume inscribed ellipsoid of a polytopic projection
| Autor: | Jianzhe Zhen, Dick den Hertog |
|---|---|
| Přispěvatelé: | Center Ph. D. Students, Research Group: Operations Research, Econometrics and Operations Research |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization jel:C63 jel:C61 Chebyshev center 0211 other engineering and technologies Polytope 02 engineering and technology polytopic projection jel:C44 removing redundant constraints maximum volume inscribed ellipsoid Maximum volume inscribed ellipsoid chebyshev center adjustable robust optimization Fourier–Motzkin elimination 020901 industrial engineering & automation TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering Mathematics::Metric Geometry Projection (set theory) Mathematics 021103 operations research General Engineering Robust optimization Ellipsoid Simple polytope Relative interior Convex body 020201 artificial intelligence & image processing Algorithm Inscribed figure Fourier-Motzkin elimination MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | INFORMS Journal on Computing, 30(1), 31-42. INFORMS Inst.for Operations Res.and the Management Sciences |
| ISSN: | 1091-9856 |
| Popis: | 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. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0763 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|