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?


1 Answer 1


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$$

  • $\begingroup$ 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. $\endgroup$ Commented Apr 4 at 0:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .