代码之家 › 专栏 › 技术社区 › Jacob

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

sparse-matrix linear-programming linear-algebra math c++

Jacob · 技术社区 · 14 年前

This great so answer points to a good sparse solver for a x=b ,but i've got constraints on x such that each element i n x is gt;=0 a n lt;=n

另外, a is hurge (around 2E6X2E6)but very sparse with ><=4 elements per row.

有什么想法/建议吗?我在找一些类似matlab的东西 lsqlin >a>but with great sparse matrics.

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


   
    
     
      
       
        
       
      
      
       
        
         编辑:
         
          在
         
        
       
       
        
         
          cvx中
         
        
       
      
      
       
        
         开始
变量x(n)
最小化(norm(a*x-b));
从属于
x=n;
x>=0;
CVX端
< /代码> <
        
        指向一个好的稀疏解算器
        
         Ax=b
        
        但是我有一些限制
        
         x
        
        使每个元素
        
         X
        
        是
        
         >=0
        
        安
        
         <=N
        
        .
        
        
        
         也,
         
          A
         
         是
         
          巨大的
         
         (约2E6x2E6),但非常稀疏
         
          <=4
         
         每行元素数。
        
        
         有什么想法/建议吗?我在找类似matlab的东西
         
          
           lsqlin
          
         
         但是有巨大的稀疏矩阵。
        
        
         我基本上是想解决大规模的问题
         
          bounded variable least squares problem
         
         在稀疏矩阵上:
        
        
         
        
        
        
        
         
          编辑:
         
         在
         
          CVX
         
         :
        
        cvx_begin
    variable x(n)
    minimize( norm(A*x-b) );
    subject to 
        x <= N;
        x >= 0;
cvx_end

6 回复 | 直到 6 年前

Victor Liu 14 年前

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

但是,通常可以使用任何凸优化包。我个人使用matlab包cvx解决了这类问题,它使用sdpt3/sedumi作为后端。cvx只是这些半定程序解算器的一个非常方便的包装器。

Fanfan 14 年前

你的问题类似于 非负最小二乘 问题(nnls),可表述为

$$\Min_X_AX-B__U 2^2\文本以X\GE 0$为准,

对此,似乎存在许多算法。

实际上,如果除了最初的非负变量$x$之外,您还创建了附加变量$x'$并将其与线性约束$x_i+x_i'=n$链接,您的问题可以或多或少地转换为nnls问题。这种方法的问题是,这些额外的线性约束可能无法在最小二乘法中得到精确的满足——然后尝试用一个大的数字对它们进行加权可能是合适的。

user168715 14 年前

你的矩阵a^t a是半正定的,所以你的问题是凸的;在设置解算器时一定要利用这个。

大多数Go-to-Qp求解器都是Fortran和/或非免费的;不过我听说了有关ooqp的一些好消息。( http://www.mcs.anl.gov/research/projects/otc/Tools/OOQP/OoqpRequestForm.html 但要得到一份拷贝有点痛苦。

p.s. 13 年前

如果你有matlab,这是你可以做的。 TFOCS . 这是用于解决问题的语法:

x = tfocs( smooth_quad, { A, -b }, proj_box( 0, N ) );

如果函数句柄太大而无法装入内存,则可以传递它。

Community Romance 7 年前

如果你将你的模型重新表述为:

最小值 $”y%5y“/$ < BR/> 受试者:
$”Y=$ < BR/> $”0 \le x \le n“/$

这是一个标准的二次规划问题。这是一种常见的模型类型,可以通过商业解决方案(如CPLEX或Gurobi)轻松解决。(免责声明:我目前为Gurobi优化工作,以前为提供cplex的ilog工作。)

从属于:
$y=Ax-b$
$0 \le x \le N$

这是一个标准的二次规划问题。这是一种常见的模型类型,可以通过商业解决方案(如CPLEX或Gurobi)轻松解决。(免责声明:我目前为Gurobi优化工作,以前为提供CPLEX的ILOG工作)。

Alejandro 14 年前

cvxopt怎么样?它适用于稀疏矩阵,并且似乎某些圆锥编程解算器可以帮助:

http://abel.ee.ucla.edu/cvxopt/userguide/coneprog.html#quadratic-cone-programs

这是对上述文档中代码的简单修改,以解决您的问题:

from cvxopt import matrix, solvers
A = matrix([ [ .3, -.4,  -.2,  -.4,  1.3 ],
             [ .6, 1.2, -1.7,   .3,  -.3 ],
             [-.3,  .0,   .6, -1.2, -2.0 ] ])
b = matrix([ 1.5, .0, -1.2, -.7, .0])
N = 2;
m, n = A.size
I = matrix(0.0, (n,n))
I[::n+1] = 1.0
G = matrix([-I, I])
h = matrix(n*[0.0]  + n*[N])
print G
print h
dims = {'l': n, 'q': [n+1], 's': []}
x = solvers.coneqp(A.T*A, -A.T*b, G, h)['x']#, dims)['x']
print x

cvxopt支持稀疏矩阵,因此对您很有用。