Welcome to MathOverflow

Question

1

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$

flag	asked Jun 10 2010 at 15:59 Jacob 29●5

	Have you looked at netlib.org? – Steve Huntsman Jun 10 2010 at 16:08
	@Steve: I just looked at it and it provides several useful papers and links. But all the implementations don't seem to discuss sparse matrix support which I truly need. – Jacob Jun 10 2010 at 16:29
	netlib.org/sparse/readme – Steve Huntsman Jun 10 2010 at 16:37
	@Steve: Thanks, but how do I introduce the constraints? – Jacob Jun 10 2010 at 21:33
	It appears you have a QP with simple bounds. There tons of solvers out there for QPs with sparse matrix support. You might want to look into these: abel.ee.ucla.edu/cvxopt, pserc.cornell.edu/bpmpd, control.ee.ethz.ch/~joloef/clp.php, pages.cs.wisc.edu/~swright/ooqp. Or just look here under quadratic programming: users.isy.liu.se/johanl/yalmip/… – Gilead Aug 13 2010 at 3:28

alext87 · Accepted Answer · 2010-06-12 06:06:09Z UTC

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.

Recommendations for a large scale bounded variable least squares (BVLS) solver for sparse matrices

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.