稀疏约束线性最小二乘求解器

Question

这个伟大的SO答案指向一个好的稀疏求解器Ax=b,但是我已经有了约束,x因此每个元素x都是>=0一个<=N.

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

有什么想法/建议吗？我正在寻找像MATLAB这样的东西,lsqlin但是有很大的稀疏矩阵.

我基本上试图解决稀疏矩阵上的大规模有界变量最小二乘问题:

编辑: 在CVX中:

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

Answer 1

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

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