# check for a compact set

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

• – Lord Shark the Unknown Nov 9 '19 at 17:32
• Regardless of the quoted assertion being true (which it might be, for all I know), it seems rather obvious that with your assumptions the set $S$ needs not be bounded. For instance, if $A$ and $B$ have all positive entries, then for all $x,y$ with strictly positive entries there will be some $\lambda>0$ such that, for all $\alpha>\lambda$, $(\alpha x,\alpha y)\in S$. – Gae. S. Nov 9 '19 at 17:36
• can you provide a rigorous mathematical proof? – Kethan Chauhan Nov 9 '19 at 17:45
• Of what?${}{}{}$ – Gae. S. Nov 9 '19 at 17:46
• Since the set is a closed subset of $\mathbb R^{m+n}$, it is compact if and only if it is bounded. So what has to be proved is that there are no non-empty bounded sets of this form. – celtschk Nov 9 '19 at 18:38

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.