How to prove a cone is convex and closed?

Question

Let $A$ be a $m\times n$ matrix and consider the cones $G_0=\{d\in\mathbb R^n:Ad<0\}$ and $G'=\{d\in\mathbb R^n:Ad\le0\}$

Prove that $G'$ is a convex closed cone.

Lets see that $G'=\overline{ G'}.$ Note that this contention $G'\subset\overline{ G'}$ is always true. Let's see the other contention.

Suppose $d\in\overline{G'}$ and $d\not\in G'. $ Thus For every open ball $B$ with $d\in B$ we have that $B\cap G'\neq\emptyset$ and $ Ad>0$

How can I reach the contradition? Is this a good way to prove it or is there a better way? I don't know

And how to prove convexity?

Please help me please thanks

Answer 1

To prove $G'$ is closed from scratch without any advanced theorems. Following your suggestion, one way $G'\subset\overline{G'}$ is trivial, let's prove the opposite inclusion by contradiction.

Let's start as you did by assuming that $\exists d\not\in G'$, $d\in\overline{G'}$. Since $d\not\in G'$, there exists one inequality among $Ad\le 0$ that is not true. In other words, there exists a row $a^T$ in the matrix $A$ such that $a^Td>0$. We denote $\rho=a^Td$ and show that for all $x$ that are close enough to $d$ we have $a^Tx>0$ too, which will mean that $x\not\in G'$ as well. Let's estimate $$ a^Tx=a^Td+a^T(x-d)\ge\rho-|a^T(x-d)|\ge\rho-\|a\|\|x-d\|. $$ From here we see that $$ \|x-d\|<\frac{\rho}{\|a\|}=\epsilon\quad\Rightarrow\quad a^Tx>0. $$ Conclusion: we have found an open ball $B$ around $d$ $$ B=\{x\colon \|x-d\|<\epsilon\} $$ such that all $x\in B$ do not belong to $G'$, that is $B\cap G'=\emptyset$. This is a contradiction with the assumption that $d\in\overline{G'}$.

Answer 2

To prove that $G^\prime$ is closed use the continuity of the function $d \mapsto Ad$ and the fact that the set $\{d \in \mathbb{R}^n : d \leq 0\}$ is closed.

Answer 3

And to show that $G'$ is convex just take two points $x,y \in G'$, the segment between these points must lie in $G'$. Let $0\leq \alpha\leq 1$, study the point $p = \alpha x + (1-\alpha)y$: $$ Ap = A(\alpha x + (1-\alpha)y) = \alpha Ax + (1-\alpha)Ay \leq 0 $$ the last inequality is true because $\alpha, 1-\alpha \geq 0$ and since $x,y \in G'$ than $Ax \leq 0$ and $Ay \leq 0$.

Answer 4

$Ad \le 0$ iff $e_k^T A d \le 0$ for $i=1,...,m$.

A set of the form $\{ x | n^T x \le \alpha \}$ is quickly checked to be closed and convex from the definition.

The intersection of a collection of closed convex sets is convex.

Elaboration:

$G'=\{ x| Ax \le 0 \} = \{ x | e_1^T A x \le 0, ..., e_m^T A x \le 0 \} = \cap_{k=1}^m \{ x | e_k^T A x \le 0 \}$.

$e_k$ is the vector of zeros except for a one in the $k$th position. Note that $e_k^T A$ is a column vector.

Each set $\{ x | e_k^T A x \le 0 \}$ is a half space, and to check if it closed, suppose $x_n \to x$ and $e_k^TA x_n \le 0$. Then by continuity (of the linear function $x \mapsto e_k^T Ax$) we have , $e_k^TAx \le 0$ and so the set is closed. To check convexity, note that $x \mapsto e_k^T Ax$ is linear and so $e_k^TA (\lambda x_1+(1-\lambda)x_2) = \lambda e_k^T A x_1 + (1-\lambda)e_k^T A x_2$ and so the set is convex.

It is straightforward to check that the intersection of closed sets is closed and it is straightforward to check that the intersection of convex sets is convex.

For the $G_0$ set, the same sort of reasoning applies, the only difference is that the intersection of a finite number of open sets is open (this is the case here), not an arbitrary intersection.