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?

[1] http://www.stat.berkeley.edu/~stark/Preprints/bvls.pdf


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.

  • $\begingroup$ Geoff, thanks. I have tried MATLAB's routines an they all fail for my problems. Maybe be I just have to tweak parameters better. $\endgroup$
    – Alexander
    Feb 16 '14 at 15:43

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.