稀疏约束线性最小二乘求解器
这个很棒的答案指出对于 Ax=b 来说是一个很好的稀疏求解器，但是我对 x 有限制，使得 x 中的每个元素都是 > =0 和 <=N。
此外，A 非常巨大（大约 2e6x2e6），但非常稀疏，每行有 <=4 个元素。
有什么想法/建议吗？我正在寻找类似于 MATLAB 的 lsqlin 但有巨大的稀疏矩阵。
我本质上是在尝试解决大规模有界变量最小二乘问题< /a> 在稀疏矩阵上：
编辑： 在 CVX 中：
cvx_begin
variable x(n)
minimize( norm(A*x-b) );
subject to
x <= N;
x >= 0;
cvx_end
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.
Also, A is huge (around 2e6x2e6) but very sparse with <=4 elements per row.
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:
EDIT:
In CVX:
cvx_begin
variable x(n)
minimize( norm(A*x-b) );
subject to
x <= N;
x >= 0;
cvx_end
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您正在尝试求解具有框约束的最小二乘法。标准稀疏最小二乘算法包括 LSQR 和最近的 LSMR。这些只需要您应用矩阵向量乘积。要添加约束，请意识到如果您位于盒子的内部（没有任何约束是“活动的”），那么您将继续使用您选择的任何内部点方法。对于所有活动约束，您执行的下一次迭代将停用约束，或约束您沿约束超平面移动。通过对您选择的算法进行一些（概念上相对简单）适当的修改，您可以实现这些约束。
但是，通常您可以使用任何凸优化包。我个人使用 Matlab 包 CVX 解决了这类问题，该包使用 SDPT3/SeDuMi 作为后端。 CVX 只是这些半定程序求解器的一个非常方便的包装器。
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.
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.
您的问题类似于非负最小二乘问题（NNLS），可以表示为
$$\min_x ||Ax-b||_2^2 \text{ subject to } x \ge 0$$，
似乎存在很多算法。
实际上，如果除了原始非负变量 $x$ 之外，您还创建其他变量 $x'$ 并将它们与线性约束 $x_i+x_i'=N$ 链接起来，那么您的问题或多或少可以转换为 NNLS 问题。这种方法的问题在于，这些额外的线性约束在最小二乘解中可能无法完全满足 - 那么尝试用大数对它们进行加权可能是合适的。
Your problem is similar to a nonnegative least-squares problem (NNLS), which can be formulated as
$$\min_x ||Ax-b||_2^2 \text{ subject to } x \ge 0$$,
for which there seems to exist many algorithms.
Actually, you problem can be more or less converted into an NNLS problem, if, in addition to your original nonnegative variables $x$ you create additional variables $x'$ and link them with linear constraints $x_i+x_i'=N$. The problem with this approach is that these additional linear constraints might not be satisfied exactly in the least-squares solution - it might be appropriate then to try to weight them with a large number.
如果您将模型重新表述为：
min
受以下条件限制：
那么这是一个标准的二次规划问题。这是一种常见的模型类型，可以使用 CPLEX 或 Gurobi 等商业求解器轻松求解。 （免责声明：我目前在 Gurobi Optimization 工作，之前在 ILOG 工作，该公司提供 CPLEX）。
If you reformulate your model as:
min
subject to:
then it is a standard quadratic programming problem. This is a common type of model that can be easily solved with a commercial solver such as CPLEX or Gurobi. (Disclaimer: I currently work for Gurobi Optimization and formerly worked for ILOG, which provided CPLEX).
你的矩阵 A^TA 是半正定的，所以你的问题是凸的；设置解算器时一定要利用这一点。
大多数首选 QP 求解器都是 Fortran 和/或非免费的；不过，我听说过有关 OOQP 的好消息 (http: //www.mcs.anl.gov/research/projects/otc/Tools/OOQP/OoqpRequestForm.html），尽管获取副本有点痛苦。
Your matrix A^T A is positive semi-definite, so your problem is convex; be sure to take advantage of that when setting up your solver.
Most go-to QP solvers are in Fortran and/or non-free; however I've heard good things about OOQP (http://www.mcs.anl.gov/research/projects/otc/Tools/OOQP/OoqpRequestForm.html), though it's a bit of a pain getting a copy.
CVXOPT 怎么样？它适用于稀疏矩阵，似乎一些锥体规划求解器可能会有所帮助：
http://abel.ee.ucla.edu/cvxopt/userguide/coneprog.html#quadratic-cone-programs
这是对上面文档中代码的简单修改，以解决你的问题：
CVXOPT支持稀疏矩阵，所以它对你有用。
How about CVXOPT? It works with sparse matrices, and it seems that some of the cone programming solvers may help:
http://abel.ee.ucla.edu/cvxopt/userguide/coneprog.html#quadratic-cone-programs
This is a simple modification of the code in the doc above, to solve your problem:
CVXOPT support sparse matrices, so it be useful for you.
如果您有 Matlab，则可以使用 TFOCS 来完成此操作。这是您用来解决问题的语法：
如果 A 太大而无法放入内存，您可以将 A 作为函数句柄传递。
If you have Matlab, this is something you can do with TFOCS. This is the syntax you would use to solve the problem:
You can pass A as a function handle if it's too big to fit into memory.