1

I am reading a proof which is showing that two (polyhedral) cones $K$ and $K'$ are equal. These cones are constructed from matrices $A\in\mathbb{R}^{p\times k}$ and $B\in\mathbb{R}^{k\times q}$, where rank$(A) = $ rank$(B) = k = $ rank$(AB)$ and the product is non-negative, i.e. $AB\in\mathbb{R}^{p\times q}_+$. Specifically, $K = \text{cone}(a_1,\dots, a_p)$ and $K' = \{x\in\mathbb{R}^k\text{ }|\text{ }x^Tb^j\geq 0,\text{ }j = 1,\dots, q\}$, where $a_i$ is the $i$-th row of $A$, $b^j$ is the $j$-th column of $B$, and cone($X$) is the cone generated by all the conic combinations of vectors in $X$. To prove the equality, we show each of the containments.

It is easy to see that $K\subset K'$ since each $a_i\in K'$, as $a_i^Tb^j$ is the $ij$-entry of $AB$, and each entry in $AB$ is assumed to be non-negative by hypothesis, so we can then extend the containment to all of $K$. The way that $K'\subset K$ is shown is by showing that $\text{for any linear function }L:\mathbb{R}^k\longrightarrow\mathbb{R}$ such that $L$ is non-negative on $K$, then $L$ is also non-negative on $K'$.

I was able to follow why this claim regarding $L$ was true, but I do not see why this then implies that $K'\subset K$. It is apparently supposed to be straightforward from here, but unfortunately I do not see why. Can someone help show me why this is true?

t42d
  • 496
  • It is not clear to me that if $L$ is non negative on $K$ that it is non negative on $K'$. – copper.hat Feb 27 '20 at 19:52
  • The reasoning is somewhat involved and requires some extra context, and I think all the excessive details would be a bit distracting from my question. I think the only relevant thing is that it IS true. But my concern is whether or not this being true implies the result. In other words it would be better to just assume this statement about $L$ as a hypothesis, with the conclusion being $K'\subset K$. Would it possibly be more helpful if I edited the question so that this statement was explicitly made to be a hypothesis? – t42d Feb 27 '20 at 20:17
  • Ok, the part you want ts fairly straightforward using the Hahn Banach separation theorem, I had added the detail below, but the other result is still interesting to me :-). – copper.hat Feb 27 '20 at 20:57

1 Answers1

0

Suppose $C$ is a closed convex cone and $p \notin C$. Then Hahn Banach shows that there is some linear functional $L$ and constant $\alpha$ such that $L(p) < \alpha \le L(x)$ for all $x \in C$. Since $C$ is a cone, we see that $\alpha \le 0$.

Now suppose $K \subset K'$ are both closed convex cones. If $K'\setminus K$ is non empty, we can use the previous result to find some $L$ that is non negative on $K$ but negative on some point of $K'$.

Hence if every $L$ that is non negative on $K$ is also non negative on $K'$, then we must have $K=K'$.

Note:

A shorter way is to note that if $K^* \subset (K')^*$, then $K' = (K')^{**} \subset K^{**} = K$.

$K=K^{**}$ holds for closed convex cones in finite dimensional space. (A similar result hold more generally, but one needs a notion of a pre dual cone which is not relevant here. See Dual of a dual cone)

copper.hat
  • 172,524
  • First, thank you very much - I have never even heard of this theorem before, and would never have come up with this. Second, regarding your second shorter method, is the emphasis on the 'if' in that statement (i.e. is $K^\subset (K')^$ something that would need to be proven independently, or is this fact obvious for some reason)? Lastly, regarding the result on $L$, the original paper is the appropriate source for details (this result is Lemma 5 in the paper). It is all routine linear algebra based on the hypotheses, but the context matters. – t42d Feb 28 '20 at 05:01
  • Generally (with closed convex cones) if $A \subset B$ then $B^* \subset A^$ (this is easy to show). The other result is that $A=A^{*}$, but you need the Hahn Banach separation theorem to show one of the inclusions. – copper.hat Feb 28 '20 at 05:14
  • The Hahn Banach theorem is a very useful theorem in functional analysis. It is geometrically obvious but takes a little work to prove. – copper.hat Feb 28 '20 at 05:17
  • Thanks for the reference, more conditions are needed to show the $L$ condition (CCGC). I can sleep now :-) – copper.hat Feb 28 '20 at 05:20