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$
  • 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

Your Answer

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

Browse other questions tagged or ask your own question.