# Largest hypercuboid inside a polyhedron

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.

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.