# What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely,

$X \in \mathbb{R}^{m \times n}, ~ A \in \mathbb{R}^{q \times m}, C > 0, ~ m > q >> n > 1$.

$\displaystyle \min_X || X - X_0 ||_F$, subject to. $~ A X \geq \mathbf{0}_{q\times n}, ~0 \leq X_{ij} \leq C ~~~\forall i,j$.

Here, C is a constant. What would be the most efficient way to solve this problem? First, does analytical solution already exist? Boyd's book section 8.1.1 discusses similar problems but it's restricted to half spaces, box constraints, and cones. Is this problem reducible to a known problem with analytical solution?

If analytical solution doesn't exist and I were to use existing solvers, LBFGS-B wouldn't take it because of the affine matrix A. What would be the best package to use (the data fits into memory) in this case?

Thank you.

• This problem is solvable in linear time using an exact method (if I understand your notation correctly). – Suvrit Feb 26 '15 at 14:51