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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.