Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
How to prove this
$$S = \{(x, y) | Ax + By ≥ c, x ≥ 0, y ≥ 0\}$$ where $A$ is an $m \times n$ matrix, $B$ is a positive semi-definite $m \times m$ matrix and $c \in \Bbb R^m$. The author explicitly assumed the set $S$ is compact in $\Bbb R^{n+m}$. A reviewer of the paper pointed out that the only compact set of the above form is the empty set. Prove the reviewer’s assertion
Claim (which I thought would be true, and it was eventually proved in this linked question).
If $B$ is positive semi-definite then there is $z\ge0$ with $z\neq0$ such that $Bz\ge0$.
(Here $z\ge0$ means that every component of $z$ is non-negative.
By $z\neq0$ we mean that at least one component of $z$ is non-zero.)
(Two proofs of this claim were given by user @daw in my linked question. The same user posted an answer to OP question here too.)
Using the above claim we show that if the set $S=\{(x,y)|Ax+By\ge c,x\ge0,y\ge0\}$ is non-empty, then it is unbounded.
Take any $(x,y)\in S$. Let $z$ be as in the claim.
Then $(x,y+\lambda z)\in S$
for all $\lambda>0$, proving that $S$ is unbounded.
(Indeed, clearly $Ax+B(y+\lambda z)=Ax+By+\lambda Bz\ge c+\lambda0=c$.)
Assume that the set in question is compact and non-empty. Then the linear programming problem $$ \min -e_1^Tx_1 - e_2^Tx_2 $$ subject to $$ Ax_1 + Bx_2 -x_3 =c $$ with $x_i\ge0$ for all $i$ has a solution. Here, $e_1$ and $e_2$ are vectors of all ones of suitable size.
The dual problem of the above problem is: $$ \max c^Ty $$ subject to $$ A^Ty \le -e_1, \ B^Ty \le -e_2 , \ -y\le 0. $$ This problem has no feasible point: Let $y\ge0$ and $y\ne0$. Then $y^TBy\ge 0>-e_2^Ty =- \|y\|_1$. In addition, $y=0$ is not feasible. This is a contradiction to strong duality: the primal problem is solvable but the dual not.
Hence, the set in question cannot be both non-empty and compact.
