# 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 $$\VV^*$$.

Recall that the dual space $$\VV^*$$ of a vector space $$\VV$$ is the set of all linear functionals on $$\VV$$. For finite dimensional spaces, $$\VV$$ and its dual $$\VV^*$$ are isomorphic. For an inner product space $$\VV$$ every linear functional in $$\VV^*$$ can be identified with a vector $$\bv \in \VV$$ by the functional $$\langle \cdot, \bv \rangle$$ (Theorem 4.106).

Definition 9.32 (Dual cone)

Let $$\VV$$ be a finite dimensional inner product space and $$\VV^*$$ be its dual space.

Let $$C \subset \VV$$. The set

$C^* \triangleq \{ \by \in \VV^* \ST \langle \bx, \by \rangle \geq 0 \Forall \bx \in C \}$

is called the dual cone of $$C$$ in $$\VV^*$$.

In the Euclidean space $$\RR^n$$, the dual cone can be written as:

$C^* \triangleq \{ \by \in \RR^n \ST \langle \bx, \by \rangle \geq 0 \Forall \bx \in C \}.$

Geometric interpretation

• For a vector $$\by$$, the set $$H_{\by, +} \{ \bx \ST \langle \bx, \by \rangle \geq 0\}$$ is a halfspace passing through origin.

• $$\by$$ is the normal vector of the halfspace along (in the direction of) the halfspace.

• If $$\by$$ belongs to the dual cone of $$C$$, then for every $$\bx \in C$$, we have $$\langle \bx, \by \rangle \geq 0$$.

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

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

### 9.5.1.1. Properties#

Property 9.16

Dual cone is a cone.

Proof. Let $$\by \in C^*$$. Then, by definition,

$\langle \bx, \by \rangle \geq 0 \Forall \bx \in C.$

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

$\langle \bx, \alpha \by \rangle = \alpha \langle \bx, \by \rangle \geq 0 \Forall \bx \in C.$

Thus, for every $$\by \in C^*$$, $$\alpha \by \in C^*$$ for all $$\alpha \geq 0$$. Thus, $$C^*$$ is a cone.

Property 9.17

Dual cone is convex.

Proof. Let $$\by_1, \by_2 \in C^*$$. Let $$t \in [0, 1]$$ and

$\by = t \by_1 + (1 - t) \by_2.$

Then for an arbitrary $$\bx \in C$$,

$\langle \bx, \by \rangle = \langle \bx, t \by_1 + (1-t) \by_2 \rangle = t \langle \bx, \by_1 \rangle + (1-t) \langle \bx, \by_2\rangle \geq 0.$

Thus, $$\by \in C^*$$. Thus, $$C^*$$ 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 $$\VV$$ and let $$C_1^*$$ and $$C_2^*$$ be their corresponding dual cones. Then,

$C_1 \subseteq C_2 \implies C_2^* \subseteq C_1^*.$

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

Proof. Let $$\by \in C_2^*$$. Then

$\langle \bx , \by \rangle \geq 0 \Forall \bx \in C_2 \implies \langle \bx , \by \rangle \geq 0 \Forall \bx \in C_1 \implies \by \in C_1^*.$

Thus, $$C_2^* \subseteq C_1^*$$.

Property 9.19 (Closedness)

A dual cone is a closed set.

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

$C^* = \{ \by \in \VV^* \ST \langle \bx, \by \rangle \geq 0 \Forall \bx \in C \}$

Fix a $$\bx \in C$$ and consider the set

$H_{\bx} = \{ \by \in \VV^* \ST \langle \bx, \by \rangle \geq 0 \}.$

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

We can now see that

$C^* = \bigcap_{\bx \in C} H_{\bx}.$

Thus, $$C^*$$ is an intersection of closed half spaces. An arbitrary intersection of closed sets is closed. Hence $$C^*$$ is closed.

Property 9.20 (Interior of dual cone)

The interior of the dual cone $$C^*$$ is given by

$\interior C^* = \{ \by \in \VV^* \ST \langle \bx , \by \rangle > 0 \Forall \bx \in C \setminus \{ \bzero \} \}.$

Proof. Let

$A = \{ \by \ST \langle \bx , \by \rangle > 0 \Forall \bx \in C \setminus \{ \bzero \} \}.$

Let $$\by \in A$$. By definition $$\by \in C^*$$; i.e., $$A \subseteq C^*$$.

Since $$\langle \bx , \by \rangle > 0$$ for every nonzero $$\bx \in C$$, hence $$\langle \bx, \by +\bu \rangle > 0$$ for every nonzero $$\bx \in C$$ and every sufficiently small $$\bu$$. Hence, $$\by \in \interior C^*$$. We have shown that $$A \subseteq \interior C^*$$.

Now, let $$\by \notin A$$ but $$\by \in C^*$$. Then, $$\langle \bx, \by \rangle = 0$$ for some nonzero $$\bx \in C$$. But then

$\langle \bx, \by - t\bx \rangle = \langle \bx, \by \rangle - t \langle \bx, \bx \rangle < 0$

for all $$t > 0$$. Thus, $$\by \notin \interior C^*$$.

Hence, $$A = \interior C^*$$.

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

If $$C$$ has a non-empty interior, then its dual cone $$C^*$$ is pointed.

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

Thus, $$\langle \bx, \by \rangle \geq 0$$ as well as $$\langle \bx, -\by \rangle \geq 0$$ for every $$\bx \in C$$, i.e, $$\langle \bx, \by \rangle = 0$$ for every $$\bx \in C$$. But this means that $$C$$ lies in a hyperplane $$H_{\by, 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 \VV$$ is its orthogonal complement $$V^{\perp}$$ defined as:

$V^{\perp} = \{ \by \ST \langle \bv, \by \rangle = 0 \Forall \bv \in V \}.$

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

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

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

Then, there exists $$\bv \in V$$ such that $$\langle \bv, \by \rangle > 0$$. Since $$V$$ is a subspace, it follows that $$-\bv \in V$$. But then

$\langle -\bv, \by \rangle = - \langle \bv, \by \rangle < 0.$

Thus, $$\by$$ cannot belong to $$V^*$$. A contradiction.

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

### 9.5.1.2. Self Dual Cones#

Definition 9.33 (Self dual cone)

A cone $$C$$ is called self dual if $$C^* = C$$, i.e., it is its own dual cone.

By equality, we mean that the dual cone $$C^*$$ is isomorphic to $$C$$ since technically $$C^* \subseteq \VV^*$$.

Example 9.15 (Nonnegative orthant)

The non-negative orthant $$\RR^n_+$$ is self dual.

Let $$C = \RR^n_+$$. For some $$\bu, \bv \in C$$, $$\langle \bu, \bv \rangle \geq 0$$. Thus, $$\RR^n_+ \subseteq C^*$$.

Now, for some $$\bv \notin \RR^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 $$\bu = [1, 0, \dots, 0] \in \RR^n_+$$. $$\langle \bv, \bu \rangle < 0$$. Thus, $$\bv \notin C^*$$.

Thus, $$C^* = \RR^n_+$$. It is self dual.

Example 9.16 (Positive semidefinite cone)

The positive semi-definite cone $$\SS^n_+$$ is self dual.

Let $$C = \SS^n_+$$ and $$\bY \in C$$. We first show that $$\bY \in C^*$$.

Choose an arbitrary $$\bX \in C$$.
Express $$\bX$$ in terms of its eigenvalue decomposition as

$\bX = \sum \lambda_i \bq_i \bq_i^T.$

Since $$\bX$$ is PSD, hence, $$\lambda_i \geq 0$$.

Then,

\begin{split} \begin{aligned} \langle \bY, \bX \rangle &= \Trace (\bX \bY) = \Trace (\bY \bX) \\ &= \Trace \left ( \bY \sum \lambda_i \bq_i \bq_i^T \right )\\ &= \sum \lambda_i \Trace \left (\bY \bq_i \bq_i^T \right) \\ &= \sum \lambda_i \Trace \left(\bq_i^T \bY \bq_i \right)\\ &= \sum \lambda_i (\bq_i^T \bY \bq_i). \end{aligned} \end{split}

But since $$\bY$$ is PSD, hence $$\bq_i^T \bY \bq_i \geq 0$$. Hence $$\langle \bY, \bX \rangle \geq 0$$. Thus, $$\bY \in C^*$$.

Now, suppose $$\bY \notin \SS^n_+$$. Then there exists a vector $$\bv \in \RR^n$$ such that $$\bv^T \bY \bv < 0$$. Consider the PSD matrix $$\bV = \bv \bv^T$$.

$\langle \bY, \bV \rangle = \Trace(\bV\bY) = \Trace (\bv \bv^T \bY) = \Trace (\bv^T \bY \bv) < 0.$

Thus, $$\bY \notin C^*$$.

This completes the proof that $$C^* = C = \SS^n_+$$, i.e., the positive semi-definite cone is self dual.

## 9.5.2. Polar Cones#

Definition 9.34 (Polar cone)

Let $$\VV$$ be a finite dimensional inner product space and $$\VV^*$$ be its dual space.

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

$C^{\circ} \triangleq \{ \by \in \VV^* \ST \langle \bx, \by \rangle \leq 0 \Forall \bx \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 $$\bx$$ be a given nonzero vector. Let

$C = \cone \{ \bx \} = \{ t \bx \ST t \geq 0 \}.$
1. Let $$\by \in C^{\circ}$$.

2. Then for every $$t \geq 0$$, we have $$\langle t \bx, \by \rangle \leq 0$$.

3. Equivalently, $$\langle \bx, \by \rangle \leq 0$$ since $$t \geq 0$$.

4. Hence

$C^{\circ} = \{ \by \in \VV^* \ST \langle \bx, \by \rangle \leq 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

$\{ \by \in \VV^* \ST \langle \bx, \by \rangle \leq 0\}$

is $$\cone \{ \bx \}$$.

### 9.5.2.1. Properties#

Property 9.22

Polar cone is a cone.

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

$\langle \bx, \by \rangle \leq 0 \Forall \bx \in C.$

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

$\langle \bx, \alpha \by \rangle = \alpha \langle \bx, \by \rangle \leq 0 \Forall \bx \in C.$

Thus, for every $$\by \in C^{\circ}$$, $$\alpha \by \in C^{\circ}$$ for all $$\alpha \geq 0$$. Thus, $$C^{\circ}$$ is a cone.

Property 9.23

Polar cone is convex.

Proof. Let $$\by_1, \by_2 \in C^{\circ}$$. Let $$t \in [0, 1]$$ and

$\by = t \by_1 + (1 - t) \by_2.$

Then for an arbitrary $$\bx \in C$$,

$\langle \bx, \by \rangle = \langle \bx, t \by_1 + (1-t) \by_2 \rangle = t \langle \bx, \by_1 \rangle + (1-t) \langle \bx, \by_2\rangle \leq 0.$

Thus, $$\by \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 $$\VV$$ and let $$C_1^{\circ}$$ and $$C_2^{\circ}$$ be their corresponding polar cones. Then,

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

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

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

$\langle \bx , \by \rangle \leq 0 \Forall \bx \in C_2 \implies \langle \bx , \by \rangle \leq 0 \Forall \bx \in C_1 \implies \by \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} = \{ \by \in \VV^* \ST \langle \bx, \by \rangle \leq 0 \Forall \bx \in C \}$

Fix a $$\bx \in C$$ and consider the set

$H_{\bx} = \{ \by \in \VV^* \ST \langle \bx, \by \rangle \leq 0 \}.$

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

We can now see that

$C^{\circ} = \bigcap_{\bx \in C} H_{\bx}.$

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

$\interior C^{\circ} = \{ \by \in \VV^* \ST \langle \bx , \by \rangle < 0 \Forall \bx \in C \setminus \{ \bzero \} \}.$

Proof. Let

$A = \{ \by \ST \langle \bx , \by \rangle < 0 \Forall \bx \in C \setminus \{ \bzero \} \}.$

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

Since $$\langle \bx , \by \rangle < 0$$ for every nonzero $$\bx \in C$$, hence $$\langle \bx, \by +\bu \rangle < 0$$ for every $$\bx \in C$$ and every sufficiently small $$\bu$$. Hence, $$\by \in \interior C^{\circ}$$. We have shown that $$A \subseteq \interior C^{\circ}$$.

Now, let $$\by \notin A$$ but $$\by \in C^{\circ}$$. Then, $$\langle \bx, \by \rangle = 0$$ for some nonzero $$\bx \in C$$. But then

$\langle \bx, \by - t\bx \rangle = \langle \bx, \by \rangle - t \langle \bx, \bx \rangle > 0$

for all $$t < 0$$. Thus, $$\by \notin \interior C^{\circ}$$.

Hence, $$A = \interior 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 $$\by \in C^{\circ}$$ such that $$-\by \in C^{\circ}$$ holds too.

Thus, $$\langle \bx, \by \rangle \leq 0$$ as well as $$\langle \bx, -\by \rangle \leq 0$$ for every $$\bx \in C$$, i.e, $$\langle \bx, \by \rangle = 0$$ for every $$\bx \in C$$. But this means that $$C$$ lies in a hyperplane $$H_{\by, 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 \VV$$ is its orthogonal complement $$V^{\perp}$$ defined as:

$V^{\perp} = \{ \by \ST \langle \bv, \by \rangle = 0 \Forall \bv \in V \}.$

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

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

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

Then, there exists $$\bv \in V$$ such that $$\langle \bv, \by \rangle < 0$$. Since $$V$$ is a subspace, it follows that $$-\bv \in V$$. But then

$\langle -\bv, \by \rangle = - \langle \bv, \by \rangle > 0.$

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

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

Example 9.18 (Polar cone of a null space)

Let $$\bA \in \RR^{m \times n}$$ and $$C = \nullspace \bA$$.

1. Recall from linear algebra that

$(\nullspace \bA)^{\perp} = \range \bA^T.$
2. Hence by Theorem 9.61,

$C^{\circ} = C^{\perp} = \range \bA^T.$

We can verify this result easily.

1. Let $$\bv \in \range \bA^T$$.

2. Then there exists $$\bu \in \RR^m$$ such that $$\bv = \bA^T \bu$$.

3. For every $$\bx \in \nullspace \bA$$, we have $$\bA \bx = \bzero$$.

4. Hence

$\langle \bx, \bv \rangle = \langle \bx, \bA^T \bu \rangle = \langle \bA \bx, \bu \rangle = \bzero.$
5. Hence $$\bv \in (\nullspace \bA)^{\circ}$$.

Property 9.28 (Polar cone and closure)

For any nonempty set $$C$$, we have

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

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

1. We have $$C \subseteq \closure C$$.

2. Hence by Property 9.24,

$(\closure C)^{\circ} \subseteq C^{\circ}.$

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

1. Let $$\by \in C^{\circ}$$.

2. Then for every $$\bx \in C$$, we have $$\langle \bx, \by \rangle \leq 0$$.

3. Let $$\bx \in \closure C$$.

4. There exists a sequence $$\{ \bx_k \}$$ of $$C$$ such that $$\lim \bx_k = \bx$$.

5. But $$\langle \bx_k, \by \rangle \leq 0$$ for every $$k$$.

6. Hence, taking the limit, we have $$\langle \bx, \by \rangle \leq 0$$.

7. Hence for every $$\bx \in \closure C$$, we have $$\langle \bx, \by \rangle \leq 0$$.

8. Hence $$\by \in (\closure C)^{\circ}$$.

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

Property 9.29 (Polar cone and convex hull)

For any nonempty set $$C$$, we have

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

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

1. We have $$C \subseteq \convex C$$.

2. Hence by Property 9.24,

$(\convex C)^{\circ} \subseteq C^{\circ}.$

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

1. Let $$\by \in C^{\circ}$$.

2. Then for every $$\bx \in C$$, we have $$\langle \bx, \by \rangle \leq 0$$.

3. Let $$\bx \in \convex C$$.

4. Then there exist $$\bx_1, \dots, \bx_k \in C$$ and $$t_1, \dots t_k \geq 0$$ with $$t_1 + \dots + t_k = 1$$ such that

$\bx = \sum_{i=1}^k t_i \bx_i.$
5. Then

$\langle \bx, \by \rangle = \sum_{i=1}^k t_i \langle \bx_i, \by \rangle.$
6. But $$\langle \bx_i, \by \rangle \leq 0$$ since $$\bx_i \in C$$ for every $$i$$.

7. Hence $$\langle \bx, \by \rangle \leq 0$$.

8. Hence for every $$\bx \in \convex C$$, we have $$\langle \bx, \by \rangle \leq 0$$.

9. Hence $$\by \in (\convex C)^{\circ}$$.

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

Property 9.30 (Polar cone and conic hull)

For any nonempty set $$C$$, we have

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

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

1. We have $$C \subseteq \cone C$$.

2. Hence by Property 9.24,

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

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

1. Let $$\by \in C^{\circ}$$.

2. Then for every $$\bx \in C$$, we have $$\langle \bx, \by \rangle \leq 0$$.

3. Let $$\bx \in \cone C$$.

4. Then there exist $$\bx_1, \dots, \bx_k \in C$$ and $$t_1, \dots t_k \geq 0$$ such that

$\bx = \sum_{i=1}^k t_i \bx_i.$
5. Then

$\langle \bx, \by \rangle = \sum_{i=1}^k t_i \langle \bx_i, \by \rangle.$
6. But $$\langle \bx_i, \by \rangle \leq 0$$ since $$\bx_i \in C$$ for every $$i$$.

7. Hence $$\langle \bx, \by \rangle \leq 0$$.

8. Hence for every $$\bx \in \cone C$$, we have $$\langle \bx, \by \rangle \leq 0$$.

9. Hence $$\by \in (\cone C)^{\circ}$$.

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

Theorem 9.62 (Polar cone theorem)

For any nonempty cone $$C$$, we have

$(C^{\circ})^{\circ} = \closure \convex 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 $$\bx \in C$$.

2. By definition, we have $$\langle \bx, \by \rangle \leq 0$$ for every $$\by \in C^{\circ}$$.

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

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

5. Now choose any $$\bz \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 $$\bz$$ on $$C$$, denoted by $$\widehat{\bz}$$ that satisfies

$\langle \bx - \widehat{\bz}, \bz - \widehat{\bz} \rangle \leq 0 \Forall \bx \in C.$
7. Since $$C$$ is a cone, hence $$\bzero \in C$$.

8. Since $$C$$ is a cone and $$\widehat{\bz} \in C$$, hence $$2 \widehat{\bz} \in C$$.

9. By putting $$\bx = \bzero$$, we get

$\langle \widehat{\bz}, \bz - \widehat{\bz} \rangle \geq 0.$
10. By putting $$\bx =2 \widehat{\bz}$$, we get

$\langle \widehat{\bz}, \bz - \widehat{\bz} \rangle \leq 0.$
11. Together, we have

$\langle \widehat{\bz}, \bz - \widehat{\bz} \rangle = 0.$
12. Putting this back into the projection inequality, we get

$\langle \bx, \bz - \widehat{\bz} \rangle \leq 0 \Forall \bx \in C.$
13. Hence $$\bz - \widehat{\bz} \in C^{\circ}$$.

14. Since $$\bz \in (C^{\circ})^{\circ}$$, hence $$\langle \bz, \bz - \widehat{\bz} \langle \leq 0$$.

15. We also have $$-\langle \widehat{\bz}, \bz - \widehat{\bz} \rangle = 0$$.

16. Adding these two, we get

$\langle \bz - \widehat{\bz}, \bz - \widehat{\bz} \rangle \leq 0.$
17. This means that

$\| \bz - \widehat{\bz} \|_2^2 \leq 0.$
18. It follows that $$\bz = \widehat{\bz}$$.

19. Hence $$\bz \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 $$\closure \convex C$$ is a closed convex cone.

2. By previous argument

$\closure \convex C = (\closure \convex C)^{\circ})^{\circ}.$
3. But

$(\closure \convex C)^{\circ} = (\convex C)^{\circ} = C^{\circ}.$
4. Hence

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

## 9.5.3. Normal Cones#

Definition 9.35 (Normal vector)

Let $$S$$ be an arbitrary subset of $$\VV$$. A vector $$\bv \in \VV^*$$ is said to be normal to $$S$$ at a point $$\ba \in S$$ if $$\bv$$ does not make an acute angle with any line segment starting from $$\ba$$ and ending at some $$\bx \in S$$; i.e., if

$\langle \bx - \ba, \bv \rangle \leq 0 \Forall \bx \in S.$

Example 9.19 (Normal vector)

Let $$C$$ be a half space given by:

$C = \{ \bx \ST \langle \bx, \bb \rangle \leq s\}.$

Let $$\ba$$ be any point on the boundary hyperplane of $$C$$ given by $$\langle \ba, \bb \rangle = s$$.

Then, $$\bb$$ is normal to $$C$$ at $$\ba$$ since for any $$\bx \in C$$

$\langle \bx - \ba , \bb \rangle = \langle \bx, \bb \rangle - \langle \ba, \bb \rangle \leq s - s = 0.$

Note that $$\bb$$ 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 $$\ba \in S$$, denoted by $$N_S(\ba)$$, is called the normal cone to $$S$$ at $$\ba$$.

$N_S(\ba) \triangleq \{ \bv \in \VV^* \ST \langle \bx - \ba , \bv \rangle \leq 0 \Forall \bx \in S \}.$

We customarily define $$N_S(\ba) = \EmptySet$$ for any $$\ba \notin S$$.

Property 9.31

A normal cone is always a convex cone.

Proof. Let $$S$$ be a subset of $$\VV$$ and let $$\ba \in S$$. Let $$N$$ denote the set of normal vectors to $$S$$ at $$\ba$$. 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 $$\bx \in S$$:

$\langle \bx - \ba , \bzero \rangle = 0.$

Thus, $$\bzero \in N$$.

Assume $$\bu \in N$$. Then,

$\langle \bx - \ba, \bu \rangle \leq 0 \Forall \bx \in S.$

But then for any $$t \geq 0$$,

$\langle \bx - \ba, t\bu \rangle = t \langle \bx - \ba, \bu \rangle \leq 0 \Forall \bx \in S.$

Thus, $$t \bu \in N$$. Thus, $$N$$ is closed under nonnegative scalar multiplication.

Now, let $$\bu, \bv \in N$$. Then,

$\langle \bx - \ba, \bu + \bv \rangle = \langle \bx - \ba, \bu \rangle + \langle \bx - \ba, \bv \rangle \leq 0 \Forall \bx \in S.$

since sum of two nonpositive quantities is nonpositive.

Thus, $$\bu + \bv \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(\ba)$$ is the normal cone to a set $$S$$ at a point $$\ba \in S$$, then:

$N_S(\ba) = \bigcap_{\bx \in S} \{ \bv \in \VV^* \ST \langle \bx - \ba , \bv \rangle \leq 0 \}.$

Proof. For some fixed $$\ba \in S$$ and any fixed $$\bx \in \VV$$, define:

$H_{-}(\bx - \ba) = \{ \bv \in \VV^* \ST \langle \bx - \ba , \bv \rangle \leq 0 \}.$

Note that $$H_{-}(\bx - \ba)$$ is a closed half-space passing through origin of $$\VV^*$$ extending opposite to the direction $$\bx - \ba$$.

Let $$\bv \in N_S(\ba)$$ be a normal vector to $$S$$ at $$\ba$$.

1. Then, for every $$\bx \in S$$, $$\langle \bx - \ba, \bv \rangle \leq 0$$.

2. Thus, for every $$\bx \in S$$, $$\bv \in H_{-}(\bx - \ba)$$.

3. Thus, $$\bv \in \bigcap_{\bx \in S} H_{-}(\bx - \ba)$$.

4. Thus, $$N_S(\ba) \subseteq \bigcap_{\bx \in S} H_{-}(\bx - \ba)$$.

Going in the opposite direction:

1. Let $$\bv \in \bigcap_{\bx \in S} H_{-}(\bx - \ba)$$.

2. Then, for every $$\bx \in S$$, $$\bv \in H_{-}(\bx - \ba)$$.

3. Thus, for every $$\bx \in S$$, $$\langle \bx - \ba , \bv \rangle \leq 0$$.

4. Thus, $$\bv$$ is a normal vector to $$S$$ at $$\ba$$.

5. Thus, $$\bv \in N_S(\ba)$$.

6. Thus, $$\bigcap_{\bx \in S} H_{-}(\bx - \ba) \subseteq N_S(\ba)$$.

Combining, we get:

$N_S(\ba) = \bigcap_{\bx \in S} H_{-}(\bx - \ba).$

Now, since $$N_S(\ba)$$ is an arbitrary intersection of closed half spaces which are individually closed sets, hence $$N_S(\ba)$$ 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(\ba)$$ is convex.

Theorem 9.63 (Normal cone of entire space)

Let $$C = \VV$$. We wish to compute the normal cone $$N_C(\bx)$$ at every $$\bx \in C$$.

1. Let $$\bv \in N_C(\bx)$$.

2. Then we must have

$\langle \by - \bx, \bv \rangle \leq 0 \Forall \by \in \VV.$
3. This is equivalent to

$\langle \bz, \bv \rangle \leq 0 \Forall \bz \in \VV.$
4. The only vector that satisfies this inequality is $$\bv = \bzero$$.

5. Hence $$N_C(\bx) = \{ \bzero \}$$.

Theorem 9.64 (Normal cone of unit ball)

$N_{B[\bzero, 1]} (\bx) = \{ \by \in \VV^* \ST \| \by \|_* \leq \langle \bx, \by \rangle \}.$

Proof. The unit ball at origin is given by:

$S = B[\bzero, 1] = \{\bx \in \VV \ST \| \bx \| \leq 1 \}.$

Consider $$\bx \in S$$. Then, $$\by \in N_S(\bx)$$ if and only if

$\begin{split} & \langle \bz - \bx , \by \rangle \leq 0 \Forall \bz \in S\\ & \iff \langle \bz , \by \rangle \leq \langle \bx, \by \rangle \Forall \bz \in S\\ & \iff \underset{\| \bz \| \leq 1}{\sup} \langle \bz , \by \rangle \leq \langle \bx, \by \rangle \\ & \iff \| \by \|_* \leq \langle \bx, \by \rangle. \end{split}$

Therefore, for any $$\bx \in S$$:

$N_S(\bx) = \{ \by \in \VV^* \ST \| \by \|_* \leq \langle \bx, \by \rangle \}.$