Orthogonal Projection onto the Unit Simplex

The Unit Simplex is defined by:

$$ \mathcal{S} = \left\{ x \in \mathbb{{R}^{n}} \mid x \succeq 0, \, \boldsymbol{1}^{T} 1 = 1 \right\} $$

Orthogonal Projection onto the Unit Simplex is defined by:

$$
\begin{alignat*}{3}
\arg \min_{x} & \quad & \frac{1}{2} \left\| x – y \right\|_{2}^{2} \\
\text{subject to} & \quad & x \succeq 0 \\
& \quad & \boldsymbol{1}^{T} x = 1
\end{alignat*}
$$

Solutions Collecting From Web of "Orthogonal Projection onto the Unit Simplex"

Projection onto the Simplex can be calculated as following.
The Lagrangian in that case is given by:

$$ \begin{align}
L \left( x, \mu \right) & = \frac{1}{2} {\left\| x – y \right\|}^{2} + \mu \left( \boldsymbol{1}^{T} x – 1 \right) && \text{} \\
\end{align} $$

The trick is to leave non negativity constrain implicit.
Hence the Dual Function is given by:

$$ \begin{align}
g \left( \mu \right) & = \inf_{x \succeq 0} L \left( x, \mu \right) && \text{} \\
& = \inf_{x \succeq 0} \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} – {y}_{i} \right) }^{2} + \mu {x}_{i} \right) – \mu && \text{Component wise form}
\end{align} $$

Again, taking advantage of the Component Wise form the solution is given:

$$ \begin{align}
{x}_{i}^{\ast} = { \left( {y}_{i} – \mu \right) }_{+}
\end{align} $$

Where the solution includes the non negativity constrain by Projecting onto $ {\mathbb{R}}_{+} $

The solution is given by finding the $ \mu $ which holds the constrain (Pay attention, since the above was equality constrain, $ \mu $ can have any value and it is not limited to non negativity as $ \lambda $ above).

The objective function (From the KKT) is given by:

$$ \begin{align}
h \left( \mu \right) = \sum_{i = 1}^{n} {x}_{i}^{\ast} – 1 & = \sum_{i = 1}^{n} { \left( {y}_{i} – \mu \right) }_{+} – 1
\end{align} $$

The above is a Piece Wise linear function of $ \mu $ and its Derivative given by:

$$ \begin{align}
\frac{\mathrm{d} }{\mathrm{d} \mu} h \left( \mu \right) & = \frac{\mathrm{d} }{\mathrm{d} \mu} \sum_{i = 1}^{n} { \left( {y}_{i} – \mu \right) }_{+} \\
& = \sum_{i = 1}^{n} -{ \mathbf{1} }_{\left\{ {y}_{i} – \mu > 0 \right\}}
\end{align} $$

Hence it can be solved using Newton Iteration.

I wrote MATLAB code which implements them both at Mathematics StackExchange Question 2338491 – GitHub.
There is a test which compares the result to a reference calculated by CVX.