Let $\Delta^n$ denote the $n$-dimensional probability simplex. Projection Onto A Simplex by Yunmei Chen and Xiaojing Ye gives an algorithm for the $\ell_2$-projection of a vector onto $\Delta^n$, i.e., given $y \in \mathbb R^n$, they give a non-iterative method to find a minimizer $x^\ast(y)$ of $$ \min_{x \in \Delta^n} \|x-y\|_p $$ where $p = 2$.
I am interested in the case where $p = 1$. Is there a method that computes an optimizer $x^\ast(y)$ for $p = 1$ which does not use a convex solver?
In the case of p=1, unlike the Euclidean norm, the optimizer is not unique. So it does not have good properties and if you think about it a bit you can see that in some cases it will be non-intuitive. But the following procedure should give one of the many possible optimizers: If $y_i\leq0$ set $x_i=0$. Now denote the rest of indices i such that $y_i>0$ as $S$. If $s=\sum_{i\in S} y_i\geq 1$ then simply choose $x_i\leq y_i, ~i\in S$, such that $\sum_{i\in S} x_i=1$ (It is easy to choose a point like that). Any such point would be an optimizer. Now for the case where $s=\sum_{i\in S} y_i <1$, simply choose $x_i\geq y_i, ~i\in S$, such that $\sum_{i\in S} x_i=1$, e.g. $x_i = y_i + \frac{1-s}{|S|}$.
In the case where all the indices in y have non-positive value, then any point on the simplex is an optimizer.