Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta\_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{c},\mathbf{x} \rangle$ is the inner product between $\mathbf{c}$ and $\mathbf{x}$.


**Question**: Given $\mathbf{c}$ and a vector $\mathbf{z}\in [0,1]^n$, how can we *efficiently* compute the projection $P(\mathbf{z}, \Delta\_{\mathbf{c}})$ of $\mathbf{z}$ onto $\Delta\_{\mathbf{c}}$?




---


By writing $P(\mathbf{z}, \Delta\_{\mathbf{c}})$, we mean 
$\arg\min\_{\mathbf{z'}\in\Delta\_{\mathbf{c}}} \Vert \mathbf{z'}-\mathbf{z} \Vert$, where $\Vert \cdot \Vert$ denotes the regular Euclidean norm.



Fast projection onto a subspace
As noted in the comments, this problem is not really a research level problem. Afaik, versions of it were originally solved in the 50s.


Here is an entire survey that discusses efficient algorithms (including linear-time procedures) for this problem as well as generalizations of it: M. Patriksson, *[A survey of classic core problems in operations research](http://www.math.chalmers.se/~mipat/LATEX/survey_posted.pdf)*, 2005, Technical Report, Chalmers University.


If you want a more immediate answer with code (has only $\ge 0$ constraints, but handling upper bounds is easy), have a look at: [Condat's L1 projection code](https://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat_simplexproj.pdf)


Another useful search time: "Continuous quadratic knapsack"


