Expressions for the dual of a polyhedral cone

528 Views Asked by At

Let $K$ be a polyhedral cone generated by the rows of a matrix $A\in\mathbb{R}^{p\times n}$, and constrained by the columns of a matrix $B\in\mathbb{R}^{n\times q}$, such that $K = \text{cone}(A_1^T,\dots, A_p^T) = \{x\in\mathbb{R}^n\text{ }|\text{ }x^TB\geq\textbf{0}^T\}$, where $A_i$ denotes the $i$-th row vector of $A$. Additionally, suppose the matrix $AB\in\mathbb{R}^{p\times q}$ is non-negative.

We have that the dual cone $K^* := \{y\in\mathbb{R}^n\text{ }|\text{ }x^Ty\geq 0\text{ }\forall x\in K\} = \{y\in\mathbb{R}^n\text{ }|\text{ }Ay\geq\textbf{0}\}$.

I want to show that it is also true that $K^* = \text{cone}(B^1,\dots, B^q)$, where $B^j$ denotes the $j$-th column vector of $B$.

I can see that the '$\supset$' inclusion is true, because each $B^j$ is in $K^*$ (since $K = \{x\in\mathbb{R}^n\text{ }|\text{ }x^TB\geq\textbf{0}^T\}$, and each $A_i^TB^j = (AB)_{ij}\geq 0$ by hypothesis, so we can extend linearly to cone$(A_1^T,\dots A_p^T) = K$), so then again by linearity I can extend to all conic combinations of the $B^j$'s, i.e. $K^*\supset\text{cone}(B^1,\dots, B^q)$. However, I am struggling with the other inclusion. I know that I haven't used the fact that $K^* = \{y\in\mathbb{R}^n\text{ }|\text{ }Ay\geq\textbf{0}\}$, but I don't see how to use this. The solution is supposed to be pretty straightforward, but unfortunately I don't see it. Would someone be able to help me see this?

1

There are 1 best solutions below

0
On BEST ANSWER

\begin{align} K^* &= \{ y \mid x^Ty \geq 0 \quad \forall x : B^Tx \geq 0\} \\ &= \{y \mid \min_x\{x^T y \mid B^Tx\geq0\} \geq 0 \} \\ &= \{y \mid \max_{z \geq 0}\{0 \mid Bz = y\} \geq 0 \} \\ &= \{Bz \mid z \geq 0 \} \end{align}