Draft:Normal Cone (variational analysis)

Definition

Let ${\displaystyle X}$ be an Asplund space with topological dual ${\displaystyle X^{*}}$ and ${\displaystyle A\subseteq X}$ a (potentially non-convex) nonempty subset of ${\displaystyle X}$. There are three main normal cones defined for this case:

1. The Fréchet (or firm or regular) normal cone ${\displaystyle N_{A}^{F}}$ is defined by $${\displaystyle N_{A}^{F}({\bar {x}}):=\{\varphi \in X^{*}:\limsup _{x\to {\bar {x}},x\neq {\bar {x}}}{\frac {\langle \varphi ,x-{\bar {x}}\rangle }{\lVert x-{\bar {x}}\rVert }}\leq 0\}}$$for any ${\displaystyle {\bar {x}}\in \operatorname {cl} A}$, and empty outside of that. Alternatively it may be defined as the polar of the Bouligand tangent cone ${\displaystyle T_{A}({\bar {x}})=\{x\in X:\exists (x^{k})\subseteq X,\exists (t_{k})\searrow 0:x^{k}\to x{\text{ and }}{\bar {x}}+t_{k}x^{k}\in A\}.}$^[1] Note that these definitions generally only coincide if ${\displaystyle A}$ is closed.
2. The Mordukhovich (or limiting) normal cone ${\displaystyle N_{A}^{M}}$ is defined by $${\displaystyle N_{A}^{M}({\bar {x}}):=\operatorname {Lim\,sup} _{x\to _{A}{\bar {x}}}N_{A}^{F}(x)=\{\varphi \in X^{*}:\exists (x^{k})\subseteq X:\exists (\varphi ^{k})\subseteq X^{*}:x^{k}\to _{X}{\bar {x}},\varphi ^{k}\to \varphi ,\varphi ^{k}\in N_{A}^{F}(x^{k})\}.}$$ Here ${\displaystyle \operatorname {Lim\,sup} }$ is an outer limit of sets where X carries its usual norm topology while ${\displaystyle X^{*}}$ is endowed with its weak* topology and the notation ${\displaystyle x\to _{A}{\bar {x}}}$ means that "${\displaystyle x}$ converges to ${\displaystyle {\bar {x}}}$ along ${\displaystyle A}$", i.e. the sequence of points in the definition of the outer limit is a sequence of points in ${\displaystyle A}$.
3. The Clarke normal cone ${\displaystyle N_{A}^{C}}$ is defined by $${\displaystyle N_{A}^{C}({\bar {x}}):=\operatorname {cl} (\operatorname {conv} (N_{A}^{M}({\bar {x}}))),}$$where ${\displaystyle \operatorname {cl} }$ is the topological closure and ${\displaystyle \operatorname {conv} }$ the convex hull of a set.

These normal cones form a nested hierarchy ${\displaystyle N_{A}^{F}({\bar {x}})\subseteq N_{A}^{M}({\bar {x}})\subseteq N_{A}^{C}({\bar {x}})}$.

Comparison of Fréchet, Mordukhovich and Clarke normal cones for applications to optimization

Suppose, for simplicity, that we have some Fréchet differentiable function ${\displaystyle f:X\to \mathbb {R} }$ and consider the stationarity condition ${\displaystyle -\nabla f({\bar {x}})\in N_{A}({\bar {x}})}$ corresponding to each of the three normal cones. If ${\displaystyle N_{A}({\bar {x}})}$ is "too large" — in the extreme case we may even find that ${\displaystyle N_{A}({\bar {x}})=X}$ — we can't expect these conditions to actually tell us anything about the (non-)optimality of ${\displaystyle {\bar {x}}}$. Conversely, if ${\displaystyle N_{A}({\bar {x}})}$ is "too small" — in the extreme case we might find it to be empty or to only contain zero — we will find it difficult or even impossible to verify that ${\displaystyle -\nabla f({\bar {x}})\in N_{A}({\bar {x}})}$, or to computationally determine ${\displaystyle {\bar {x}}}$ such that this holds. Because of this (and differences in their associated calculi) all three cones (as well as further ones) have their place in the theory and applications.

Examples

• Let ${\displaystyle A=\{(x,y)\in \mathbb {R} ^{2}:xy=0,y\geq 0\}}$. Then, identifying ${\displaystyle (\mathbb {R} ^{2})^{*}\simeq \mathbb {R} ^{2}}$, we have ${\displaystyle N_{A}^{F}(0)=\{0\}\times (-\infty ,0]}$, ${\displaystyle N_{A}^{M}(0)=\{xy=0\}}$ and ${\displaystyle N_{A}^{C}(0)=\mathbb {R} ^{2}.}$
• Suppose ${\displaystyle X\subseteq \mathbb {R} ^{n}}$ is a smooth embedded submanifold. Let ${\displaystyle p\in X}$ and denote by ${\displaystyle N_{p}X\subseteq T_{p}\mathbb {R} ^{n}}$ the normal space of ${\displaystyle X}$ at ${\displaystyle p}$. Then ${\displaystyle N_{p}X\simeq _{\mathbf {Vect} }N_{X}^{F}(p)=N_{X}^{C}(p)=N_{X}^{M}(p)}$.^[5]

Properties

• The inclusions ${\displaystyle N_{A}^{F}({\bar {x}})\subseteq N_{A}^{M}({\bar {x}})\subseteq N_{A}^{C}({\bar {x}})}$ always hold, in general they are strict.
• ${\displaystyle N_{A}^{F}({\bar {x}})}$ may be trivial, while ${\displaystyle N_{A}^{M}({\bar {x}})}$ is always nontrivial provided that ${\displaystyle \dim(X)<\infty }$, ${\displaystyle A}$ is closed and ${\displaystyle {\bar {x}}\in \operatorname {bd} (A)}$.
• Since the Clarke normal cone is always convex it can often end up being "too large" in practice and may degenerate to ${\displaystyle N_{A}^{C}({\bar {x}})=X^{*}}$. In contrast to this, the Mordukhovich normal cone can be nonconvex which allows it to remain "small enough to be useful" in some cases where Clarke is too large.
• It holds that ${\displaystyle N_{A}^{C}({\bar {x}})=((N_{A}^{M}({\bar {x}}))_{\circ })^{\circ }}$ where ${\displaystyle S_{\circ }\subseteq X}$ is the prepolar of a set ${\displaystyle S\subseteq X^{*}}$ and ${\displaystyle T^{\circ }\subseteq X^{*}}$ is the polar of a set ${\displaystyle T\subseteq X}$ so that ${\displaystyle N_{A}^{C}({\bar {x}})}$ is the bipolar of ${\displaystyle N_{A}^{M}({\bar {x}})}$.

• Let ${\displaystyle C\subseteq X}$ be a convex set, then ${\displaystyle N_{C}^{\operatorname {conv} }=N_{C}^{F}=N_{C}^{M}=N_{C}^{C}}$.
• ${\displaystyle N_{A}^{M}}$ is stable, that is ${\displaystyle N_{A}^{M}({\bar {x}})=\operatorname {Lim\,sup} _{x\to _{A}{\bar {x}}}N_{A}^{M}(x).}$
• Let ${\displaystyle X}$ be Hilbert, ${\displaystyle C\subseteq X}$ non-empty and closed, and suppose ${\displaystyle c\in \operatorname {proj} _{C}(x^{*})}$. Then ${\displaystyle x^{*}-c\in N_{C}^{F}(c)}$. (Note that in contrast to the convex case this fails to be an equivalence in general. Moreover, if ${\displaystyle X}$ is infinite dimensional there may be no such ${\displaystyle c}$)
• Product Rule: ${\displaystyle N_{A_{1}\times A_{2}}^{F}({\bar {x}}_{1},{\bar {x}}_{2})=N_{A_{1}}^{F}({\bar {x}}_{1})\times N_{A_{2}}^{F}({\bar {x}}_{2})}$ for any two nonempty, closed subsets ${\displaystyle A_{1},A_{2}\subseteq X}$, ${\displaystyle {\bar {x}}_{1}\in A_{1},{\bar {x}}_{2}\in A_{2}}$ of a normed space ${\displaystyle X}$. The analogous statement holds for ${\displaystyle N_{A_{1}\times A_{2}}^{M}}$. ^[1]
• Intersection rule: Suppose ${\displaystyle (A_{i})_{i}}$ is a finite family of closed subsets in ${\displaystyle X}$ that is allied at ${\displaystyle {\bar {x}}\in \bigcap _{i}A_{i}}$. Then$${\displaystyle N_{\bigcap _{i}C_{i}}^{\operatorname {conv} }({\bar {x}})\subseteq \sum _{i}N_{C_{i}}^{\operatorname {conv} }({\bar {x}})}$$holds. Alliedness is a somewhat lengthy, technical condition that may be found in Penot's book. Alternatively one may assume the so-called Fuzzy qualification condition. ^[1]
• Chain Rule: Let ${\displaystyle F:\mathbb {R} ^{n}\to \mathbb {R} ^{m}}$ be a ${\displaystyle C^{1}}$-function, and ${\displaystyle C=\{x\in A:F(x)\in D\}}$ where ${\displaystyle A,D}$ are closed in ${\displaystyle \mathbb {R} ^{n},\mathbb {R} ^{m}}$ respectively. Then $${\displaystyle N_{C}^{M}({\bar {x}})=N_{A}^{M}({\bar {x}})+F'({\bar {x}})^{*}N_{D}^{M}(F({\bar {x}})),}$$ subject to some constraint qualifications and regularity conditions. ^[5] Here ${\displaystyle F'}$ is the Jacobian of ${\displaystyle F}$.

References