Is there a closed form solution for projection onto a nonnegative half-space?

58 Views Asked by At

Let $x,a \in \mathbb{R}^n$ and $b \in \mathbb{R}$. Is there a closed form for calculating the orthogonal projection of a given vector $v \in \mathbb{R}^n$ onto set $$ C=\{x \in \mathbb{R}^n \bigl\vert a^{\top}x \leq b, x \geq 0\} $$ where we know $0 \in C$?

My try

The goal is to find $x^*$ as follows:

$$ x^* = \text{argmin}_{x \in C}\|x-v\|^2. $$

We can minimize the Lagrangian $L(x, \lambda)=\|x-v\|^2+\lambda (a^{\top}x-b)$ over $x \geq 0$ similar to this note. Therefore, $$ \begin{aligned} L(x, \lambda) &= \|x\|^2-2x^{\top}v+\|v\|^2+\lambda a^{\top}x -b\lambda \\ &= \|x\|^2-x^{\top}(2v - \lambda a)+\|v\|^2-b\lambda \\ &= \|x\|^2-x^{\top}(2v - \lambda a)\pm \|2v - \lambda a\|^2+ \|v\|^2-b\lambda \\ &= \|x-(2v - \lambda a)\|^2 - \|2v - \lambda a\|^2+ \|v\|^2-b\lambda. \end{aligned} $$ Then,

$$ (2v - \lambda a)_{+}=\text{argmin}_{x \geq 0}L(x, \lambda) $$ where $(2v - \lambda a)_{+}=\max(2v - \lambda a, 0)$.