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

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.

• You are missing $\leq0$ in the definition of $N_C$ Nov 19 '18 at 23:14
• Notice that $C=\{x:Ax=b\}$ is an affine space. It is of the form $x_0+\ker A$. It is closed and convex 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$ 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)$. 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? Nov 20 '18 at 0:03

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