Normal and tangent cones

This is a follow-up on the previous post on support functions.

2. Normal and Tangent Cones

In this section we will focus only nonempty closed and convex sets. Rockafellar and Wets in [2] provide an excellent treatment of the more general case of nonconvex and not necessarily closed sets.

Let \( C\subseteq \mathbb{R}^n\) be a nonempty closed convex set and let \( \bar{x} \in C\). A \( d \in \mathbb{R}^n\) is said to be a normal vector to \( C\) at \( \bar{x}\) if \( \langle d, x - \bar{x}\rangle\leq 0\) for all \( x \in C\). The set of normal vectors to \( C\) at \( \bar{x}\) is denoted by \( N_C(\bar{x})\) and can be easily shown to be a convex cone. It is

$$\begin{aligned}N_C(\bar{x}) = \left\{d\in\mathbb{R}^n: \langle d, x-\bar{x}\rangle \leq 0, \forall x\in C\right\}.\end{aligned}$$

Equivalently

$$\begin{aligned}N_C(\bar{x}) =& \left\{d\in\mathbb{R}^n: \sup_{x\in C}\langle d, x-\bar{x}\rangle \leq 0\right\}\\=&\left\{d\in\mathbb{R}^n: \sup_{x\in C}\langle d, x\rangle \leq \langle d, \bar{x}\rangle\right\}\\=&\left\{d\in\mathbb{R}^n: \delta^*_C(d) \leq \langle d, \bar{x}\rangle\right\},\end{aligned}$$

where \( \delta^*_C\) is the support function of \( C\). If \( \bar{x} \notin C\), then \( N_C(\bar{x}) = \emptyset.\)

A vector \( w\in\mathbb{R}^n\) is a tangent vector of \( C\) at \( \bar{x}\) if there are sequences \( (x^\nu)_\nu \subseteq C\), \( x^\nu \to \bar{x}\) and \( \tau^\nu \to 0^+\) such that \( (x^\nu - \bar{x})/\tau^\nu \to w\).

The set of all tangent vectors of \( C\) at \( \bar{x}\in C\) is denoted by \( T_C(\bar{x})\) and it is a closed cone that can be written as the outer limit

$$\begin{aligned}T_C(\bar{x}) = \limsup_{\tau \to 0^+}\tau^{-1}(C-\bar{x}).\end{aligned}$$

The tangent cone can also be expressed as

$$\begin{aligned}T_C(\bar{x}) {}={}& \mathrm{cl} \{w = \lambda (x-\bar{x}), x\in C, \lambda \geq 0\} \\ {}={}& \mathrm{cl}\;\mathrm{cone}(C - \bar{x}).\end{aligned}$$

2.1. Properties of the normal and tangent cones

A first notable property of the normal cone is the following:

Next, let us state an important duality result between the tangent cone and the normal cone.

Sometimes it is more convenient to determine either the normal or the tangent cone; the other one can be determined by virtue of the above proposition.

Some further properties of the normal and tangent cones are stated below (some of these properties are taken from [3, Section 5.3]:

Let us now give some examples most of which are taken from Exercise 2 in [1].

2.2. Trivial case: normal cone of a singleton

This is a trivial example: \(N_{\{x_0\}}(x_0)=\mathbb{R}^n\).

2.3. Normal cone of a closed interval

Let \( C = [a, b] \subseteq \mathbb{R}\). Then, if \( \bar{x} \in (a, b)\), it is \( N_{[a, b]}(\bar{x}) = \{0\}\). If \( \bar{x} = a\), then \( N_{[a, b]}(a) = \{d \in \mathbb{R}: d(x-a) \leq 0, \forall x \in[a, b]\}\), where \( x-a \geq 0\), so \( N_{[a, b]}(a) = (-\infty, 0]\). Likewise, \( N_{[a,b]}(b) = [0, \infty)\). Overall,

2.4. Normal cone of a unit norm-ball

In this section we will prove the following result

We will provide two proofs to this result.

2.4-A. Normal cone of a unit norm-ball (method #1)

For this, we will use the result of Exercise 6.7 from [2], which states the following: Let \( F:\mathbb{R}^n \to \mathbb{R}^m\) be a smooth matting and \( C = F^{-1}(D)\), where \( D \subseteq \mathbb{R}^m\) and suppose that \( \nabla F\) has rank \( m\) at \( \bar{x} \in C\) with \( \bar{u} = F(\bar{x}) \in D\). Then

$$\begin{aligned}T_C(\bar{x}) =& \{w : \nabla F(\bar{x}) w \in T_D(\bar{u})\} \\ N_C(\bar{x}) =& \{\nabla F(\bar{x})^\intercal y : y \in N_{D}(\bar{u})\} \\ \widehat{N}_C(\bar{x}) =& \{\nabla F(\bar{x})^\intercal y : y \in \widehat{N}_{D}(\bar{u})\} \end{aligned}$$

In this case we have \( C = \{x : \|x\| \leq 1\}\). Suppose that \( \|x\| = \sqrt{\langle x, x\rangle}\) for a given inner product on \( \mathbb{R}^n\). This means that there is a symetric positive definite matrix \( Q\) such that \( \|x\| = \sqrt{x^\intercal Q x}\) and we can write \( C = \{x \in \mathbb{R}^n : x^\intercal Q x \leq 1\}\). Define \( F(x) = \tfrac{1}{2}x^\intercal Q x - \tfrac{1}{2}\) and \( D = (-\infty, 0]\). Then \( \nabla F(x) = Qx\), so for \( \|\bar{x}\| = 1\),

$$\begin{aligned} N_C(\bar{x}) =& \{\nabla F(\bar{x})^\intercal y : y \in N_{D}(\bar{u})\} = \{ yQ\bar{x} : y \geq 0\}, \end{aligned}$$

which means that \( N_C(\bar{x}) = \mathrm{cone}(Q\bar{x})\) whenever \( \|\bar{x}\| = 1\) and since the tangent cone is the polar of the normal cone,

$$\begin{aligned}T_C(\bar{x}) = \{w \in \mathbb{R}^n : \langle Q\bar{x}, w \rangle \leq 0\}.\end{aligned}$$

2.4-B. Normal cone of a unit norm-ball (method #2)

Here is an alternative approach: the tangent cone of \( C\) at a point \( \bar{x}\) with \( \|\bar{x}\|_Q = 1\) can be determined using the fact that

$$\begin{aligned}T_C(\bar{x}) = \limsup_{\tau \to 0^+}\tau^{-1}(C - \bar{x}) = \mathrm{cl}\bigcup_{\tau \to 0^+}\tau^{-1}(C - \bar{x}),\end{aligned}$$

where the second equality is because \( C\) is a closed clonex set, and

$$\begin{aligned}\tau^{-1}(C - \bar{x}) = \{x \in \mathbb{R}^n: \|\tau x + \bar{x}\|_Q \leq 1\} = \mathcal{B}^{\|\cdot\|_Q}\left(\tfrac{\bar{x}}{\tau}, \tfrac{1}{\tau}\right).\end{aligned}$$

Let \( \langle \cdot, \cdot \rangle_Q\) denote the inner product that corresponds to \( \|\cdot\|_Q\). We claim that \( T_C(\bar{x}) = \{w \in \mathbb{R}^n: \langle w, \bar{x} \rangle_Q \leq 0\}.\)

Firstly we will show that \( \tau^{-1}(C - \bar{x}) = \mathcal{B}^{\|\cdot\|_Q}\left(\tfrac{\bar{x}}{\tau}, \tfrac{1}{\tau}\right) \subseteq \{w \in \mathbb{R}^n: \langle w, \bar{x} \rangle_Q \leq 0\}.\) Take \( w \in \mathcal{B}^{\|\cdot\|_Q}\left(\tfrac{\bar{x}}{\tau}, \tfrac{1}{\tau}\right),\) i.e., \( \|w + \tau^{-1}\bar{x}\|_Q \leq \tau^{-1}\). We need to show that \( \langle w, \bar{x}\rangle_Q \leq 0\). Indeed,

$$\begin{aligned}\|w + \tau^{-1}\bar{x}\|_Q^2 \leq \tau^{-2} \Rightarrow& \|w\|_Q^2 + \|\tau^{-1}\bar{x}\|_Q^2 + 2 \langle w, \tau^{-1}\bar{x}\rangle_Q \leq \tau^{-2} \\ \Rightarrow& 2\langle w, \tau^{-1}\bar{x}\rangle_Q \leq \tau^{-2} - \|\tau^{-1}\bar{x}\|_Q^2 - \|w\|_Q^2 \leq -\|w\|_Q^2 \\ \Rightarrow& \langle w, \tau^{-1}\bar{x} \rangle_Q \leq 0\end{aligned}$$

Since the set \( \{w \in \mathbb{R}^n: \langle w, \bar{x} \rangle_Q \leq 0\}\) is closed we have that

$$\begin{aligned}T_C(\bar{x}) = \mathrm{cl} \bigcup_{\tau \to 0^+} \mathcal{B}^{\|\cdot\|_Q}\left(\tfrac{\bar{x}}{\tau}, \tfrac{1}{\tau}\right) \subseteq \{w \in \mathbb{R}^n: \langle w, \bar{x} \rangle_Q \leq 0\}.\end{aligned}$$

We now want to show the converse. We start by showing that \( \{w \in \mathbb{R}^n: \langle w, \bar{x} \rangle_Q < 0\} \subseteq T_C(\bar{x})\). In particular, we will show that for every \( w\in\mathbb{R}^n\) with \( \langle w, \bar{x}\rangle_Q < 0\), there is a \( \tau>0\) such that \( \mathcal{B}^{\|\cdot\|_Q}\left(\tfrac{\bar{x}}{\tau}, \tfrac{1}{\tau}\right) \ni w\), or what is the same

$$\begin{aligned}\left\|w + \tau^{-1}\bar{x}\right\|_Q^2 \leq \tau^{-2} \Leftrightarrow \ldots \Leftrightarrow \tau \leq -2\frac{\langle w, \bar{x}\rangle_Q}{\|w\|_Q^2},\end{aligned}$$

where the right hand side is positive.

It remains to show that all vectors \( w\in\mathbb{R}^n\) with \( \langle w, \bar{x}\rangle_Q = 0\) are in the tangent cone. To that end, we will determine a sequence of points \( x_\tau\) that converge to \( w\) while \( x_\tau \in \mathcal{B}^{\|\cdot\|_Q}\left(\tfrac{\bar{x}}{\tau}, \tfrac{1}{\tau}\right).\) The selection of these points is shown in the following figure.

The blue line is the locus of the points \( x_\tau\) for \( \tau > 0\). In this figure we use the Euclidean norm and \( \bar{x}=(0, -1)\), \( w=(8,0) \perp \bar{x}\). In two dimensions, this locus is part of a curve known as the right strophoid.

Given a \( w\) with \( \langle w, \bar{x}\rangle_Q = 0\), we take \( x_\tau\) to be the point where the ball intersects the line segment that connects \( w\) with \( \bar{x}/\tau\). This point is

$$\begin{aligned}x_\tau = -\frac{\bar{x}}{\tau} + \frac{1}{\tau} \frac{w + \frac{\bar{x}}{\tau}}{\left\|w + \frac{\bar{x}}{\tau} \right\|_Q}.\end{aligned}$$

This is a linear combination of \( w\) and \( \bar{x}/\tau\) and can be written as a linear combination of \( w\) and \( \bar{w}\) as \( x_\tau = \lambda(\tau) w + \beta(\tau)\bar{x}\), where

$$\begin{aligned}\lambda(\tau) =& \frac{1}{\|\tau w + \bar{x}\|_Q}, \\ \beta(\tau) =& \frac{1}{\tau}\left(\frac{1}{\tau\left\|w + \frac{\bar{x}}{\tau}\right\|_Q} - 1\right).\end{aligned}$$

We will show that \( \lim_{\tau \to 0^+}\lambda(\tau)=1\) and \( \lim_{\tau \to 0^+}\beta(\tau)=0\). For the first limit we have

$$\begin{aligned}\lim_{\tau \to 0^+}\lambda(\tau) =& \lim_{\tau \to 0^+}\frac{1}{\sqrt{\tau^2\|w\|_Q^2 + 1}} = 1,\end{aligned}$$

where we used the fact that \( \|\bar{x}\|_Q=1\) and \( \langle w, \bar{x}\rangle_Q = 0\). Next,

$$\begin{aligned} \lim_{\tau \to 0^+}\beta(\tau) =& \lim_{\tau \to 0^+}\frac{1}{\tau}\left(\frac{1}{\tau\left\|w + \frac{\bar{x}}{\tau}\right\|_Q} - 1\right) \\ =& \lim_{\tau \to 0^+}\frac{1}{\tau^2\sqrt{\|w\|_Q^2 + \frac{1}{\tau^2}}} - \frac{1}{\tau} \\ =& \lim_{\tau \to 0^+}\frac{1}{\tau \sqrt{\|w\|_Q^2 \tau^2 + 1}} - \frac{1}{\tau} \\ =& \lim_{\tau \to 0^+} \frac{1 - \sqrt{\|w\|_Q^2 \tau^2 + 1}}{\tau \sqrt{\|w\|_Q^2 \tau^2 + 1}} \\ =& \lim_{\tau \to 0^+} \frac{1}{\sqrt{\|w\|_Q^2 \tau^2 + 1}} \cdot \lim_{\tau \to 0^+}\frac{1 - \sqrt{\|w\|_Q^2 \tau^2 + 1}}{\tau}\end{aligned}$$

where we used the product rule of the limit. The first limit is equal to 1. The second one is as follows:

$$\begin{aligned} \lim_{\tau \to 0^+}\beta(\tau) =& \lim_{\tau \to 0^+}\frac{\left(1 - \sqrt{\|w\|_Q^2 \tau^2 + 1}\right)\left(1 + \sqrt{\|w\|_Q^2 \tau^2 + 1}\right)}{\tau\left(1 + \sqrt{\|w\|_Q^2 \tau^2 + 1}\right)} \\ =& \lim_{\tau \to 0^+}\frac{-\|w\|_Q^2 \tau }{1 + \sqrt{\|w\|_Q^2 \tau^2 + 1}} = 0 \end{aligned}$$

This completes the proof. We have shown that \( T_{\mathcal{B}^{\|\cdot\|_Q}}(\bar{x}) = \{w: \langle w, \bar{x}\rangle_Q \leq 0\},\) whenever \( \|\bar{x}\|_Q = 1\).

2.6. Normal cone of a subspace

Suppose that \( C\) is a subspace of \( \mathbb{R}^n\) spanned by the vectors \( \{e_1, \ldots, e_p\}\). Then every \( x \in C\) can be written as \( x = a_1 e_1 + \ldots + a_p e_p\). Take \( \bar{x} \in C\). This means that we can write \( \bar{x} = \bar{a}_1 e_1 + \ldots + \bar{a}_p e_p\) for some \( \bar{a}_1,\ldots, \bar{a}_p\). We have

$$\begin{aligned}N_C(\bar{x}) =& \left\{d\in\mathbb{R}^n: \langle d, x-\bar{x}\rangle \leq 0, \forall x \in C\right\} \\ =& \left\{ d \in \mathbb{R}^n : \langle d, (a_1 - \bar{a}_1)e_1 + \ldots + (a_p - \bar{a}_p)e_p \rangle \leq 0, \forall a_1,\ldots, a_p \in \mathbb{R}\right\} \\ =& \left\{ d \in \mathbb{R}^n : \langle d, b_1 e_1 + \ldots + b_p e_p\rangle \leq 0, \forall b_1,\ldots, b_p \in \mathbb{R}\right\} \end{aligned}$$

It is not difficult to conclude that \( N_C(\bar{x}) = C^\perp\): firstly, if \( d \in N_C(\bar{x})\) if we choose \( b_1 = 1\) and \( b_2=\ldots=b_p=0\) we have that \( \langle d, e_1\rangle \leq 0\). Then, by choosing \( b_1 = -1\) and \( b_2=\ldots=b_p=0\) we see that \( \langle d, -e_1\rangle \leq 0\), so \( \langle d, e_1 \rangle = 0\). Similarly, we have that \( \langle d, e_i \rangle = 0\) for \( i=1,\ldots, p\), therefore, \( N_C(\bar{x}) \subseteq C^\perp\). The converse is straightforward.

2.7. Normal cone of a closed halfspace

Let \( C = \{x \in \mathbb{R}^n : \langle a, x\rangle \leq b\}\) and \( \bar{x} \in C\). Here is is more convenient to start by determining \( T_C(\bar{x})\).

If \( \langle a, \bar{x}\rangle < b\) then and only then \( x\in\mathrm{int} C\), so \( N_C(\bar{x}) = \{0\}\) and \( T_C(\bar{x}) = \mathbb{R}^n\). Take \( \bar{x}\) on the boundary of \( C\), that is, \( \langle a, \bar{x}\rangle = b\). Then,

$$\begin{aligned}\tau^{-1}(C - \bar{x}) = \{x \in \mathbb{R}^n : \langle a, x \rangle \leq 0\} \Rightarrow T_C(\bar{x}) = \{x \in \mathbb{R}^n : \langle a, x\rangle \leq 0\}.\end{aligned}$$

Then, since \( N_C(\bar{x}) = T_C(\bar{x})^\circ\), it is

$$\begin{aligned}N_C(\bar{x}) =& \{y\in\mathbb{R}^n: \langle y, x\rangle \leq 0, \forall x: \langle a, x\rangle \leq 0\} \\ =& \left\{y\in\mathbb{R}^n: \sup_{\langle a, x\rangle \leq 0}\langle y, x\rangle \leq 0 \right\} \\ =& \{y\in\mathbb{R}^n: \delta_{\{x: \langle a, x\rangle \leq 0\}}^*(y) \leq 0\}\end{aligned}$$

But we know that \( \delta^*_{\{x: \langle a, x\rangle \leq 0\}}(y) = \delta_{\{\lambda a; \lambda \geq 0\}}(y),\) therefore,

2.8. Normal cone of polyhedral set

In this section we will derive the normal and tangent cones of polyhedral sets given then V and H representations. We start with the following proposition for polyhedra given in their H representation:

Proof. We will start with the tangent cone. Firstly, we will make a few observations.

Claim 1. For every \( \epsilon > 0\), \( T_{C}(\bar{x}) = T_{C \cap \mathcal{B}(\bar{x}, \epsilon)}(\bar{x}).\)

This is simply because \( T_C\) is defined as a limit, so it is a local property. The following property can be verified very easily:

Claim 2. For every nonempty convex clossed set \( C\subseteq\) and \( \bar{x} \in C\), \( T_C(\bar{x}) = T_{C - \bar{x}}(0).\)

Now define the set \( C_{\mathcal{I}(\bar{x})} = \{x \in \mathbb{R}^n: \langle a_i, x \rangle \leq b_i, \forall i \in \mathcal{I}(\bar{x})\}.\) For all \( j \notin \mathcal{I}(\bar{x}),\) \( \langle a_j , \bar{x} \rangle \neq 0\), so due to the continuity of the inner product, there is a neighbourhood of \( \bar{x}\), \( \mathcal{B}(\bar{x}, \epsilon)\) where \( \langle a_j , x \rangle \neq 0\) for all \( x\in \mathcal{B}(\bar{x}, \epsilon).\) As a result, \( C \cap \mathcal{B}(\bar{x}, \epsilon) = C_{\mathcal{I}}(\bar{x}) \cap \mathcal{B}(\bar{x}, \epsilon).\)

From Claims 1 and 2 we have

$$\begin{aligned}T_C(\bar{x}) {}={}& T_{C-\bar{x}}(0) \\ {}={}& T_{(C-\bar{x}) \cap \mathcal{B}(\epsilon)}(0) \\ {}={}& T_{(C_{\mathcal{I}(\bar{x})}-\bar{x}) \cap \mathcal{B}(\epsilon)}(0),\end{aligned}$$

and note that \( C_{\mathcal{I}(\bar{x})}-\bar{x} = \{x: \langle a_i, x\rangle \leq 0, \forall i \in \mathcal{I}(\bar{x})\},\) which is a cone. This completes the proof. \(\Box\)

This can be proven using the support function of \(C\) (see Proposition 1.5).

---

References

[1] JM Borwein and AS Lewis, Convex analysis and nonlinear optimization: theory and examples, Springer, CMS Books in Mathematics, 2010.

[2] RT Rockafellar and RJB Wets, Variational Analysis, Springer, 2009

[3] J-B Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis, Springer, 2001