0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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'}$.

$\endgroup$
  • $\begingroup$ Thank you for your answer $A.\Gamma.$ I have a question: How do you pass from $a^Tx=a^Td+a^T(x-d)\ge\rho-|a^T(x-d)|\ge\rho-\|a\|\|x-d\|$ to $\Vert x-d\Vert<\frac{\rho}{||a||}?$ $\endgroup$ – user441848 Jun 17 '18 at 3:45
  • $\begingroup$ @user441848 If we want $a^Tx>0$ then it is sufficient to require $\rho-\|a\|\|x-d\|>0$. The latter is equivalent to $\rho>\|a\|\|x-d\|$ $\Leftrightarrow$ $\frac{\rho}{\|a\|}>\|x-d\|$. $\endgroup$ – A.Γ. Jun 17 '18 at 6:41
  • $\begingroup$ ok, got it. I have another question, you say: Since $d∉G′$, there exists one inequality among $Ad≤0$ that is not true. I thought that if $d\not\in G',$ then $Ad>0$. But I think you right if we see $G'=\{d\in\mathbb R^n:Ad\le0\}$ equivalent to $G'=\{\forall d\in\mathbb R^n:Ad\le0\}$.Then the negation is there exists $d$ such that.. They must be equivalent right? $\endgroup$ – user441848 Jun 17 '18 at 20:53
  • $\begingroup$ @user441848 The definition of $G'$ is the following: if $A$ is an $m\times n$ matrix then $x\in G'$ iff all $m$ inequalities are $\le$ for this $x$. Now the negaition is: $x$ is not in $G'$ iff not all $m$ inequalities are $\le$ for this $x$. Not all $\le$ is the same as to say that there is at least one $>$. $\endgroup$ – A.Γ. Jun 17 '18 at 20:57
  • $\begingroup$ got it, thank you! $\endgroup$ – user441848 Jun 17 '18 at 21:02
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How will I use continuity? Where? Could you explain with more details? $\endgroup$ – user441848 Jun 16 '18 at 0:20
  • $\begingroup$ Use the fact that the inverse image of a closed set by a continuous map is closed. $\endgroup$ – João Caminada Jun 16 '18 at 0:24
  • $\begingroup$ ? ${}{}{}{}{}{}$ $\endgroup$ – user441848 Jun 16 '18 at 0:28
  • $\begingroup$ Show that $G^\prime$ is the inverse image of the set I specified by the map I specified and use the observation I made in the last comment. $\endgroup$ – João Caminada Jun 16 '18 at 0:31
  • $\begingroup$ Note that the image of $d \to Ad$ with $d \in \{d \in \mathbb{R}^n : d \leq 0\}$ is $G'$ and since a continuos function takes closed sets in the domain to closed sets in the image you got that $G'$ is closed. Look here: math.stackexchange.com/questions/437829/… $\endgroup$ – Lucas Resende Jun 16 '18 at 0:31
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ I don't understand this at all 😳 $\endgroup$ – user441848 Jun 16 '18 at 3:48
  • $\begingroup$ Would you mind to explain? $\endgroup$ – user441848 Jun 16 '18 at 4:06
  • $\begingroup$ Thank you for the explanation :) . I have a question Then by continuty, $e_k^TAx\le0$ and so the set is closed Continuity of what are you refering to? $\endgroup$ – user441848 Jun 17 '18 at 3:30
  • $\begingroup$ In the next pharagraph I think you meant intersection of convex set is convex $\endgroup$ – user441848 Jun 17 '18 at 3:35
  • $\begingroup$ @user441848: I added an elaboration and fixed the typo. $\endgroup$ – copper.hat Jun 17 '18 at 19:32

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.