The normal cone to a ball at a boundary point of the ball

Question

I got stuck in a problem that in the end I needed to know what is the normal cone to a ball $B = \left\{ x \in \mathbb{R}^n : \lVert x \rVert \leq 1 \right\}$ (here $\lVert \cdot \rVert$ is an arbirtrary norm), at a point at the boundary $\partial B$. Recalling that the normal cone to a closed convex set $C$ at a point $x$ in $\mathbb{R}^n$ is the set

$$N_C(x) = \left\{ y \in \mathbb{R}^n : \langle y,z-x \rangle \leq 0 \ \forall z \in C \right\}.$$

I manage to compute it for $n = 1$, you can assume $B = [-1,1]$, if I'm not mistaken, it is

$$N_B(x) = \begin{cases} [0,+\infty), & \ \text{if} \ x=1, \\ (-\infty,0], & \ \text{if} \ x=-1.\end{cases}$$

Intuitively, I think the normal cone $N_B(x)$ will always be a half space at boundary points, but I don't know how this in a more general setting, is my intuition correct? If not, what is it? Any help, hints or references would be appreciated.

$\textbf{Edit}:$ Actually when the norm is differentiable at the point I managed to see that the normal cone is a line (using e.g. Theorem 23.7 of Rockafellar's Convex Analysis book), so the problem actually lies in points where the norm is not differentiable.

Answer 1

Let $\|\cdot\|_*$ denote the dual norm to $\|\cdot\|$: $$ \|y\|_* := \sup_{\|x\|\le 1} x^Ty. $$ This implies $$ x^Ty \le \|x\| \cdot \|y\|_*. $$ Let $$ B:=\{x: \ \|x\|\le 1\}. $$

---

Claim. The normal cone of the unit ball $B$ is then $$ N_B(x) = \{ y: \ x^Ty = \|y\|_*\}. $$

---

Proof. Assume $x^Ty = \|y\|_*$. Take $z\in B$. Then $$ \langle y,z-x \rangle \le \|y\|_* \|z\| - \|y\|_* \le 0. $$ Now take $y \in N_B(x) $. By compactness, there is $z$ with $\|z\|\le 1$ such that $z^Ty=\|y\|_*$. Then $$ 0 \ge \langle y, z-x \rangle = \|y\|_* - y^Tx, $$ which implies $y^Tx \ge \|y\|_*$. Since $\|x\|=1$, this implies $x^Ty = \|y\|_*$ by $$ \|y\|_* \le x^Ty \le \|x\|\cdot \|y\|_* = \|y\|_*. $$

Answer 2

My answer is

$$ N_B(x) = \textbf{cone} (\partial \, \|x\|), \tag{1}$$

which is the conical hull of the subdifferential of $\|x\|$.

By definition, for sub-gradient $y \in \partial \, \|x\|$, for any $z$ the following holds:

$$y^T(z-x) \le \|z\|-\|x\|.$$

By considering the points $x$ and $z$ with $\|x\|=1$ and $\|z\|=1$, we obtain

$$y^T(z-x) \le 0.$$

If $y$ satisfies the above, so does $\lambda y$ for any $\lambda \ge 0$, which gives the result (1).

When $\|x\|$ is differentiable at $x$, i.e., $$\partial \, \|x\|=\{ \nabla \|x\| \},$$ $N_B(x)$ is a ray from $0$ along the gradient $\nabla \|x\|$.

For $n=1$, the gradients (derivatives) of $|x|$ at $x=-1$ and $x=1$ are $-1$ and $1$, respectively, so from (1) we obtain

$$N_B(x) = \begin{cases} [0,+\infty), & \ \text{if} \ x=1, \\ (-\infty,0], & \ \text{if} \ x=-1.\end{cases}$$

For $n=2$ and $\|x\|=\|x\|_1$, from (1) the normal cone at point $x=\left (\frac 12,\frac 12 \right)^T$ is given by

$$\left \{\lambda \binom 11, \lambda \ge0 \right \},$$

while at point $x=(1,0)^T$, it becomes

$$\left \{\lambda _1\binom 11+\lambda _2\binom {1}{-1}, \lambda_1, \lambda_2 \ge0 \right \}.$$