2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Royi Apr 3 '18 at 15:47
  • $\begingroup$ Yep. You got it right. $\endgroup$ – Royi Apr 4 '18 at 13:15
  • $\begingroup$ 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? $\endgroup$ – Crush_on_You Feb 28 at 8:35
  • $\begingroup$ Yep. Indeed this is the case from the above (KKT). $\endgroup$ – Royi Feb 28 at 8:37
  • $\begingroup$ 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? $\endgroup$ – Crush_on_You Feb 28 at 8:41
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ would be awesome if the key ideas can be summarized in the post. $\endgroup$ – Siong Thye Goh Mar 21 '18 at 2:23
  • $\begingroup$ @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 $. $\endgroup$ – Royi Mar 21 '18 at 13:15
  • $\begingroup$ This idea is much older than that paper. Late 80's, I believe, a JOTA paper if I remember. $\endgroup$ – copper.hat Feb 29 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.