稀疏约束线性最小二乘法 [英] Sparse constrained linear least-squares solver

问题描述

如此出色的答案指向Ax=b的一个好的稀疏求解器，但是我对x有约束，所以x中的每个元素都是>=0和<=N.

This great SO answer points to a good sparse solver for Ax=b, but I've got constraints on x such that each element in x is >=0 an <=N.

此外，A是巨大(大约2e6x2e6)，但是非常稀疏，每行只有<=4个元素.

Also, A is huge (around 2e6x2e6) but very sparse with <=4 elements per row.

有什么想法/建议吗?我正在寻找类似MATLAB的 lsqlin 但矩阵稀疏.

Any ideas/recommendations? I'm looking for something like MATLAB's lsqlin but with huge sparse matrices.

我实质上是在尝试解决大规模最小限界变量稀疏矩阵的平方问题:

I'm essentially trying to solve the large scale bounded variable least squares problem on sparse matrices:

在 CVX :

cvx_begin
    variable x(n)
    minimize( norm(A*x-b) );
    subject to 
        x <= N;
        x >= 0;
cvx_end

推荐答案

您正在尝试求解具有框约束的最小二乘法.标准稀疏最小二乘算法包括LSQR和最近的LSMR.这些仅要求您应用矩阵向量乘积.要添加约束，请意识到，如果您位于框的内部(没有一个约束处于活动"状态)，则可以继续使用选择的任何内部点方法.对于所有活动约束，您执行的下一个迭代将停用约束，或约束您沿约束超平面移动.通过对所选算法进行一些(概念上相对简单)适当的修改，您可以实现这些约束.

You are trying to solve least squares with box constraints. Standard sparse least squares algorithms include LSQR and more recently, LSMR. These only require you to apply matrix-vector products. To add in the constraints, realize that if you are in the interior of the box (none of the constraints are "active"), then you proceed with whatever interior point method you chose. For all active constraints, the next iteration you perform will either deactivate the constraint, or constrain you to move along the constraint hyperplane. With some (conceptually relatively simple) suitable modifications to the algorithm you choose, you can implement these constraints.

但是，通常，您可以使用任何凸优化包.我已经使用Matlab软件包CVX亲自解决了这种类型的问题，该软件包使用SDPT3/SeDuMi作为后端. CVX只是这些半定程序求解器的一个非常方便的包装器.

Generally however, you can use any convex optimization package. I have personally solved this exact type of problem using the Matlab package CVX, which uses SDPT3/SeDuMi for a backend. CVX is merely a very convenient wrapper around these semidefinite program solvers.

这篇关于稀疏约束线性最小二乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！