# 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} x = 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*}

How could one solve this convex optimization problem?

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}

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$$).

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

\begin{align} 0 = 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 2327504 - GitHub.
There is a test which compares the result to a reference calculated by CVX.

• The constraint regarding $\mu$ is given by $h \left( \mu \right) = 0$. I guess objective function isn't the most clear term :-). But in the case above it is the objective function of the Dual Function. – Royi Apr 3 '18 at 15:47
• Yep. You got it right. – Royi Apr 4 '18 at 13:15
• It seems to me that the minimization problem boils down to find $\mu$ such that $h \left( \mu \right)= 0$ or $\sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{+} - 1 = 0$, right? – Crush_on_You Feb 28 at 8:35
• Yep. Indeed this is the case from the above (KKT). – Royi Feb 28 at 8:37
• I'm sorry but your solution seems much more simpler than the very complicated one proposed by Yunmei Chen and Xiaojing Ye. May I miss something? – Crush_on_You Feb 28 at 8:41

The best algorithm to compute the exact solution to this problem can be found in Projection Onto A Simplex.

• would be awesome if the key ideas can be summarized in the post. – Siong Thye Goh Mar 21 '18 at 2:23
• @SiongThyeGoh, It based on the same idea as my solution below. The main difference is that instead of utilizing Newton Method to find the optimal $\mu$ they use some other trick based on the sorted values of the vector $y$. – Royi Mar 21 '18 at 13:15
• This idea is much older than that paper. Late 80's, I believe, a JOTA paper if I remember. – copper.hat Feb 29 at 6:25