I wish to compute the minimizer of $$ \min_{x \in \Delta_n} \langle g , x - y \rangle + \frac{c}{2}\lvert x - y\rvert_1^2$$ where the subindex $1$ indicates that the norm is the $1$-norm and $\Delta_n$ is the unit simplex.
Where can I find info on such problem? The closest I found was a paper by Nesterov where it reduced the problem to computing the minimum value of $$ \min_{t \geq 0} \sum_{i=1}^n y_i(g_i - 2t)^+ + \frac{t^2}{2c}$$ where $y_i, g_i$ are the components of the given vectors $y$ and $g$ of the original problem, $n$ is their length and $\alpha^+$ here means $\max \{0, \alpha\}$.
However it didn't have any info on how to compute the minimum value of this reduced problem, and also only the minimum value of the problems are the same, but I wish to compute the minimizer, not just the value.
I would be happy with a matlab code, a no language code or any info on how to obtain the minimizer.
Assuming that $c \geq 0$, you can reformulate your problem as a convex optimization problem, introducing a dummy variable $t$. It is equivalent to $$\min_{x \in \Delta_n,t \in \mathbb{R}} \langle g , x - y \rangle + \frac{c}{2} t^2 $$ subject to the convex constraint $$ \lVert x - y\rVert_1 \leq t. $$
Note that we do not need an equality constraint as $t$ will be choosen as small as possible in the minimization.
For the reformulated and convex problem you could use the cvx-interface for matlab to solve it. See http://cvxr.com/cvx/ and http://cvxr.com/cvx/doc/CVX.pdf.