How to get explicit form of polar cone?

Question

I'm asked about a question to find the explicit form of polar cone of $C=\{x:x=Ap,p\geq 0\}$. But I can only write out by definition $C^*=\{y:y^TAp\leq 0,p\geq 0\}$. But can the expression be more explicit?

Answer 1

It easy to see that the polar is $$ C^* = \{y : A^Ty \leq 0 \} $$

By definition,

$$ C^* = \{y : y^T A p \leq 0, p \geq 0\} $$

Take $p = e_i$, the unit vector with $1$ at coordinate $i$ for some $i$. Then we have

$$ y^T (A)_i \leq 0 \Leftrightarrow (A^T y)_i \leq 0, \forall i $$

Therefore, we just proved that $C^* \subseteq \{ y: A^T y \leq 0 \}$. Now, we will prove that $\{y: A^T y \leq 0\} \subseteq C^*$. Take any such $y$: it is easy to see that

$$ y^T A p = p^T \underbrace{(A^T y)}_{\triangleq q} = p^T q = \sum_i p_i q_i $$

but we know that $p_i \geq 0, q_i = (A^T y)_i \leq 0, \forall i$ by the above. Therefore, $y^T A p \leq 0$, concluding that $\{y : A^T y \leq 0\} = C^*$.

Answer 2

Perhaps another way, $C$ is the set of all linear combinations of columns of $A$ with positive coefficients.