9.5. Cones II

9.5.1. Dual Cones

Dual cones are defined for finite dimensional inner product spaces. Dual cones technically belong to the dual space ${\mathbb{V}}^{\ast }$.

Recall that the dual space ${\mathbb{V}}^{\ast }$ of a vector space $\mathbb{V}$ is the set of all linear functionals on $\mathbb{V}$. For finite dimensional spaces, $\mathbb{V}$ and its dual ${\mathbb{V}}^{\ast }$ are isomorphic. For an inner product space $\mathbb{V}$ every linear functional in ${\mathbb{V}}^{\ast }$ can be identified with a vector $\mathbf{v}\in \mathbb{V}$ by the functional $⟨\cdot ,\mathbf{v}⟩$ (Theorem 4.106).

Definition 9.32 (Dual cone)

Let $\mathbb{V}$ be a finite dimensional inner product space and ${\mathbb{V}}^{\ast }$ be its dual space.

Let $C\subset \mathbb{V}$. The set

$$C^{\ast }\triangleq \{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C\}$$

is called the dual cone of $C$ in ${\mathbb{V}}^{\ast }$.

In the Euclidean space ${\mathbb{R}}^n$, the dual cone can be written as:

$$C^{\ast }\triangleq \{\mathbf{y}\in {\mathbb{R}}^n|⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C\}.$$

Geometric interpretation

• For a vector $\mathbf{y}$, the set $H_{\mathbf{y},+}\{\mathbf{x}|⟨\mathbf{x},\mathbf{y}⟩\ge 0\}$ is a halfspace passing through origin.

• $\mathbf{y}$ is the normal vector of the halfspace along (in the direction of) the halfspace.

• If $\mathbf{y}$ belongs to the dual cone of $C$, then for every $\mathbf{x}\in C$, we have $⟨\mathbf{x},\mathbf{y}⟩\ge 0$.

• Thus, the set $C$ is contained in the halfspace $H_{\mathbf{y},+}$.

• In particular, if $C$ is a cone, then it will also touch the boundary of the half space $H_{\mathbf{y},+}$ as $C$ contains the origin.

9.5.1.1. Properties

Property 9.16

Dual cone is a cone.

Proof. Let $\mathbf{y}\in C^{\ast }$. Then, by definition,

$$⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C.$$

Thus, for some $\alpha \ge 0$,

$$⟨\mathbf{x},\alpha \mathbf{y}⟩=\alpha ⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C.$$

Thus, for every $\mathbf{y}\in C^{\ast }$, $\alpha \mathbf{y}\in C^{\ast }$ for all $\alpha \ge 0$. Thus, $C^{\ast }$ is a cone.

Property 9.17

Dual cone is convex.

Proof. Let ${\mathbf{y}}_1,{\mathbf{y}}_2\in C^{\ast }$. Let $t\in [0,1]$ and

$$\mathbf{y}=t{\mathbf{y}}_1+(1-t){\mathbf{y}}_2.$$

Then for an arbitrary $\mathbf{x}\in C$,

$$⟨\mathbf{x},\mathbf{y}⟩=⟨\mathbf{x},t{\mathbf{y}}_1+(1-t){\mathbf{y}}_2⟩=t⟨\mathbf{x},{\mathbf{y}}_1⟩+(1-t)⟨\mathbf{x},{\mathbf{y}}_2⟩\ge 0.$$

Thus, $\mathbf{y}\in C^{\ast }$. Thus, $C^{\ast }$ is convex.

We note that dual cone is a convex cone even if the original set $C$ is neither convex nor a cone.

Property 9.18 (Containment reversal in dual cone)

Let $C_1$ and $C_2$ be two subsets of $\mathbb{V}$ and let $C_1^{\ast }$ and $C_2^{\ast }$ be their corresponding dual cones. Then,

$$C_1\subseteq C_2⟹C_2^{\ast }\subseteq C_1^{\ast }.$$

The dual cone of the subset contains the dual cone of the superset.

Proof. Let $\mathbf{y}\in C_2^{\ast }$. Then

$$⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C_2⟹⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C_1⟹\mathbf{y}\in C_1^{\ast }.$$

Thus, $C_2^{\ast }\subseteq C_1^{\ast }$.

Property 9.19 (Closedness)

A dual cone is a closed set.

Proof. The dual cone of a set $C$ is given by

$$C^{\ast }=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\ge 0\mathrm{\forall }\mathbf{x}\in C\}$$

Fix a $\mathbf{x}\in C$ and consider the set

$$H_{\mathbf{x}}=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\ge 0\}.$$

The set $H_{\mathbf{x}}$ is a closed half space.

We can now see that

$$C^{\ast }=\bigcap _{\mathbf{x}\in C}{H}_{\mathbf{x}}.$$

Thus, $C^{\ast }$ is an intersection of closed half spaces. An arbitrary intersection of closed sets is closed. Hence $C^{\ast }$ is closed.

Property 9.20 (Interior of dual cone)

The interior of the dual cone $C^{\ast }$ is given by

$$\mathrm{int}{C}^{\ast }=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩>0\mathrm{\forall }\mathbf{x}\in C\setminus \{\mathbf{0}\}\}.$$

Proof. Let

$$A=\{\mathbf{y}|⟨\mathbf{x},\mathbf{y}⟩>0\mathrm{\forall }\mathbf{x}\in C\setminus \{\mathbf{0}\}\}.$$

Let $\mathbf{y}\in A$. By definition $\mathbf{y}\in C^{\ast }$; i.e., $A\subseteq C^{\ast }$.

Since $⟨\mathbf{x},\mathbf{y}⟩>0$ for every nonzero $\mathbf{x}\in C$, hence $⟨\mathbf{x},\mathbf{y}+\mathbf{u}⟩>0$ for every nonzero $\mathbf{x}\in C$ and every sufficiently small $\mathbf{u}$. Hence, $\mathbf{y}\in \mathrm{int}{C}^{\ast }$. We have shown that $A\subseteq \mathrm{int}{C}^{\ast }$.

Now, let $\mathbf{y}\notin A$ but $\mathbf{y}\in C^{\ast }$. Then, $⟨\mathbf{x},\mathbf{y}⟩=0$ for some nonzero $\mathbf{x}\in C$. But then

$$⟨\mathbf{x},\mathbf{y}-t\mathbf{x}⟩=⟨\mathbf{x},\mathbf{y}⟩-t⟨\mathbf{x},\mathbf{x}⟩<0$$

for all $t>0$. Thus, $\mathbf{y}\notin \mathrm{int}{C}^{\ast }$.

Hence, $A=\mathrm{int}{C}^{\ast }$.

Property 9.21 (Non-empty interior implies pointed dual cone)

If $C$ has a non-empty interior, then its dual cone $C^{\ast }$ is pointed.

Proof. Let $C$ have a non-empty interior and assume that its dual cone $C^{\ast }$ is not pointed. Then, there exists a non-zero $\mathbf{y}\in C^{\ast }$ such that $-\mathbf{y}\in C^{\ast }$ holds too.

Thus, $⟨\mathbf{x},\mathbf{y}⟩\ge 0$ as well as $⟨\mathbf{x},-\mathbf{y}⟩\ge 0$ for every $\mathbf{x}\in C$, i.e, $⟨\mathbf{x},\mathbf{y}⟩=0$ for every $\mathbf{x}\in C$. But this means that $C$ lies in a hyperplane $H_{\mathbf{y},0}$ and hence has an empty interior. A contradiction.

Theorem 9.60 (Dual cone of a subspace)

The dual cone of a subspace $V\subseteq \mathbb{V}$ is its orthogonal complement $V^{\perp }$ defined as:

$$V^{\perp }=\{\mathbf{y}|⟨\mathbf{v},\mathbf{y}⟩=0\mathrm{\forall }\mathbf{v}\in V\}.$$

More precisely, $V^{\ast }$ is isomorphic to $V^{\perp }$ as the dual cone is a subset of ${\mathbb{V}}^{\ast }$.

Proof. Let $V^{\ast }$ be the dual cone of $V$. If $\mathbf{v}\in V^{\perp }$, then by definition, $\mathbf{v}\in V^{\ast }$. Thus, $V^{\perp }\subseteq V^{\ast }$.

Let us now assume that there is a vector $\mathbf{y}\in V^{\ast }$ s.t. $\mathbf{y}\notin V^{\perp }$.

Then, there exists $\mathbf{v}\in V$ such that $⟨\mathbf{v},\mathbf{y}⟩>0$. Since $V$ is a subspace, it follows that $-\mathbf{v}\in V$. But then

$$⟨-\mathbf{v},\mathbf{y}⟩=-⟨\mathbf{v},\mathbf{y}⟩<0.$$

Thus, $\mathbf{y}$ cannot belong to $V^{\ast }$. A contradiction.

Thus, $V^{\ast }=V^{\perp }$.

9.5.1.2. Self Dual Cones

Definition 9.33 (Self dual cone)

A cone $C$ is called self dual if $C^{\ast }=C$, i.e., it is its own dual cone.

By equality, we mean that the dual cone $C^{\ast }$ is isomorphic to $C$ since technically $C^{\ast }\subseteq {\mathbb{V}}^{\ast }$.

Example 9.15 (Nonnegative orthant)

The non-negative orthant ${\mathbb{R}}_{+}^n$ is self dual.

Let $C={\mathbb{R}}_{+}^n$. For some $\mathbf{u},\mathbf{v}\in C$, $⟨\mathbf{u},\mathbf{v}⟩\ge 0$. Thus, ${\mathbb{R}}_{+}^n\subseteq C^{\ast }$.

Now, for some $\mathbf{v}\notin {\mathbb{R}}_{+}^n$, there is at least one component which is negative. Without loss of generality, assume that the first component $v_1<0$.

Now consider the vector $\mathbf{u}=[1,0,\dots ,0]\in {\mathbb{R}}_{+}^n$. $⟨\mathbf{v},\mathbf{u}⟩<0$. Thus, $\mathbf{v}\notin C^{\ast }$.

Thus, $C^{\ast }={\mathbb{R}}_{+}^n$. It is self dual.

Example 9.16 (Positive semidefinite cone)

The positive semi-definite cone ${\mathbb{S}}_{+}^n$ is self dual.

Let $C={\mathbb{S}}_{+}^n$ and $\mathbf{Y}\in C$. We first show that $\mathbf{Y}\in C^{\ast }$.

Choose an arbitrary $\mathbf{X}\in C$.
Express $\mathbf{X}$ in terms of its eigenvalue decomposition as

$$\mathbf{X}=\sum {\lambda }_i{\mathbf{q}}_i{\mathbf{q}}_i^T.$$

Since $\mathbf{X}$ is PSD, hence, ${\lambda }_i\ge 0$.

Then,

$$\begin{array}{r}\begin{array}{rl}⟨\mathbf{Y},\mathbf{X}⟩& =\mathrm{tr}(\mathbf{X}\mathbf{Y})=\mathrm{tr}(\mathbf{Y}\mathbf{X})\\ & =\mathrm{tr}(\mathbf{Y}\sum {\lambda }_i{\mathbf{q}}_i{\mathbf{q}}_i^T)\\ & =\sum {\lambda }_i\mathrm{tr}\left(\mathbf{Y}{\mathbf{q}}_i{\mathbf{q}}_i^T\right)\\ & =\sum {\lambda }_i\mathrm{tr}\left({\mathbf{q}}_i^T\mathbf{Y}{\mathbf{q}}_i\right)\\ & =\sum {\lambda }_i({\mathbf{q}}_i^T\mathbf{Y}{\mathbf{q}}_i).\end{array}\end{array}$$

But since $\mathbf{Y}$ is PSD, hence ${\mathbf{q}}_i^T\mathbf{Y}{\mathbf{q}}_i\ge 0$. Hence $⟨\mathbf{Y},\mathbf{X}⟩\ge 0$. Thus, $\mathbf{Y}\in C^{\ast }$.

Now, suppose $\mathbf{Y}\notin {\mathbb{S}}_{+}^n$. Then there exists a vector $\mathbf{v}\in {\mathbb{R}}^n$ such that ${\mathbf{v}}^T\mathbf{Y}\mathbf{v}<0$. Consider the PSD matrix $\mathbf{V}=\mathbf{v}{\mathbf{v}}^T$.

$$⟨\mathbf{Y},\mathbf{V}⟩=\mathrm{tr}(\mathbf{V}\mathbf{Y})=\mathrm{tr}(\mathbf{v}{\mathbf{v}}^T\mathbf{Y})=\mathrm{tr}({\mathbf{v}}^T\mathbf{Y}\mathbf{v})<0.$$

Thus, $\mathbf{Y}\notin C^{\ast }$.

This completes the proof that $C^{\ast }=C={\mathbb{S}}_{+}^n$, i.e., the positive semi-definite cone is self dual.

9.5.2. Polar Cones

Definition 9.34 (Polar cone)

Let $\mathbb{V}$ be a finite dimensional inner product space and ${\mathbb{V}}^{\ast }$ be its dual space.

Let $C\subseteq \mathbb{V}$. Then, its polar cone $C^{\circ }$ is defined as

$$C^{\circ }\triangleq \{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{x}\in C\}.$$

We note that polar cones are just the negative of dual cones. Thus, they exhibit similar properties as dual cones.

Example 9.17 (Polar cone of a ray)

Let $\mathbf{x}$ be a given nonzero vector. Let

$$C=\mathrm{cone}\{\mathbf{x}\}=\{t\mathbf{x}|t\ge 0\}.$$

1. Let $\mathbf{y}\in C^{\circ }$.

2. Then for every $t\ge 0$, we have $⟨t\mathbf{x},\mathbf{y}⟩\le 0$.

3. Equivalently, $⟨\mathbf{x},\mathbf{y}⟩\le 0$ since $t\ge 0$.

4. Hence

   $$C^{\circ }=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\le 0\}.$$

5. Also note that $C$ is closed and convex.

6. We shall show later in polar cone theorem that

   $$(C^{\circ }{)}^{\circ }=C.$$

7. Hence the polar cone of the set

   $$\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\le 0\}$$

   is $\mathrm{cone}\{\mathbf{x}\}$.

9.5.2.1. Properties

Property 9.22

Polar cone is a cone.

Proof. Let $\mathbf{y}\in C^{\circ }$. Then, by definition,

$$⟨\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{x}\in C.$$

Thus, for some $\alpha \ge 0$,

$$⟨\mathbf{x},\alpha \mathbf{y}⟩=\alpha ⟨\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{x}\in C.$$

Thus, for every $\mathbf{y}\in C^{\circ }$, $\alpha \mathbf{y}\in C^{\circ }$ for all $\alpha \ge 0$. Thus, $C^{\circ }$ is a cone.

Property 9.23

Polar cone is convex.

Proof. Let ${\mathbf{y}}_1,{\mathbf{y}}_2\in C^{\circ }$. Let $t\in [0,1]$ and

$$\mathbf{y}=t{\mathbf{y}}_1+(1-t){\mathbf{y}}_2.$$

Then for an arbitrary $\mathbf{x}\in C$,

$$⟨\mathbf{x},\mathbf{y}⟩=⟨\mathbf{x},t{\mathbf{y}}_1+(1-t){\mathbf{y}}_2⟩=t⟨\mathbf{x},{\mathbf{y}}_1⟩+(1-t)⟨\mathbf{x},{\mathbf{y}}_2⟩\le 0.$$

Thus, $\mathbf{y}\in C^{\circ }$. Thus, $C^{\circ }$ is convex.

We note that polar cone is a convex cone even if the original set $C$ is neither convex nor a cone.

Property 9.24 (Containment reversal in polar cone)

Let $C_1$ and $C_2$ be two subsets of $\mathbb{V}$ and let $C_1^{\circ }$ and $C_2^{\circ }$ be their corresponding polar cones. Then,

$$C_1\subseteq C_2⟹C_2^{\circ }\subseteq C_1^{\circ }.$$

The polar cone of the subset contains the polar cone of the superset.

Proof. Let $\mathbf{y}\in C_2^{\circ }$. Then

$$⟨\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{x}\in C_2⟹⟨\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{x}\in C_1⟹\mathbf{y}\in C_1^{\circ }.$$

Thus, $C_2^{\circ }\subseteq C_1^{\circ }$.

Property 9.25 (Closedness)

A polar cone is a closed set.

Proof. The polar cone of a set $C$ is given by

$$C^{\circ }=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{x}\in C\}$$

Fix a $\mathbf{x}\in C$ and consider the set

$$H_{\mathbf{x}}=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩\le 0\}.$$

The set $H_{\mathbf{x}}$ is a closed half space.

We can now see that

$$C^{\circ }=\bigcap _{\mathbf{x}\in C}{H}_{\mathbf{x}}.$$

Thus, $C^{\circ }$ is an intersection of closed half spaces. An arbitrary intersection of closed sets is closed. Hence $C^{\circ }$ is closed.

Property 9.26 (Interior of polar cone)

The interior of the polar cone $C^{\circ }$ is given by

$$\mathrm{int}{C}^{\circ }=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x},\mathbf{y}⟩<0\mathrm{\forall }\mathbf{x}\in C\setminus \{\mathbf{0}\}\}.$$

Proof. Let

$$A=\{\mathbf{y}|⟨\mathbf{x},\mathbf{y}⟩<0\mathrm{\forall }\mathbf{x}\in C\setminus \{\mathbf{0}\}\}.$$

Let $\mathbf{y}\in A$. By definition $\mathbf{y}\in C^{\circ }$; i.e., $A\subseteq C^{\circ }$.

Since $⟨\mathbf{x},\mathbf{y}⟩<0$ for every nonzero $\mathbf{x}\in C$, hence $⟨\mathbf{x},\mathbf{y}+\mathbf{u}⟩<0$ for every $\mathbf{x}\in C$ and every sufficiently small $\mathbf{u}$. Hence, $\mathbf{y}\in \mathrm{int}{C}^{\circ }$. We have shown that $A\subseteq \mathrm{int}{C}^{\circ }$.

Now, let $\mathbf{y}\notin A$ but $\mathbf{y}\in C^{\circ }$. Then, $⟨\mathbf{x},\mathbf{y}⟩=0$ for some nonzero $\mathbf{x}\in C$. But then

$$⟨\mathbf{x},\mathbf{y}-t\mathbf{x}⟩=⟨\mathbf{x},\mathbf{y}⟩-t⟨\mathbf{x},\mathbf{x}⟩>0$$

for all $t<0$. Thus, $\mathbf{y}\notin \mathrm{int}{C}^{\circ }$.

Hence, $A=\mathrm{int}{C}^{\circ }$.

Property 9.27 (Non-empty interior implies pointed polar cone)

If $C$ has a non-empty interior, then its polar cone $C^{\circ }$ is pointed.

Proof. Let $C$ have a non-empty interior and assume that its polar cone $C^{\circ }$ is not pointed. Then, there exists a non-zero $\mathbf{y}\in C^{\circ }$ such that $-\mathbf{y}\in C^{\circ }$ holds too.

Thus, $⟨\mathbf{x},\mathbf{y}⟩\le 0$ as well as $⟨\mathbf{x},-\mathbf{y}⟩\le 0$ for every $\mathbf{x}\in C$, i.e, $⟨\mathbf{x},\mathbf{y}⟩=0$ for every $\mathbf{x}\in C$. But this means that $C$ lies in a hyperplane $H_{\mathbf{y},0}$ and hence has an empty interior. A contradiction.

Theorem 9.61 (Polar cone of a subspace)

The polar cone of a subspace $V\subseteq \mathbb{V}$ is its orthogonal complement $V^{\perp }$ defined as:

$$V^{\perp }=\{\mathbf{y}|⟨\mathbf{v},\mathbf{y}⟩=0\mathrm{\forall }\mathbf{v}\in V\}.$$

More precisely, $V^{\circ }$ is isomorphic to $V^{\perp }$ as the polar cone is a subset of ${\mathbb{V}}^{\ast }$.

Proof. Let $V^{\circ }$ be the polar cone of $V$. If $\mathbf{v}\in V^{\perp }$, then by definition, $\mathbf{v}\in V^{\circ }$. Thus, $V^{\perp }\subseteq V^{\circ }$.

Let us now assume that there is a vector $\mathbf{y}\in V^{\circ }$ s.t. $\mathbf{y}\notin V^{\perp }$.

Then, there exists $\mathbf{v}\in V$ such that $⟨\mathbf{v},\mathbf{y}⟩<0$. Since $V$ is a subspace, it follows that $-\mathbf{v}\in V$. But then

$$⟨-\mathbf{v},\mathbf{y}⟩=-⟨\mathbf{v},\mathbf{y}⟩>0.$$

Thus, $\mathbf{y}$ cannot belong to $V^{\circ }$. A contradiction.

Thus, $V^{\circ }=V^{\perp }$.

Example 9.18 (Polar cone of a null space)

Let $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ and $C=\mathrm{null}\mathbf{A}$.

1. Recall from linear algebra that

   $$(\mathrm{null}\mathbf{A}{)}^{\perp }=\mathrm{range}{\mathbf{A}}^T.$$

2. Hence by Theorem 9.61,

   $$C^{\circ }=C^{\perp }=\mathrm{range}{\mathbf{A}}^T.$$

We can verify this result easily.

1. Let $\mathbf{v}\in \mathrm{range}{\mathbf{A}}^T$.

2. Then there exists $\mathbf{u}\in {\mathbb{R}}^m$ such that $\mathbf{v}={\mathbf{A}}^T\mathbf{u}$.

3. For every $\mathbf{x}\in \mathrm{null}\mathbf{A}$, we have $\mathbf{A}\mathbf{x}=\mathbf{0}$.

4. Hence

   $$⟨\mathbf{x},\mathbf{v}⟩=⟨\mathbf{x},{\mathbf{A}}^T\mathbf{u}⟩=⟨\mathbf{A}\mathbf{x},\mathbf{u}⟩=\mathbf{0}.$$

5. Hence $\mathbf{v}\in (\mathrm{null}\mathbf{A}{)}^{\circ }$.

Property 9.28 (Polar cone and closure)

For any nonempty set $C$, we have

$$C^{\circ }=(\mathrm{cl}C{)}^{\circ }.$$

Proof. We first show that $(\mathrm{cl}C{)}^{\circ }\subseteq C^{\circ }$.

1. We have $C\subseteq \mathrm{cl}C$.

2. Hence by Property 9.24,

   $$(\mathrm{cl}C{)}^{\circ }\subseteq C^{\circ }.$$

We now show that $C^{\circ }\subseteq (\mathrm{cl}C{)}^{\circ }$.

1. Let $\mathbf{y}\in C^{\circ }$.

2. Then for every $\mathbf{x}\in C$, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

3. Let $\mathbf{x}\in \mathrm{cl}C$.

4. There exists a sequence $\{{\mathbf{x}}_k\}$ of $C$ such that $lim{\mathbf{x}}_k=\mathbf{x}$.

5. But $⟨{\mathbf{x}}_k,\mathbf{y}⟩\le 0$ for every $k$.

6. Hence, taking the limit, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

7. Hence for every $\mathbf{x}\in \mathrm{cl}C$, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

8. Hence $\mathbf{y}\in (\mathrm{cl}C{)}^{\circ }$.

9. Hence $C^{\circ }\subseteq (\mathrm{cl}C{)}^{\circ }$.

Property 9.29 (Polar cone and convex hull)

For any nonempty set $C$, we have

$$C^{\circ }=(\mathrm{conv}C{)}^{\circ }.$$

Proof. We first show that $(\mathrm{conv}C{)}^{\circ }\subseteq C^{\circ }$.

1. We have $C\subseteq \mathrm{conv}C$.

2. Hence by Property 9.24,

   $$(\mathrm{conv}C{)}^{\circ }\subseteq C^{\circ }.$$

We now show that $C^{\circ }\subseteq (\mathrm{conv}C{)}^{\circ }$.

1. Let $\mathbf{y}\in C^{\circ }$.

2. Then for every $\mathbf{x}\in C$, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

3. Let $\mathbf{x}\in \mathrm{conv}C$.

4. Then there exist ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\in C$ and $t_1,\dots t_k\ge 0$ with $t_1+\cdots +t_k=1$ such that

   $$\mathbf{x}=\sum _{i=1}^k{t}_i{\mathbf{x}}_i.$$

5. Then

   $$⟨\mathbf{x},\mathbf{y}⟩=\sum _{i=1}^k{t}_i⟨{\mathbf{x}}_i,\mathbf{y}⟩.$$

6. But $⟨{\mathbf{x}}_i,\mathbf{y}⟩\le 0$ since ${\mathbf{x}}_i\in C$ for every $i$.

7. Hence $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

8. Hence for every $\mathbf{x}\in \mathrm{conv}C$, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

9. Hence $\mathbf{y}\in (\mathrm{conv}C{)}^{\circ }$.

10. Hence $C^{\circ }\subseteq (\mathrm{conv}C{)}^{\circ }$.

Property 9.30 (Polar cone and conic hull)

For any nonempty set $C$, we have

$$C^{\circ }=(\mathrm{cone}C{)}^{\circ }.$$

Proof. We first show that $(\mathrm{cone}C{)}^{\circ }\subseteq C^{\circ }$.

1. We have $C\subseteq \mathrm{cone}C$.

2. Hence by Property 9.24,

   $$(\mathrm{cone}C{)}^{\circ }\subseteq C^{\circ }.$$

We now show that $C^{\circ }\subseteq (\mathrm{cone}C{)}^{\circ }$.

1. Let $\mathbf{y}\in C^{\circ }$.

2. Then for every $\mathbf{x}\in C$, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

3. Let $\mathbf{x}\in \mathrm{cone}C$.

4. Then there exist ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\in C$ and $t_1,\dots t_k\ge 0$ such that

   $$\mathbf{x}=\sum _{i=1}^k{t}_i{\mathbf{x}}_i.$$

5. Then

   $$⟨\mathbf{x},\mathbf{y}⟩=\sum _{i=1}^k{t}_i⟨{\mathbf{x}}_i,\mathbf{y}⟩.$$

6. But $⟨{\mathbf{x}}_i,\mathbf{y}⟩\le 0$ since ${\mathbf{x}}_i\in C$ for every $i$.

7. Hence $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

8. Hence for every $\mathbf{x}\in \mathrm{cone}C$, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$.

9. Hence $\mathbf{y}\in (\mathrm{cone}C{)}^{\circ }$.

10. Hence $C^{\circ }\subseteq (\mathrm{cone}C{)}^{\circ }$.

Theorem 9.62 (Polar cone theorem)

For any nonempty cone $C$, we have

$$(C^{\circ }{)}^{\circ }=\mathrm{cl}\mathrm{conv}C.$$

In particular, if $C$ is closed and convex, we have

$$(C^{\circ }{)}^{\circ }=C.$$

Proof. First we assume that $C$ is nonempty, closed and convex and show that $(C^{\circ }{)}^{\circ }=C$.

1. Pick any $\mathbf{x}\in C$.

2. By definition, we have $⟨\mathbf{x},\mathbf{y}⟩\le 0$ for every $\mathbf{y}\in C^{\circ }$.

3. Hence $\mathbf{x}\in (C^{\circ }{)}^{\circ }$.

4. Hence $C\subseteq (C^{\circ }{)}^{\circ }$.

5. Now choose any $\mathbf{z}\in (C^{\circ }{)}^{\circ }$.

6. Since $C$ is nonempty, closed and convex, hence by projection theorem (Theorem 10.7), there exists a unique projection of $\mathbf{z}$ on $C$, denoted by $\hat{\mathbf{z}}$ that satisfies

   $$⟨\mathbf{x}-\hat{\mathbf{z}},\mathbf{z}-\hat{\mathbf{z}}⟩\le 0\mathrm{\forall }\mathbf{x}\in C.$$

7. Since $C$ is a cone, hence $\mathbf{0}\in C$.

8. Since $C$ is a cone and $\hat{\mathbf{z}}\in C$, hence $2\hat{\mathbf{z}}\in C$.

9. By putting $\mathbf{x}=\mathbf{0}$, we get

   $$⟨\hat{\mathbf{z}},\mathbf{z}-\hat{\mathbf{z}}⟩\ge 0.$$

10. By putting $\mathbf{x}=2\hat{\mathbf{z}}$, we get

    $$⟨\hat{\mathbf{z}},\mathbf{z}-\hat{\mathbf{z}}⟩\le 0.$$

11. Together, we have

    $$⟨\hat{\mathbf{z}},\mathbf{z}-\hat{\mathbf{z}}⟩=0.$$

12. Putting this back into the projection inequality, we get

    $$⟨\mathbf{x},\mathbf{z}-\hat{\mathbf{z}}⟩\le 0\mathrm{\forall }\mathbf{x}\in C.$$

13. Hence $\mathbf{z}-\hat{\mathbf{z}}\in C^{\circ }$.

14. Since $\mathbf{z}\in (C^{\circ }{)}^{\circ }$, hence $⟨\mathbf{z},\mathbf{z}-\hat{\mathbf{z}}⟨\le 0$.

15. We also have $-⟨\hat{\mathbf{z}},\mathbf{z}-\hat{\mathbf{z}}⟩=0$.

16. Adding these two, we get

    $$⟨\mathbf{z}-\hat{\mathbf{z}},\mathbf{z}-\hat{\mathbf{z}}⟩\le 0.$$

17. This means that

    $$\Vert \mathbf{z}-\hat{\mathbf{z}}{\Vert }_2^2\le 0.$$

18. It follows that $\mathbf{z}=\hat{\mathbf{z}}$.

19. Hence $\mathbf{z}\in C$.

20. Hence $(C^{\circ }{)}^{\circ }\subseteq C$.

We have so far shown that if $C$ is a nonempty, closed and convex cone then

$$C=(C^{\circ }{)}^{\circ }.$$

Now consider the case where $C$ is just an arbitrary nonempty cone.

1. Then $\mathrm{cl}\mathrm{conv}C$ is a closed convex cone.

2. By previous argument

   $$\mathrm{cl}\mathrm{conv}C=(\mathrm{cl}\mathrm{conv}C{)}^{\circ }{)}^{\circ }.$$

3. But

   $$(\mathrm{cl}\mathrm{conv}C{)}^{\circ }=(\mathrm{conv}C{)}^{\circ }=C^{\circ }.$$

4. Hence

   $$\mathrm{cl}\mathrm{conv}C=(C^{\circ }{)}^{\circ }.$$

9.5.3. Normal Cones

Definition 9.35 (Normal vector)

Let $S$ be an arbitrary subset of $\mathbb{V}$. A vector $\mathbf{v}\in {\mathbb{V}}^{\ast }$ is said to be normal to $S$ at a point $\mathbf{a}\in S$ if $\mathbf{v}$ does not make an acute angle with any line segment starting from $\mathbf{a}$ and ending at some $\mathbf{x}\in S$; i.e., if

$$⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0\mathrm{\forall }\mathbf{x}\in S.$$

Example 9.19 (Normal vector)

Let $C$ be a half space given by:

$$C=\{\mathbf{x}|⟨\mathbf{x},\mathbf{b}⟩\le s\}.$$

Let $\mathbf{a}$ be any point on the boundary hyperplane of $C$ given by $⟨\mathbf{a},\mathbf{b}⟩=s$.

Then, $\mathbf{b}$ is normal to $C$ at $\mathbf{a}$ since for any $\mathbf{x}\in C$

$$⟨\mathbf{x}-\mathbf{a},\mathbf{b}⟩=⟨\mathbf{x},\mathbf{b}⟩-⟨\mathbf{a},\mathbf{b}⟩\le s-s=0.$$

Note that $\mathbf{b}$ points opposite to the direction of the halfspace.

Definition 9.36 (Normal cone)

The set of all vectors normal to a set $S$ at a point $\mathbf{a}\in S$, denoted by $N_S(\mathbf{a})$, is called the normal cone to $S$ at $\mathbf{a}$.

$$N_S(\mathbf{a})\triangleq \{\mathbf{v}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0\mathrm{\forall }\mathbf{x}\in S\}.$$

We customarily define $N_S(\mathbf{a})=\varnothing$ for any $\mathbf{a}\notin S$.

Property 9.31

A normal cone is always a convex cone.

Proof. Let $S$ be a subset of $\mathbb{V}$ and let $\mathbf{a}\in S$. Let $N$ denote the set of normal vectors to $S$ at $\mathbf{a}$. We have to show that $N$ is a convex cone; i.e., we have to show that $N$ contains all its conic combinations.

For any $\mathbf{x}\in S$:

$$⟨\mathbf{x}-\mathbf{a},\mathbf{0}⟩=0.$$

Thus, $\mathbf{0}\in N$.

Assume $\mathbf{u}\in N$. Then,

$$⟨\mathbf{x}-\mathbf{a},\mathbf{u}⟩\le 0\mathrm{\forall }\mathbf{x}\in S.$$

But then for any $t\ge 0$,

$$⟨\mathbf{x}-\mathbf{a},t\mathbf{u}⟩=t⟨\mathbf{x}-\mathbf{a},\mathbf{u}⟩\le 0\mathrm{\forall }\mathbf{x}\in S.$$

Thus, $t\mathbf{u}\in N$. Thus, $N$ is closed under nonnegative scalar multiplication.

Now, let $\mathbf{u},\mathbf{v}\in N$. Then,

$$⟨\mathbf{x}-\mathbf{a},\mathbf{u}+\mathbf{v}⟩=⟨\mathbf{x}-\mathbf{a},\mathbf{u}⟩+⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0\mathrm{\forall }\mathbf{x}\in S.$$

since sum of two nonpositive quantities is nonpositive.

Thus, $\mathbf{u}+\mathbf{v}\in N$. Thus, $N$ is closed under vector addition.

Combining these two observations, $N$ is closed under conic combinations. Hence, $N$ is a convex cone.

Property 9.32

A normal cone is closed.

Specifically, if $N_S(\mathbf{a})$ is the normal cone to a set $S$ at a point $\mathbf{a}\in S$, then:

$$N_S(\mathbf{a})=\bigcap _{\mathbf{x}\in S}\{\mathbf{v}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0\}.$$

Proof. For some fixed $\mathbf{a}\in S$ and any fixed $\mathbf{x}\in \mathbb{V}$, define:

$$H_{-}(\mathbf{x}-\mathbf{a})=\{\mathbf{v}\in {\mathbb{V}}^{\ast }|⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0\}.$$

Note that $H_{-}(\mathbf{x}-\mathbf{a})$ is a closed half-space passing through origin of ${\mathbb{V}}^{\ast }$ extending opposite to the direction $\mathbf{x}-\mathbf{a}$.

Let $\mathbf{v}\in N_S(\mathbf{a})$ be a normal vector to $S$ at $\mathbf{a}$.

1. Then, for every $\mathbf{x}\in S$, $⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0$.

2. Thus, for every $\mathbf{x}\in S$, $\mathbf{v}\in H_{-}(\mathbf{x}-\mathbf{a})$.

3. Thus, $\mathbf{v}\in \bigcap _{\mathbf{x}\in S}{H}_{-}(\mathbf{x}-\mathbf{a})$.

4. Thus, $N_S(\mathbf{a})\subseteq \bigcap _{\mathbf{x}\in S}{H}_{-}(\mathbf{x}-\mathbf{a})$.

Going in the opposite direction:

1. Let $\mathbf{v}\in \bigcap _{\mathbf{x}\in S}{H}_{-}(\mathbf{x}-\mathbf{a})$.

2. Then, for every $\mathbf{x}\in S$, $\mathbf{v}\in H_{-}(\mathbf{x}-\mathbf{a})$.

3. Thus, for every $\mathbf{x}\in S$, $⟨\mathbf{x}-\mathbf{a},\mathbf{v}⟩\le 0$.

4. Thus, $\mathbf{v}$ is a normal vector to $S$ at $\mathbf{a}$.

5. Thus, $\mathbf{v}\in N_S(\mathbf{a})$.

6. Thus, $\bigcap _{\mathbf{x}\in S}{H}_{-}(\mathbf{x}-\mathbf{a})\subseteq N_S(\mathbf{a})$.

Combining, we get:

$$N_S(\mathbf{a})=\bigcap _{\mathbf{x}\in S}{H}_{-}(\mathbf{x}-\mathbf{a}).$$

Now, since $N_S(\mathbf{a})$ is an arbitrary intersection of closed half spaces which are individually closed sets, hence $N_S(\mathbf{a})$ is closed.

Since each half space is convex and intersection of convex sets is convex, hence, as a bonus, this proof also shows that $N_S(\mathbf{a})$ is convex.

Theorem 9.63 (Normal cone of entire space)

Let $C=\mathbb{V}$. We wish to compute the normal cone $N_C(\mathbf{x})$ at every $\mathbf{x}\in C$.

1. Let $\mathbf{v}\in N_C(\mathbf{x})$.

2. Then we must have

   $$⟨\mathbf{y}-\mathbf{x},\mathbf{v}⟩\le 0\mathrm{\forall }\mathbf{y}\in \mathbb{V}.$$

3. This is equivalent to

   $$⟨\mathbf{z},\mathbf{v}⟩\le 0\mathrm{\forall }\mathbf{z}\in \mathbb{V}.$$

4. The only vector that satisfies this inequality is $\mathbf{v}=\mathbf{0}$.

5. Hence $N_C(\mathbf{x})=\{\mathbf{0}\}$.

Theorem 9.64 (Normal cone of unit ball)

$$N_{B[\mathbf{0},1]}(\mathbf{x})=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|\Vert \mathbf{y}{\Vert }_{\ast }\le ⟨\mathbf{x},\mathbf{y}⟩\}.$$

Proof. The unit ball at origin is given by:

$$S=B[\mathbf{0},1]=\{\mathbf{x}\in \mathbb{V}|\Vert \mathbf{x}\Vert \le 1\}.$$

Consider $\mathbf{x}\in S$. Then, $\mathbf{y}\in N_S(\mathbf{x})$ if and only if

$$\begin{array}{rl}& ⟨\mathbf{z}-\mathbf{x},\mathbf{y}⟩\le 0\mathrm{\forall }\mathbf{z}\in S\\ & ⟺⟨\mathbf{z},\mathbf{y}⟩\le ⟨\mathbf{x},\mathbf{y}⟩\mathrm{\forall }\mathbf{z}\in S\\ & ⟺\underset{\Vert \mathbf{z}\Vert \le 1}{sup}⟨\mathbf{z},\mathbf{y}⟩\le ⟨\mathbf{x},\mathbf{y}⟩\\ & ⟺\Vert \mathbf{y}{\Vert }_{\ast }\le ⟨\mathbf{x},\mathbf{y}⟩.\end{array}$$

Therefore, for any $\mathbf{x}\in S$:

$$N_S(\mathbf{x})=\{\mathbf{y}\in {\mathbb{V}}^{\ast }|\Vert \mathbf{y}{\Vert }_{\ast }\le ⟨\mathbf{x},\mathbf{y}⟩\}.$$