# 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). Feb 26 '15 at 14:51

## 1 Answer

By simple inspection, this is a simple quadratic programming problem which is convex and can be solved via interior point methods. CVX should work.

The KKT conditions can provide some insights about the analytical solution but I do not see and easy closed-form solution.

• So I'd assume analytic solution doesn't exist for this problem. Mar 10 '15 at 23:45