Fitting a convex polytope into another convex polytope

by cr34m3
Tags: halfspaces, optimizing, polytopes
cr34m3 is offline
Sep28-10, 03:05 AM
P: 2

I am presently writing Python code to solve the following problem; fit the largest volume polytope (P1), with a given number of faces, into a known other polytope (P2) (with more faces than the one being fitted inside). Both polytopes are convex and are described by the feasible region of a number of halfspaces, also both polytopes have the same number of dimensions.

The polytope, P1, is described by Ax < b. A halfspace description was favoured above a vertex description as the number of vertices do not have a clear correlation to the number of faces (which are to be specified). The solution would then be;
- Optimize for A and b, to
- maximise the volume of P1, subject to
- P1 inside of P2.

In the 2D case, this simplifies to; fit the largest triangle (P1) into a given square (P2).

Two formulations of the problem have been tried;
firstly, using a constrained solver (Sequential Least Squares Quadratic Programming) - this gives problems (especially when P1 inverts itself). The gradient information seems unreliable (noting that for a fixed size gradient matrix, the inequality constraints need to be expressed in terms of the initial shape P2).
Secondly, using an unconstrained solver (Downhill Simplex), reformulating the problem with penalties. Vertices are penalized when outside of the initial shape. This however places too much emphasis on the vertices and makes the solution a very strong function of the starting point. Vertices simply migrate to the edges of P2 without maximising P1's volume.

The problem seems rather straightforward, but I'm not making progress.

Any suggestions on problem reformulation or methods of solving this would be greatly appreciated.

Phys.Org News Partner Science news on
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes

Register to reply

Related Discussions
Tiling the faces of a polygon/polytope Differential Geometry 0
Proving a convex function on an open convex set satisfies some inequalities Calculus & Beyond Homework 1
number of edges of a convex polytope with n vertices Calculus & Beyond Homework 4
Help with Convex. Differential Geometry 1
Convex Set General Math 13