Convex Optimization - Polar Cone

Let S be a non empty set in $mathbb{R}^n$ Then, the polar cone of S denoted by $S^*$ is given by $S^*=left {p in mathbb{R}^n, p^Tx leq 0 : forall x in S ight }$.

Remark

Polar cone is always convex even if S is not convex.

If S is empty set, $S^*=mathbb{R}^n$.

Polarity may be seen as a generapsation of orthogonapty.

Let $Csubseteq mathbb{R}^n$ then the orthogonal space of C, denoted by $C^perp =left { y in mathbb{R}^n:left langle x,y ight angle=0 forall x in C ight }$.

Lemma

Let $S,S_1$ and $S_2$ be non empty sets in $mathbb{R}^n$ then the following statements are true −

$S^*$ is a closed convex cone.

$S subseteq S^{**}$ where $S^{**}$ is a polar cone of $S^*$.

$S_1 subseteq S_2 Rightarrow S_{2}^{*} subseteq S_{1}^{*}$.

Proof

Step 1 − $S^*=left { p in mathbb{R}^n,p^Txleq 0 : forall :x in S ight }$

Let $x_1,x_2 in S^*Rightarrow x_{1}^{T}xleq 0 $ and $x_{2}^{T}x leq 0,forall x in S$

For $lambda in left ( 0, 1 ight ),left [ lambda x_1+left ( 1-lambda ight )x_2 ight ]^Tx=left [ left ( lambda x_1 ight )^T+ left {left ( 1-lambda ight )x_{2} ight }^{T} ight ]x, forall x in S$

$=left [ lambda x_{1}^{T} +left ( 1-lambda ight )x_{2}^{T} ight ]x=lambda x_{1}^{T}x+left ( 1-lambda ight )x_{2}^{T}leq 0$

Thus $lambda x_1+left ( 1-lambda ight )x_{2} in S^*$

Therefore $S^*$ is a convex set.

For $lambda geq 0,p^{T}x leq 0, forall :x in S$

Therefore, $lambda p^T x leq 0,$

$Rightarrow left ( lambda p ight )^T x leq 0$

$Rightarrow lambda p in S^*$

Thus, $S^*$ is a cone.

To show $S^*$ is closed, i.e., to show if $p_n ightarrow p$ as $n ightarrow infty$, then $p in S^*$

$forall x in S, p_{n}^{T}x-p^T x=left ( p_n-p ight )^T x$

As $p_n ightarrow p$ as $n ightarrow infty Rightarrow left ( p_n ightarrow p ight ) ightarrow 0$

Therefore $p_{n}^{T}x ightarrow p^{T}x$. But $p_{n}^{T}x leq 0, : forall x in S$

Thus, $p^Tx leq 0, forall x in S$

$Rightarrow p in S^*$

Hence, $S^*$ is closed.

Step 2 − $S^{**}=left { q in mathbb{R}^n:q^T p leq 0, forall p in S^* ight }$

Let $x in S$, then $ forall p in S^*, p^T x leq 0 Rightarrow x^Tp leq 0 Rightarrow x in S^{**}$

Thus, $S subseteq S^{**}$

Step 3 − $S_2^*=left { p in mathbb{R}^n:p^Txleq 0, forall x in S_2 ight }$

Since $S_1 subseteq S_2 Rightarrow forall x in S_2 Rightarrow forall x in S_1$

Therefore, if $hat{p} in S_2^*, $then $hat{p}^Tx leq 0,forall x in S_2$

$Rightarrow hat{p}^Txleq 0, forall x in S_1$

$Rightarrow hat{p}^T in S_1^*$

$Rightarrow S_2^* subseteq S_1^*$

Theorem

Let C be a non empty closed convex cone, then $C=C^**$

Proof

$C=C^{**}$ by previous lemma.

To prove : $x in C^{**} subseteq C$

Let $x in C^{**}$ and let $x otin C$

Then by fundamental separation theorem, there exists a vector $p eq 0$ and a scalar $alpha$ such that $p^Ty leq alpha, forall y in C$

Therefore, $p^Tx > alpha$

But since $left ( y=0 ight ) in C$ and $p^Tyleq alpha, forall y in C Rightarrow alphageq 0$ and $p^Tx>0$

If $p otin C^*$, then there exists some $ar{y} in C$ such that $p^T ar{y}>0$ and $p^Tleft ( lambda ar{y} ight )$ can be made arbitrarily large by taking $lambda$ sufficiently large.

This contradicts with the fact that $p^Ty leq alpha, forall y in C$

Therefore,$p in C^*$

Since $x in C^*=left { q:q^Tpleq 0, forall p in C^* ight }$

Therefore, $x^Tp leq 0 Rightarrow p^Tx leq 0$

But $p^Tx> alpha$

Thus is contardiction.

Thus, $x in C$

Hence $C=C^{**}$.