Fitting a convex polytope into another convex polytope

[cr34m3]

Hi,

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é

 

[jvicens]

Hi André,

Thank you for sharing your problem with us. It is certainly an interesting one and I can see why you are having some difficulty finding a solution. Here are a few suggestions that may help you in your quest to maximize the volume of P1 within P2:

1. Consider using a different optimization method. While the methods you have tried so far may not be yielding the desired results, there are many other optimization methods out there that may be better suited for your problem. For example, genetic algorithms or simulated annealing may be useful in finding a global maximum for your objective function.

2. Try using a different objective function. Instead of simply maximizing the volume of P1, you could consider incorporating penalties or constraints that take into account the shape of P1. This may help prevent P1 from inverting itself or migrating to the edges of P2.

3. Consider using a different representation for your polytopes. While a halfspace description may have been favored initially, it may not be the most suitable for this particular problem. You could try using a vertex description instead, as it may provide a clearer correlation between the number of vertices and the number of faces.

4. Look into other methods of measuring volume. Instead of simply using the traditional volume formula for your polytopes, you could consider using alternative measures of volume that may be better suited for your problem. For example, you could use the determinant of the covariance matrix of the points in P1 or P2 as a measure of volume.

I hope these suggestions help you make progress on your problem. Good luck!