Normal cone (convex analysis)

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$ be a convex subset of a finite-dimensional real inner product space $V$, and let $x\in C$. The normal cone to $C$ at $x$ is

$$N_{C}(x)=\{v\in V:\langle v,y-x\rangle \leq 0{\text{ for all }}y\in C\}.$$

If $x\notin C$, the normal cone is often defined to be empty. The elements of $N_{C}(x)$ are called normal vectors to $C$ at $x$. The sign convention above gives outward normals.

If $x$ is an interior point of $C$, then $N_{C}(x)=\{0\}$. If $C$ is a smooth full-dimensional convex body and $x$ is a boundary point, then $N_{C}(x)$ is the ray generated by the outward normal vector at $x$.

Subgradients

Normal cones are closely related to subgradients. If $f:V\to \mathbb {R} \cup \{+\infty \}$ is a proper convex function, then its epigraph $$\operatorname {epi} f=\{(x,t):t\geq f(x)\}$$ is a convex set. A vector $p\in V$ is a subgradient of $f$ at $x$ if and only if $$(p,-1)\in N_{\operatorname {epi} f}(x,f(x)).$$

Equivalently, $$f(y)\geq f(x)+\langle p,y-x\rangle \quad {\text{for all }}y.$$

Sublevel sets

Still with $f$ a proper convex function, consider the sublevel set through a point $x$: $$C=\{y:f(y)\leq f(x)\}.$$ Every subgradient of $f$ at $x$ determines a normal vector to $C$ at $x$. Indeed, if $p\in \partial f(x)$ and $y\in C$, then $$\langle p,y-x\rangle \leq f(y)-f(x)\leq 0.$$

Under standard regularity hypotheses, for example when $x\in \operatorname {core} (\operatorname {dom} f)$ and $x$ is not a minimizer of $f$, the converse also holds: $$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.

References

• Borwein, Jonathan M.; Lewis, Adrian S. (2006), Convex Analysis and Nonlinear Optimization: Theory and Examples (2nd ed.), New York: Springer, ISBN 978-0-387-29570-1.
• Boyd, Stephen; Vandenberghe, Lieven (2004), Convex Optimization, Cambridge University Press, ISBN 978-0-521-83378-3.
• Rockafellar, R. Tyrrell (1970), Convex Analysis, Princeton Mathematical Series, vol. 28, Princeton University Press, ISBN 978-0-691-08069-7.
• Rockafellar, R. Tyrrell; Wets, Roger J.-B. (1998), Variational Analysis, Grundlehren der mathematischen Wissenschaften, vol. 317, Springer, ISBN 978-3-540-62772-2.