0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ look at the dual polytope P* of P. Then your halfspace does not cut P iff it is contained in P*, more or less by definition of the dual polytope. $\endgroup$ Mar 4 at 22:00
  • $\begingroup$ @DimaPasechnik: I do not understand your comment. I just looked up the definition of a dual polytope. It seems to me that however this other polytope is configured, so long as it is not the complement of $P$, the iff does not seem to hold. What am I missing? Could you please elaborate? $\endgroup$
    – Hans
    Mar 4 at 23:19
  • $\begingroup$ P* contains the inequalities valid for P. Vertices of P* are facets of P, convex linear combinations of vertices of P* are, in general, less tight inequalities valid for P, what is unclear? Try this on a 4 gon in plane... $\endgroup$ Mar 4 at 23:45
  • 1
    $\begingroup$ Meta question about the accepted answer to this question: meta.mathoverflow.net/questions/5084/… $\endgroup$
    – YCor
    Jul 1 at 14:14
6
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ +1. This is a great approach. I will try to prove the original proposition directly via the Farkas lemma or the separating hyperplane theorem. $\endgroup$
    – Hans
    Mar 15 at 16:46
  • $\begingroup$ well, I think you could accept this answer, as proving strong duality for LPs (using Farkas lemma, or otherwise) is really bookwork, something not needed to be repeated here. $\endgroup$ Mar 15 at 22:32
  • $\begingroup$ Agree. Accepted. $\endgroup$
    – Hans
    Mar 17 at 12:22
2
$\begingroup$

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^*$.

$\endgroup$
14
  • $\begingroup$ Cool! I see that when the origin is in the interior of the convex hull $P*$ of the rows of the $A$ scaled as you described, called $A'$, $\beta^-1a' = u^T A'$ where $u\ge0$ and $u^T\mathbf 1=1$. But how does one proceed to show the two desired relations from here, especially the second one? $\endgroup$
    – Hans
    Mar 5 at 22:05
  • $\begingroup$ if your a'x<b' cannot be normalised so that b'=1 then it is not valid (check for x=0). $\endgroup$ Mar 6 at 0:28
  • $\begingroup$ Let us say $b'$ or $\beta>0$ so that $b'^{-1}a'^Tx\le1$. How do we argue for the desired relation? $\endgroup$
    – Hans
    Mar 6 at 0:38
  • $\begingroup$ P* is a polytope, and so each point $a$ (ie an inequality $<a,x>\leq 1$ ) in P* can be expressed as $\lambda A$ for $\lambda \geq 0$, $\sum \lambda_k=1$. For each point $a$ outside, there will be a separating hyperplane, which, in case of P*, is just $z \in P$ s.t. $<a,z> >1$. $\endgroup$ Mar 6 at 10:17
  • 2
    $\begingroup$ Proved, naturally, and please note I am not oblidged to provide you more details - it's a research maths forum, not undergraduate maths forum. The whole question ought to be closed as being out of scope. $\endgroup$ Mar 9 at 9:45
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ how about setting $\lambda_i=u_i/b_{1,i}$ ? We're playing a bit carelessly with signs of $b_{1,k}$ here, but assuming $b_1>0$ it all looks fine. $\endgroup$ Mar 10 at 0:32
  • $\begingroup$ @DimaPasechnik: I discussed your suggestion in my answer above. It is not clear to me this works in general. Also I have improved my symbols. $\endgroup$
    – Hans
    Mar 10 at 3:30
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can the down-voter explain why he down-votes? What is wrong with the proof? $\endgroup$
    – Hans
    Jul 1 at 14:40
  • $\begingroup$ you unaccepted this answer and accepted this one, without even mentioning the original accepted answer. The author of the originally accepted answer believes this is unfair, and posted this question on Meta (apparently without notifying you), and possibly downvoted this answer. While I don't believe downvoting was accurate (nor am I sure who downvoted your answer), I believe you should react to the meta post in some way. $\endgroup$
    – YCor
    Jul 1 at 18:36
  • $\begingroup$ @YCor: Thank you for alerting me to the Meta post related to this question. I have never used Meta part of mathoverflow. I will look into that item later, as I am occupied right now, and respond accordingly. $\endgroup$
    – Hans
    Jul 1 at 20:12

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.