Given a polyhedron $\mathbf{Ax} \leq \mathbf{b}$, how to find the largest hypercuboid, with unknown center $\mathbf{x_{0}}$ and side lengths $2\epsilon_{i}$, which are aligned along the co-ordinate axes that fit inside?

By 'largest', I'm flexible with the definition. It could be $\prod_{i} \epsilon_{i}$ or $\sum_{i} \epsilon_{i}$, the latter being a linear objective function.

The problem is quite well known for ellipsoids and hypercubes, but the fact that there are unequal side lengths, which themselves are unknowns, seems to make it a tricky one.


It turns out that the problem has quite an elegant solution.

Let the hypercuboid be defined by $\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$ instead of using the more cumbersome $\mathbf{x_{0}}$ and $\epsilon_{i}$

For a hypercuboid to lie within a polyhedron, each of its vertices must lie inside, that is, satisfy the inequality $\mathbf{Ax} \leq \mathbf{b}$. Note that every vertex consists of co-ordinates either from $\mathbf{l}$ or $\mathbf{u}$. Thus, there is one vertex which is $\mathbf{u}$ for all the positive entries of $\mathbf{A}$ and $\mathbf{l}$ for all negative entries. This can be written more succinctly as

Define $\mathbf{A^{+}_{ij}} = max(0,\mathbf{A}_{ij})$ and $\mathbf{A^{-}_{ij}} = max(0,-\mathbf{A}_{ij})$

The hypercuboid constraint can thus be written as $\mathbf{A^{+}u - A^{-}l} \leq \mathbf{b}$

For maximum volume, one could use the concave function, geometric mean($\mathbf{u-l}$), as the objective function. This can be easily solved in CVX, for example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.