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

  • 2
    $\begingroup$ Please see math.meta.stackexchange.com/questions/5020 $\endgroup$ – Lord Shark the Unknown Nov 9 '19 at 17:32
  • $\begingroup$ 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$. $\endgroup$ – Gae. S. Nov 9 '19 at 17:36
  • $\begingroup$ can you provide a rigorous mathematical proof? $\endgroup$ – Kethan Chauhan Nov 9 '19 at 17:45
  • $\begingroup$ Of what?${}{}{}$ $\endgroup$ – Gae. S. Nov 9 '19 at 17:46
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


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.