A O (n) ALGORITHM FOR PROJECTING A VECTOR ON THE INTERSECTION OF A HYPERPLANE AND R_+~n

摘要

Cet article présente un algorithme de complexité linéaire pour déterminer la projection d'un vecteur de R~n sur l'intersection d'un hyperplan et de l'orthant positif. Un algorithme de recherche de médiane en temps linéaire est utilisé pour calculer la médiane des composantes du vecteur à projeter. Ceci généralise donc un résultat antérieur de Maculan et Paula Jr pour le cas de la projection sur le simplexe de R~n.%We present a O (n) time algorithm for the projection of a vector on the intersection of a hyperplane and R_+~n. A linear-time median-finding algorithm is used to determine the median of the components of the vector to be projected. This extends a previous result of Maculan and Paula Jr. concerning the projection on the n-dimensional simplex.