Skip to main content
6 of 12
Added the solution pointed out by Dima Pasechnik.
Hans
  • 2.3k
  • 15
  • 30

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. But of course I must have missed something. Could someone please point out exactly what it is?


Epilogue: As Dima Pasechnik points out, the proposition is obtained when we set $$\lambda_i = u_i\frac{A_{ij}}{\beta_i}.$$ What prevented me from making this step from early on was I ignorantly dismissed the possibility of $\lambda$ dependent on $b$ and especially $x_0$.

Hans
  • 2.3k
  • 15
  • 30