Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Do you mean the projection from the origin? If so, the answer is simply $y/s$, where $s$ is the sum of the coordinates of $y$. – Jim Belk Jun 18 '11 at 18:24
@Jim Belk - I meant "projection" to mean the map which sends $y$ to the closest point to it in $S$. Sadly, this does not turn out to equal $y/s$. – robinson Jun 18 '11 at 22:55
Related: – Wok Oct 29 '12 at 12:43
up vote 2 down vote accepted

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

share|cite|improve this answer
This article is not available. – Wok Oct 29 '12 at 12:43
Found. – Wok Oct 29 '12 at 12:50
There is even a Matlab code. It is unfortunately not extensively vectorized, but it is simple to do so. – Wok Oct 29 '12 at 14:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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