6
$\begingroup$

Looking at the example here, I'm trying to understand how the author finds the dual cone $K^*$.

The question asks to find the dual cone of $\{Ax | x \succeq 0\}$ where $A \in \mathbb R^{m\ \mathrm{x}\ n}$.

I know that the dual cone for a cone $K$ is $K^*=\{y|y^Tx\ge0 \ \mathrm{for \ all}\ x \in K\}$. The solution to this question apparently is $K^*=\{y|(A^Ty)^Tx\ge0 \ \mathrm{for \ all}\ x\succeq0 \}$.

I have a series of questions on dual cones I need to answer for homework and I really want to understand how to find dual cones in general. Any help is appreciated.

$\endgroup$

2 Answers 2

7
$\begingroup$

It has been three and a half years since this question was asked. I hope my answer still helps somehow.

By definition, the dual cone of a cone $K$ is:

$$K^* = \{y | x^Ty \ge 0, \forall x \in K\}$$ Denote $Ax \in K$, and directly using the definition, we have:

$$K^* = \{y|(Ax)^Ty, x\succeq 0\} = \{y|(A^Ty)^Tx\ge0, x\succeq0\}$$ Now lets have a close look at the conditions of the set.

For concise, first denote $A^Ty$ as $u$.

For $\forall x\succeq0$, to make $u^Tx \ge 0$, all the components of $u$ must be greater than $0$. If $u_i<0$, you can choose a $x$ looks like $(x_0=0, ..., x_i=1, x_{i+1}=0, ...)$, which makes $u^Tx \lt 0$.

Thus the final form of the dual cone is:

$$K^*=\{y|A^Ty\succeq0\}$$

$\endgroup$
3
$\begingroup$

It follows from the formula $(A^Ty)^Tx=y^T(Ax)$.

I denote $K^{o}=\{\ y|(A^Ty)^Tx\geqslant0\ \forall x\succeq0\ \}$. We want to show that $K^*=K^o$.


$\textbf{First part}$: $K^*\subset K^o$:

If $y$ is in $K^*$, and $x\succeq0$, then $(A^Ty)^Tx=y^T(Ax)\geqslant 0$ since $Ax$ is in $K$. So $y$ is in $K^{o}$.


$\textbf{Second part}$: $K^o\subset K^*$:

Conversely, if $y$ is in $K^o$, and $z\in K$, then there exists $x\succeq0$ such that $z=Ax$. It follows that $y^Tz=y^T(Ax)=(A^Ty)^Tx\geqslant 0$ since $y$ is in $K^o$. So $y$ is in $K^*$.

$\endgroup$
2
  • $\begingroup$ Thank you for your response however given the simplicity of my question, it's clear I'm a novice. Your response is very textbook-esque, which unfortunately is still somewhat unclear to me. Can you walk through your answer in layman's terms so I might have a chance to understand? $\endgroup$
    – strimp099
    Commented Feb 2, 2014 at 17:25
  • 3
    $\begingroup$ Hello. I don't know what details are missing in my proof, sorry. Could you tell me in which part you need more explanations: the formula $(A^Ty)^x=y^t(Ax)$ ? the inclusion $K^*\subset K^o$ ? The inclusion $K^o\subset K^*$ ? Edit: I initially used the notation $K^\vee$ for the dual cone, instead of $K^*$, since it is the notation I am used to. Was it where you had a problem in my proof? I edited it. $\endgroup$
    – Taladris
    Commented Feb 2, 2014 at 23:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .