Confining a polytope to one side of an affine hyperplane

Question

Judging whether one convex polytope is inside of another when both are expressed as a system of linear inequalities seems not to be an easy problem. This answer on math.stackexchange.com claims the following proposition regarding a special case.

Using Farkas' lemma to show, a halfspace $\{x \mid a' x \leq b' \}$ contains the polytope $P= \{x |A x \leq b \}$ if and only if there exists $\lambda \in \mathbb{R}^m$ with $\lambda \geq 0$ (understood component-wise) such that: \begin{align*} a' &= \lambda^T A \\ b' &\geq \lambda^T b \end{align*}

It is easy to prove the sufficiency. I am able to show the necessity of $a' = \lambda^T A$ by Farkas' lemma, but not $b' \geq \lambda^T b$. I tried but failed to argue by contradiction. How does one prove that last inequality?

Answer 1

On can use Linear Programming (LP) duality. Consider the LP problem $$\beta':=\max \langle a',x\rangle : x\in P.\tag{P}$$ So $\beta'$ is minimal number s.t. $\langle a',x\rangle\leq\beta'$ for all $x\in P$. Thus $\beta'\leq b'$, for $b'$ as in the question.

The dual of (P) is $$ \beta^*:=\min \langle\lambda,b\rangle : \lambda\geq 0, \lambda^\top A=a'. \tag{D} $$ So we see that (D) encodes all the possible $\lambda$ giving $\lambda^\top A=a'$.

Strong duality says that $\beta'=\beta^*$, i.e. there exists feasible $\lambda$ s.t. $\langle \lambda, b\rangle=\beta'\leq b'$, as required.

Strong duality is not so easy to show, and it appears to be equivalent to the question asked. (Note that it is easier to show weak duality, which is $\beta^*\geq\beta'$, and this does not give the needed inequality).

Answer 2

This is not really a complex problem. It is a straightforward excercise about the dual polytope $P^*$ of $P$ (that every polytope $Q\supset P$ has all its inequalties in $P^*$).

For clarity, assume that $P$ is full-dimensional, and that the origin is in the interior of $P$. Then $b>0$. Hence $A$ can be scaled so that $b=(1,\dots,1)$.

Now $P^*$ is the convex closure of the rows of $A$, and every valid for $P$ inequality $\langle a',x\rangle\leq \beta$ satisfies $\beta>0$, i.e. is equivalent to $\beta^{-1}\langle a',x\rangle\leq 1$, and $\beta^{-1} a'\in P^*$.

Answer 3

This is not a proof per se but for detailed discussion with Dima Pasechnik. It is too long for the comment section.

---

Suppose $P$ is bounded and not a singleton. The original proposition does not stipulate $0\in $ interior of $P$.

I transcribe Dima Pasechnik's answer in detail as follows. We pick an interior point $x_0$ of $P$, i.e., $Ax_0<b$. Let $y:=x-x_0$. \begin{align} Ay&\le b-Ax_0=:\beta \\ \implies a'y&\le b'-a'x_0=:\beta' \end{align} where vector $\beta>0$ and scalar $\beta'>0$. Writing the matrices in the entry form so as to be clear, we have \begin{align} \sum_j\frac{A_{ij}}{\beta_i}y_j&\le1 \\ \implies \sum_j\frac{a'_j}{\beta'}y_j&\le1. \end{align} By Farkas' lemma or the separating hyperplane theorem, $\forall j$, $\frac{a'_j}{\beta'}$ is a convex combination of $\Big\{\frac{A_{ij}}{\beta_i}\Big\}_i$, or $\exists u\in R^n$ such that $u_i\ge0\, \forall i, \sum_iu_i=1$ and $$\frac{a'_j}{\beta'}=\sum_i u_i\frac{A_{ij}}{\beta_i}$$ or $$\frac{a'_j}{b'-\sum_ja'_jx_{0,j}}=\sum_i u_i\frac{A_{ij}}{b_i-\sum_jA_{ij}x_{0,j}} \tag1$$ $\forall j$.

Now, the question is how one derives from Equation (1) the desired inequalities in the question, i.e. \begin{align} a'_j &= \sum_i\lambda_i A_{ij} \quad\forall j, \\ b' &\geq \sum_i\lambda_i b_i \tag2 \end{align} for some $\lambda_i\ge0, \forall i$ (without requiring $\sum_i\lambda_i=1$).

Note that the convex combination in (1) is for the ratio as opposed to for the numerator and denominator separately. Moreover, the denominator of (1) involves $A, a', x_0$ rather than just $b$ and $b'$, while (2) especial the second relation $b'\ge \lambda^Tb$ is independent of $A, a'$ especially $x_0$.

---

I doubt you can derive (2) from (1) directly without other conditions.

If we define as Dima Pasechnik suggests $$\lambda_i := u_i\frac{\beta'}{\beta_i},$$ we obtain the equation above Inequality (2) which I had obtained without the normalization or the dual polytope concept, as well as for $x_0=0$ which makes $\beta=b$ and $\beta'=b'$ the equality version of (2). However, it is not clear how we could arrive at Inequality (2) under the general condition where both $\beta$ and $\beta'$ depend on $x_0$ which is the ultimate question I am after, since $\beta$ and $\beta'$ depend on $x_0$ while $b$ and $b'$ do not.

Answer 4

Here is a proof that uses directly the separating hyperplane theorem, which states the following.

Given a matrix $A$ and column matrix $b$, \begin{align} Ax=b, &\text{ for some column matrix }x\ge0 \\ &\iff \\ y^TA\ge0 &\text{ for some column matrix }y \implies y^Tb\ge0 \end{align}

---

We put as follows the required proposition into the above form with the exception that the matrix is transposed. The premise of the proposition is \begin{align} &\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}\begin{bmatrix} -xx_1 \\ x_1 \end{bmatrix}\ge 0 \\ &\iff \\ &\begin{cases} Ax\le b \implies a'^Tx\le b' \\ x_1\ge0 \end{cases} \\ &\implies \\ &\begin{bmatrix}a'^T &b'\end{bmatrix} \begin{bmatrix}-xx_1 \\x_1 \end{bmatrix}\ge0 \end{align}

The conclusion of the proposition is \begin{align} &\begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\begin{bmatrix} A & b \\ 0 & 1 \end{bmatrix}=\begin{bmatrix}a'^T & b'\end{bmatrix}, \text{ for some} \begin{bmatrix}\lambda^T & \lambda_1\end{bmatrix}\ge0 \\ &\iff \\ &\exists \lambda\ge0 \ni \begin{cases} \lambda^TA=a'^T \\ \lambda^Tb\le b' \end{cases} \end{align}

The premise and the conclusion are seen to be equivalent in view of the separating hyperplane theorem as stated above. We have now proved the desired proposition.