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 \}. \]