Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To test for a particular property of positive LTI systems using feasibility problems I've come across the following claim which, intuitively, I believe can be generalised. I think I've (rather un-elegantly) proved it in the simplest case. However, I can't seem to make any headway trying to extend the proof. Any help would be greatly appreciated. The claim and my proof are next and my questions regarding the claim and its potential generalisations are after that.

Many thanks in advance.

Suppose that we have vectors $v_1,v_2,u\in\mathbb{R}^n$ that form a linearly independent set, three cones $C_1:=\{\theta_1v_1+\theta_2u:\theta_1,\theta_2>0\}$, $C_2:=\{\theta_1v_2+\theta_2u:\theta_1,\theta_2>0\}$ and $C:=\{\theta_1v_1+\theta_2v_2:\theta_1,\theta_2>0\}$ and a convex set $A$. Consider a fourth cone $C_v:=\{\theta_1v+\theta_2u:\theta_1,\theta_2>0\}$ where $v\in C$.

The aim is to show that:

Claim: If $A\cap C_1\neq\emptyset$ and $A\cap C_2\neq\emptyset$, then, for any $v\in C$, $A\cap C_v\neq\emptyset$.

If I'm not mistaken, one way to prove this is to consider the convex hulls $\mathcal{H}(C_1\cup C_2)$, $\mathcal{H}(C_1\cup C_v)$ and $\mathcal{H}(C_2\cup C_v)$. Notice that by definition of convex hull, $\mathcal{H}(C_1\cup C_2)=\mathcal{H}(C_1\cup C_v)\cup \mathcal{H}(C_2\cup C_v)$ and, due to linear independence of $v_1,v_2$ and $u$, $\mathcal{H}(C_1\cup C_v)\cap \mathcal{H}(C_2\cup C_v)=C_v$.

Because $A\cap C_1\neq\emptyset$ and $A\cap C_2\neq\emptyset$, there exists $x,y\in\mathbb{R}^n$ such that $x\in A, x\in C_1$ and $y\in A, y\in C_2$. Then by convexity of $A$, the line segment $l:=\{(1-\theta) x+\theta y:\theta\in[0,1]\}$ is contained in $A$, i.e., $l\subset A$. Hence it is sufficient to show that $l\cap C_v\neq\emptyset$.

Once again, by convexity, $l\subset \mathcal{H}(C_1\cup C_2)$. Let $l_1:=l\cap\mathcal{H}(C_1\cup C_v)$ and $l_2:=l\cap\mathcal{H}(C_2\cup C_v)$. Note that $x\in l_1$ and $y\in l_2$, hence, $l_1$ and $l_2$ are not empty. The intersection of two convex sets is convex, thus $ l_1=\{(1-\theta) x+\theta y:\theta\in[0,k_1]\}$ and $l_2 =\{(1-\theta) x+\theta y:\theta\in[k_2,1]\}$ where $k_1,k_2\in[0,1]$.

Because $\mathcal{H}(C_1\cup C_v)\cap \mathcal{H}(C_2\cup C_v)= C_v$, if $k_1\geq k_2$ then $l\cap C_v\neq\emptyset$ and we are done. Noting that, since $l\subset \mathcal{H}(C_1\cup C_2)$,

$l_1\cup l_2=(l\cap\mathcal{H}(C_1\cup C_v))\cup (l\cap\mathcal{H}(C_2\cup C_v))=l\cap(\mathcal{H}(C_1\cup C_v)\cup \mathcal{H}(C_2\cup C_v))$ $=l\cap \mathcal{H}(C_1\cup C_2)=l$

we can show that $k_1\geq k_2$ by contradiction. Suppose $k_1< k_2$, then $l = l_1\cup l_2=\{(1-\theta) x+\theta y:\theta\in[0,k_1]\cup [k_2,1]\}$ is not convex, giving the contradiction we were looking for.

The figure below provides some intuition regarding the proof, $z=l\cap C_v$.

My questions then are (sorry - some of them overlap slightly):

  1. Is there any flaws in the above proof?

  2. Is this claim a straightforward consequence of some standard theorem?

  3. Is there an alternative (and hopefully simpler) proof for the above which is easy to generalise?

  4. Can the claim be extended to:

Suppose that we have $m\leq n$ vectors $v_1,v_2,\dots,v_{m-1},u\in R^n$ that form a linearly independent set, $m$ cones $C_1:=\{θ_1v_1+θ_2u:θ1,θ2>0\}, C_2:=\{θ_1v_2+θ_2u:θ_1,θ_2>0\}, \dots ,$ $C_{m-1}:=\{θ_1v_{m-1}+θ_2u:θ_1,θ_2>0\}$ and $C:=\{\sum_{i=1}^{m-1}\theta_i v_i:θ_1,\dots,θ_{m-1}>0\}$ and a convex set A. Consider a last cone $C_v:=\{θ_1v+θ_2u:θ_1,θ_2>0\}$ where $v\in C$

Claim: If $A\cap C_1\neq\emptyset,\dots, A\cap C_{m-1}\neq\emptyset$, then, for any $v\in C$, $A\cap C_v\neq\emptyset$.

5 . What about to (including its own extensions):

Suppose that we have $4$ vectors $v_1,v_2,u_1,u_2\in R^n$ that form a linearly independent set, $6$ cones $C_1:=\{θ_1v_1+θ_2u_1:θ1,θ2>0\}, C_2:=\{θ_1v_2+θ_2u_1:θ_1,θ_2>0\}, $ $K_{1}:=\{θ_1v_1+θ_2u_2:θ_1,θ_2>0\}$, $K_{2}:=\{θ_1v_2+θ_2u_2:θ_1,θ_2>0\}$, $C:=\{θ_1v_1+θ_2v_2:θ_1,θ_2>0\}$ and $K:=\{θ_1u_1+θ_2u_2:θ_1,θ_2>0\}$ and a convex set A. Consider a last cone $C_{v,u}:=\{θ_1v+θ_2u:θ_1,θ_2>0\}$ where $v\in C$ and $u\in K$.

Claim: If $A\cap C_1\neq\emptyset, A\cap C_2\neq\emptyset, A\cap K_1\neq\emptyset$ and $A\cap K_2\neq\emptyset$, then, for any $v\in C,u\in K$, $A\cap C_{v,u}\neq\emptyset$.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.