I need to solve
$$\mbox{min}||Ax - b||_2^2 \quad \mbox{s.t.} \quad l \leq x \leq u,$$
where $A \in R^{m \times n}$, $m \ll n$, $n \approx 10^4-10^5$.
BVLS [1] based on active-set method works fine for small problems, but it is too slow for large-scale problems I have.
Are there any other (maybe approximate) methods to deal with such problems?
In the bound-constrained case, MATLAB defaults to using a trust-region reflective method found in Coleman, T.F. and Y. Li, "A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables," SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996. You might try that method, and see how it works out.
For very large scale problems, I'd probably use algorithms in TAO tailored to quadratic problems, such as GPCG or BQPIP.
