A linear-time median-finding algorithm for projecting a vector on the simplex of \({\mathbb{R}}^ n\) (Q1823149): Difference between revisions

An algorithm is given for the projection of a vector \(\bar x\in R^ n\) on the simplex \(\{x\in R^ n|\) \(e^ Tx=1\), \(x\geq 0\}\). The problem is written as a convex quadratic programming problem, for which the Kuhn- Tucker conditions are solved. It is shown that the complexity is O(n) time. A numerical example is given.