Equality of two polyhedral cones

121 Views Asked by At

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?

1

There are 1 best solutions below

4
On BEST ANSWER

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)