4
$\begingroup$

Given an elementwise nonnegative vector $y$, I'd like to find the projection of $y$ onto the simplex $S: \{ (x_1, \ldots, x_n) ~|~ \sum_{i=1}^n x_i=1, x_i \geq 0 \mbox{ for all } i \}$.

Is there a closed form expression for this? If not, I need to write a computer program which will compute this projection; is there something simple I could do to compute this?

Simplicity is more important to me than running time; I don't want to spend a long time coding this. I do realize this is a convex optimization problem and could be solved by using various optimization solvers, but that seems like overkill.

  • 0
    [Who were you robinson? What did you see?](http://xkcd.com/979/)2012-10-29

1 Answers 1

5

You can try the article Projection Onto A Simplex by Yunmei Chen and Xiaojing Ye (the code from which is available here), or look at any book on Convex Opimization. The "closed formula" involves sorting, and you can find it using Lagrange multipliers (the version for inequality constraints).

  • 0
    There is even a [Matlab code](http://www.mathworks.com/matlabcentral/fileexchange/30332). It is unfortunately not extensively vectorized, but it is simple to do so.2012-10-29