1
$\begingroup$

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.

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

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So I'd assume analytic solution doesn't exist for this problem. $\endgroup$
    – Ben Jackson
    Commented Mar 10, 2015 at 23:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .