[Math] Determine the normal and tangent cones $N_C (x)$ and $T_C (x)$ for all $x \in C$.

Question

GIVEN

Let $C = \{ x \in \mathbb{R}^n : Ax=b \}$, where $A$ is an $m \times n$ matrix and $b \in \mathbb{R}^m$.

Determine the normal cone $N_C(x)$ and $T_C(x)$ for all $x \in C$.

USEFUL DEFINITIONS

Let $C$ be a nonempty, closed and convex set and let $x \in C$.

Normal Cone

The normal cone of $C$ at $x$ is denoted by $N_C(x)$, and is defined by:
$$z \in N_C(x) \Longleftrightarrow \langle z, c-x\rangle \leq 0, \; \forall c \in C$$
If $x \in \text{int}(C)$ then $N_C(x) = \{ 0 \}$, and if $x \in \text{bdry}(C)$ then then $N_C(x) \neq \{ 0 \}$.

($\text{int}$, $\text{cl}$ and $\text{bdry}$ refer to the interior, closure and the boundary).

Tangent Cone

It is defined to be the polar cone of the normal cone.
$$T_C(x) = \big(N_C(x)\big)^\circ = \{ u \in \mathbb{R}^n : \langle u,v \rangle \leq 0, \; \forall v \in N_C(x) \}$$
It can also be expressed as,
$$T_C(x) = \text{cl}\{ \lambda (c-x) : c \in C \text{ and } \lambda \geq 0\}$$

---

ATTEMPT

I do not clearly understand what $C = \{ x \in \mathbb{R}^n : Ax=b \}$ is, nor do I know how to use its $Ax=b$ property. I am not even sure how to prove that it is closed and convex to use the above definitions.

I first interpreted $Ax=b$ as being a collection of hyperplanes $\langle a^i ,x \rangle = b_i$ with $i=\{1,\ldots,m\}$ and $a^i$ being the $i$th row of $A$. This gives me the impression that $x$ is the intersection of hyperplanes.

I am very confused.

How might I be able to calculate the normal and tangent cones of $C$?

Any help is immensely appreciated.

Answer 1

This is a community wiki answer compiling the discussion in the comments in order to mark this as answered and remove it from the unanswered queue (once either upvoted or accepted).

Notice that $C=\{x:Ax=b\}$ is an affine space. It is of the form $x_0+\ker A$. It is closed and convex – Federico Nov 19 '18 at 23:16

Since $N$ and $T$ are invariant by translation, meaning $N_{x_0+C}(x_0+x)=N_C(x)$, you just have to study the case of a vector space $\ker A$ – Federico Nov 19 '18 at 23:19

Moreover, since $y+\ker A=\ker A$ if $y\in \ker A$, you can just study what happens at the origin: $N_{\ker A}(0)$ and $T_{\ker A}(0)$. – Federico Nov 19 '18 at 23:21

Going with your hints, doesn't that mean that we obtain $\langle z,c\rangle \leq 0$ for all $c\in \ker(A)$? How would this characterize the normal cone? – ex.nihil Nov 20 '18 at 0:03

Notice that if $c \in \ker A$, then also $−c\in\ker A$. So you get both $\langle z,c\rangle\leq 0$ and $\langle z,−c\rangle \leq 0$. This means that actually $\langle z,c\rangle =0$ ... – Federico Nov 20 '18 at 0:05

So, the vectors normal to $C$ are exactly orthogonal to $C$? Does this mean I can write an explicit form for $N_C(x)$? Pardon my slowness, I have big gaps in my Linear Algebra education which I am trying to compensate. – ex.nihil Nov 20 '18 at 0:11

Indeed, for vector subspaces $V$ you get $N_V=V^\perp$. The normal cone is a generalization of the orthogonal space. The two notions coincide for vector spaces. – Federico Nov 20 '18 at 0:14

And since you said the normal cone is translation-invariant, I presume $N_C=C^\perp$ is also true for affine spaces $C$? – ex.nihil Nov 20 '18 at 0:16

Exactly, with the subtlety that $C^\perp$ is a notation usually reserved for vector subspaces. If $C=x+V$ is an affine space with $V$ its corresponding vector space, you have $N_C=V^\perp$. of course, from this it follows also $T_C=V$. – Federico Nov 20 '18 at 0:18