1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.