# Maximum volume inside a convex polyhedron

For a rectangle $$\mathcal R = \{ x \in R^n \mid l \preceq x \preceq u \}$$ of maximum volume to be enclosed in polyhedron $$\mathcal P = \{ x \mid Ax \preceq b \}$$, according to Stephen Boyd's EE364a Homework 7 solutions, we simply need

$$\sum\limits_{j=1}^n(a_{ij}^+ u_j - a_{ij}^- l_j)\leq b_i, \quad i=1, \dots, m$$

where $$a_{ij}^+ = \max(a_{ij}, 0)$$ and $$a_{ij}^- = \max(-a_{ij}, 0)$$. How can I see this fact?

First, if $$\sum\limits_{j=1}^n(a_{ij}^+ u_j - a_{ij}^- l_j)\leq b_i, i=1, \dots, m$$, we prove $$\mathcal{R}\subset \mathcal{P}$$.
Let $$V_i^+=\{j|a_{ij}\ge 0\}$$ and $$V_i^-=\{j|a_{ij}< 0\}$$, then we have $$\sum\limits_{j\in V_i^+}a_{ij}^+ u_j - \sum\limits_{j\in V_i^-}a_{ij}^- l_j\leq b_i, i=1, \dots, m$$
For $$j\in V_{i}^+$$ and $$x\in \mathcal{R}$$, we have $$a_{ij}x_{j}=a_{ij}^+x_{j}\le a_{ij}^+u_j$$. Similarly, for $$j\in V_{i}^-$$ and $$x\in \mathcal{R}$$, we have $$a_{ij}x_{j}=-a_{ij}^-x_{j}\le -a_{ij}^-l_j$$
Thus, we have \begin{align*} \sum\limits_{j=1}^na_{ij}x_{j}=&\sum\limits_{j\in V_i^+}a_{ij}x_j+\sum\limits_{j\in V_i^-}a_{ij}x_j\\ \le & \sum\limits_{j\in V_i^+}a_{ij}^+u_j-\sum\limits_{j\in V_i^-}a_{ij}^-l_j\\ \le & b_i, i=1,\cdots,m \end{align*} Therefore, if $$\sum\limits_{j=1}^n(a_{ij}^+ u_j - a_{ij}^- l_j)\leq b_i, i=1, \dots, m$$, we then have $$\mathcal{R}\subset \mathcal{P}$$.
Coversely, if $$\mathcal{R}\subset \mathcal{P}$$, we construt a vector $$x\in \mathcal{R}$$ which satisfys: if $$j\in V_{i}^+$$, $$x_{j}=u_j$$, otherwise, $$x_j=l_j$$. Then according to $$\mathcal{R}\subset \mathcal{P}$$, we must have $$Ax\le b$$, which is exactly the same as $$\sum\limits_{j=1}^n(a_{ij}^+ u_j - a_{ij}^- l_j)\leq b_i, i=1, \dots, m$$
• So you essentially loosen $a_{ij} x_j$ and then say if the looser thing still meets the $Ax \leq b$ criterion, then we're all good? How does this ensure the corners of the rectangle still fall inside the polyhedron? The intuition here is non-obvious. Commented Apr 4 at 0:43