1
$\begingroup$

Given a closed convex cone $D$ in $\mathbb{R}^{n}$, the cone $K_{2} \in \mathbb{R}^{m}$ is defined by $$ K_{2} = \{ y = (y^{1}, y^{2}, \cdots , y^{m}): y^{i} \in \mathbb{R}^{n},\, i= 1, \cdots , m, \, y^{1} + y^{2} + \cdots + y^{m} \in D \} $$

I need to describe its polar cone $K_{2}^{\circ}$.

Recall that for a given cone $C$, its polar cone $C^{\circ}$ is defined to be the set of all $x$ such that $\langle x,y \rangle \leq 0$ for all $y \in C$.

So, if $y \in K_{2}$, then $$ y = \begin{pmatrix} y^{1}, & y^{2},& \cdots, & y^{m}\end{pmatrix} \\ = \begin{pmatrix}\begin{pmatrix} y_{1}^{1} & y_{2}^{1} & \cdots y_{n}^{1} \end{pmatrix}, \begin{pmatrix} y_{1}^{2} & y_{2}^{2} & \cdots y_{n}^{2} \end{pmatrix},\cdots ,\begin{pmatrix} y_{1}^{m} & y_{2}^{m} & \cdots y_{n}^{m} \end{pmatrix} \end{pmatrix}.$$

So, I need to find the set of all $x$ such that when I take the inner product of $x$ and $y$, I get a value $\leq 0$.

My first problem is that I'm not sure if I have even expressed a general set in $K_{2}$ correctly here. Secondly, I would think that perhaps I should take the inner product of a general $y$ with a general $x$, set the result $\leq 0$ and then try to solve for what the components of $x$ are, but as I am not sure even what a general $x$ should look like, I am at a loss as to how this should be done.

If this is not the correct approach to finding the polar of this cone, what is the correct approach? Beyond the inner product definition of a polar cone (which in terms of angles between things, means that $x$ and $y$ make an obtuse angle with each other), I don't know much about how to go about finding them.

I sincerely thank you for your time and patience!

$\endgroup$
  • $\begingroup$ I am more used to the terminology 'dual cone'. $\endgroup$ – copper.hat Oct 1 '17 at 7:17
  • $\begingroup$ @copper.hat that's not the same thing. The dual cone is the orthogonal complement of the polar cone. $\endgroup$ – ALannister Oct 1 '17 at 17:32
  • $\begingroup$ The dual cone is the negative of the polar cone. $\endgroup$ – copper.hat Oct 1 '17 at 18:12
  • $\begingroup$ @copper.hat correct. $\endgroup$ – ALannister Oct 1 '17 at 18:15
1
$\begingroup$

Here's an initial observation, but not a full solution. Changing notation slightly, $$K_2 = \{ Y = \begin{bmatrix} y_1 & \cdots & y_m \end{bmatrix} \in \mathbb R^{n \times m} \mid y_1 + \cdots + y_m \in D \}.$$ (Here $y_i$ is the $i$th column of the matrix $Y$.) A matrix $X \in \mathbb R^{m \times n}$ belongs to $K_2^\circ$ if and only if $$\langle X, Y \rangle = \text{tr}(Y X^T) = \text{tr}(y_1 x_1^T + \cdots + y_m x_m^T) \leq 0 \text{ for all } Y \in K_2.$$ If $x_1 = \cdots = x_m = x \in D^\circ$, then $$\langle X, Y \rangle = \text{tr}( (y_1+\cdots+y_m)^T x) = x^T(y_1 + \cdots + y_m) \leq 0, $$ so $X \in K_2^\circ$. This shows that $S = \{ \begin{bmatrix} x & \cdots & x \end{bmatrix} \mid x \in D^\circ\} \subset K_2^\circ$.

We can conjecture that in fact $S = K_2^\circ$. We still need to show containment in the other direction.

By the way, sometimes once you have guessed what the polar cone is, it turns out to be easier to show that $S^\circ = K_2$. If it can be shown that $S^\circ = K_2$, which I suspect is straightforward, it will follow that $S = K_2^\circ$.


Let's attempt to show that $S^\circ \subset K_2$. So, suppose that $Y \in S^\circ$. From the definition of $S^\circ$, we have that $\langle Y, X \rangle \leq 0$ for all $X \in S$. Using the definition of $S$, we see that $$ \tag{1}\langle Y, \begin{bmatrix} x & \cdots x \end{bmatrix} \rangle \leq 0 $$ for all $x \in \mathbb R^n$. We have hoping to conclude that $Y \in K_2$. In other words, we are hoping to conclude that the columns of $Y$ sum to $0$. Does this follow somehow from the fact that the inequality (1) holds for all $x \in \mathbb R^n$?

$\endgroup$
  • $\begingroup$ so it IS a matrix? I wasn't even sure what sets in $K_{1}$ were supposed to look like. $\endgroup$ – ALannister Sep 29 '17 at 0:11
  • $\begingroup$ I think that we should view $K_2$ as being a subset of $\mathbb R^{n \times m}$, and so $K_2^\circ$ is also a subset of $\mathbb R^{n \times m}$. $\endgroup$ – littleO Sep 29 '17 at 0:12
  • $\begingroup$ By the way, I'm assuming familiarity with the Frobenius inner product on $\mathbb R^{n \times m}$ defined by $\langle A, B \rangle = \text{tr}(A^T B) = \text{tr}(B^T A)$. Note that $\text{tr}(A^T B) = \text{tr}(B A^T)$ for all $A, B$. $\endgroup$ – littleO Sep 29 '17 at 0:16
  • $\begingroup$ I've seen that defined in my text. One more thing, why did you think $x_{1}=\cdots = x_{m} = x $ would do the job? And how did you know that $x \in D^{\circ}$ even? $\endgroup$ – ALannister Sep 29 '17 at 0:22
  • 1
    $\begingroup$ At this point, I think you are done. That's the answer. The polar of $K_2$ has now been expressed in terms of the polar of $D$. But notice that $A^T \lambda$ is the vector that you get by stacking $m$ copies of $\lambda$. It's interesting to see that this description of $K_2^\circ$ is consistent with the conjecture we made in the earlier approach that we took to this problem. $\endgroup$ – littleO Sep 29 '17 at 19:35
0
$\begingroup$

The result follows from mostly formal cone calculations.

It is straightforward to show that if $K$ is a cone and $L$ a linear operator then $(LK)^\circ = (L^T)^{-1} K^\circ$.

Let $A= \begin{bmatrix} I \cdots I \end{bmatrix}$, then $K_2 = A^{-1} D$. Note that this is the inverse in a set valued sense, $A$ is not injective.

Note that this gives $A^{-1} D = \ker A + A^\dagger D $, where $A^\dagger$ is the pseudo inverse of $A$.

Also note that $(\ker A)^\circ = {\cal R} A^T $ since $\ker A$ is a subspace.

Note that $A^\dagger y = {1 \over n} A^Ty$, and so $A^\dagger D = A^T D$.

If $A,B$ are closed convex cones then $(A+B)^\circ = A^\circ \cap B^\circ$.

Hence $K_2^\circ = (\ker A)^\circ \cap (A^T D)^\circ = {\cal R} A^T \cap (A^T D)^\circ = {\cal R} A^T \cap A^{-1} D^\circ$.

Noting that ${\cal R} A^T = \{ (y,\cdots, y) \}_{y \in \mathbb{R}^n}$, we see that $K_2^\circ = \{ (y,\cdots, y) | y \in D^\circ \} = A^T D^\circ$.

$\endgroup$
  • $\begingroup$ Is there a standard name for the fact that $(LK)^\circ = (L^T)^{-1} K^\circ$? I know it's related to Farkas' lemma. $\endgroup$ – littleO Sep 30 '17 at 23:02
  • $\begingroup$ I'm not aware of a name. The result follows from Formal manipulations, Farka's lemma is a much stronger result. $\endgroup$ – copper.hat Sep 30 '17 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.