In convex analysis and optimization, the normal cone to a set at a point is a convex cone consisting of vectors that make a non-acute angle with every feasible direction from the point. For a convex set, it is the polar cone of the tangent cone and gives a geometric form of first-order optimality conditions.
Definition Let C {\displaystyle C} be a convex subset of a finite-dimensional real inner product space V {\displaystyle V} , and let x ∈ C {\displaystyle x\in C} . The normal cone to C {\displaystyle C} at x {\displaystyle x} is
N C ( x ) = { v ∈ V : ⟨ v , y − x ⟩ ≤ 0 for all y ∈ C } . {\displaystyle N_{C}(x)=\{v\in V:\langle v,y-x\rangle \leq 0{\text{ for all }}y\in C\}.}
If x ∉ C {\displaystyle x\notin C} , the normal cone is often defined to be empty. The elements of N C ( x ) {\displaystyle N_{C}(x)} are called normal vectors to C {\displaystyle C} at x {\displaystyle x} . The sign convention above gives outward normals. If x {\displaystyle x} is an interior point of C {\displaystyle C} , then N C ( x ) = { 0 } {\displaystyle N_{C}(x)=\{0\}} . If C {\displaystyle C} is a smooth full-dimensional convex body and x {\displaystyle x} is a boundary point, then N C ( x ) {\displaystyle N_{C}(x)} is the ray generated by the outward normal vector at x {\displaystyle x} .
Subgradients Normal cones are closely related to subgradients. If f : V → R ∪ { + ∞ } {\displaystyle f:V\to \mathbb {R} \cup \{+\infty \}} is a proper convex function, then its epigraph
epi f = { ( x , t ) : t ≥ f ( x ) } {\displaystyle \operatorname {epi} f=\{(x,t):t\geq f(x)\}}
is a convex set. A vector p ∈ V {\displaystyle p\in V} is a subgradient of f {\displaystyle f} at x {\displaystyle x} if and only if
( p , − 1 ) ∈ N epi f ( x , f ( x ) ) . {\displaystyle (p,-1)\in N_{\operatorname {epi} f}(x,f(x)).}
Equivalently,
f ( y ) ≥ f ( x ) + ⟨ p , y − x ⟩ for all y . {\displaystyle f(y)\geq f(x)+\langle p,y-x\rangle \quad {\text{for all }}y.}
Sublevel sets Still with f {\displaystyle f} a proper convex function, consider the sublevel set through a point x {\displaystyle x} :
C = { y : f ( y ) ≤ f ( x ) } . {\displaystyle C=\{y:f(y)\leq f(x)\}.}
Every subgradient of
f {\displaystyle f} at x {\displaystyle x} determines a normal vector to C {\displaystyle C} at
x {\displaystyle x} . Indeed, if p ∈ ∂ f ( x ) {\displaystyle p\in \partial f(x)} and y ∈ C {\displaystyle y\in C} , then
⟨ p , y − x ⟩ ≤ f ( y ) − f ( x ) ≤ 0. {\displaystyle \langle p,y-x\rangle \leq f(y)-f(x)\leq 0.}
Under standard regularity hypotheses, for example when
x ∈ core ( dom f ) {\displaystyle x\in \operatorname {core} (\operatorname {dom} f)} and x {\displaystyle x} is not a minimizer of f {\displaystyle f} , the converse also holds:
N C ( x ) = R + ∂ f ( x ) , {\displaystyle N_{C}(x)=\mathbb {R} _{+}\,\partial f(x),}
or equivalently the normal cone to the sublevel set is the closed convex cone generated by the subdifferential.
Notes
… excerpt ends here. Continue reading the full article.
