- #1

cr34m3

- 2

- 0

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.

André