1
$\begingroup$

I'm trying to solve the BVLS problem for huge (2e6x2e6) matrices which are very sparse (4 elements per row). Does anybody have a recommendation for a free solver (preferably a library of routines)?

The BVLS problem is defined as:

$\underset{l \le x \le u}{\min} \lVert Ax - b \rVert_2^2$

Improve this question
$\endgroup$
5

1 Answer 1

Reset to default
2
$\begingroup$

This is such a well-solved problem that there are many software packages that have built in functions for this.

Here are a selection of built-in functions in different software packages that can be used:

In Matlab: lsqlin (type help lsqlin into Matlab and it tells you exactly what to type. I have just (approximately) solved your problem with random sparse matrices and it works great.)

KNITRO for Mathematica this package also solves this exact problem but I don't have this software so I can't tell you which exact function.

For a free solver I have found this: http://sourceforge.net/projects/quadprog/ However it assumes that $A$ has full column rank. This is just because this algorithm uses the dual problem which exists when the Hessian $A^TA$ is positive definite.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Alext87:I use lsqlin for my experiments but I need a solver to integrate into a larger application (and it should be free). The matrix is not full rank, so I don't know about quadprog. $\endgroup$
    – Jacob
    Commented Jun 14, 2010 at 14:34

You must log in to answer this question.

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