Normal cone to the unit simplex

121 Views Asked by At

Normal cone of a closed convex set $C\in\mathbf{R}^{n}$ is given by

$$ N_{C}(x)=\begin{cases} \{u\in\mathbf{R}^{n}\mid u^{\top}(y-x)\leq0,\;\forall y\in C\}, & \text{if }x\in C\\ \emptyset, & \text{else}. \end{cases} $$

Is there a closed-form expression for the normal cone when $C$ is the unit simplex? I.e., if $$ C=\{v\in\mathbf{R}^{n}\mid\sum_{i=1}^{n}v_{i}=1,v_{i}\geq0,\; \text{for } i=1,\ldots,n\}, $$ then what is $N_{C}(x)$ for $x\in C$?

2

There are 2 best solutions below

3
On

Isn't it just the span of $\pmatrix{1\\1\\ \vdots \\ 1}$? I think that if you draw out the standard simplex in 2-space and 3-space, this should become instantly obvious.

0
On

Based on Example 5.2.6 of the book "Jean-Baptiste Hiriart-Urruty, and Claude Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals. Vol. 305. Springer science & business media, 1996", the desired normal cone of unit simplex is given by

$$N_{C}(x)=\{\alpha\mathbf{1}+\sum_{j:x_{j}=0}\beta_{j}e_{j}\mid\alpha\in\mathbf{R},\;\beta_{j}\leq0\},$$

where $x\in C$. Here $\mathbf{1} = (1,1,\ldots,1)$ and $e_j$ is the $i$-th unit vector with the $j$-th element 1 and the rest being zero.