9

この素晴らしい SO の回答は、 の優れたスパース ソルバーを示しAx=bていますが、 のx各要素xが.>=0<=N

また、巨大（約2e6x2e6）ですが、行ごとの要素が非常にまばらAです。<=4

アイデア/推奨事項はありますか？MATLAB のようなものを探していますlsqlinが、巨大なスパース マトリックスがあります。

私は基本的に、スパース行列で大規模な有界変数最小二乗問題を解決しようとしています:

代替テキスト

編集： CVXで：

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

6 に答える 6

3

あなたの問題は、次のように定式化できる非負最小二乗問題 (NNLS) に似ています。

$$\min_x ||Ax-b||_2^2 \text{ } x \ge 0$$ の対象

多くのアルゴリズムが存在するようです。

実際、元の非負の変数 $x$ に加えて、追加の変数 $x'$ を作成し、それらを線形制約 $x_i+x_i'=N$ でリンクすると、問題は多かれ少なかれ NNLS 問題に変換できます。このアプローチの問題は、これらの追加の線形制約が最小二乗解で正確に満たされない可能性があることです。その場合、大きな数で重み付けを試みることが適切な場合があります。

于 2010-06-10T08:32:33.280 に答える
3

ボックス制約を使用して最小二乗法を解こうとしています。標準的なスパース最小二乗アルゴリズムには、LSQR と、最近では LSMR が含まれています。これらには、行列ベクトル積を適用するだけで済みます。制約を追加するには、ボックスの内部にいる場合 (どの制約も「アクティブ」でない場合)、選択した内点法に進むことに注意してください。すべてのアクティブな拘束について、実行する次の反復では、拘束が非アクティブ化されるか、拘束超平面に沿って移動するように拘束されます。選択したアルゴリズムに (概念的には比較的単純な) 適切な変更を加えることで、これらの制約を実装できます。

ただし、通常は、任意の凸最適化パッケージを使用できます。バックエンドにSDPT3/SeDuMiを使用するMatlabパッケージCVXを使用して、この正確なタイプの問題を個人的に解決しました。CVX は、これらの半正定値プログラム ソルバーの非常に便利なラッパーにすぎません。

于 2010-06-10T09:15:24.210 に答える
2

モデルを次のように再定式化すると:

最小
の対象:

それは標準的な二次計画問題です。これは、CPLEX や Gurobi などの商用ソルバーで簡単に解決できる一般的なタイプのモデルです。(免責事項: 私は現在 Gurobi Optimization で働いており、以前は CPLEX を提供する ILOG で働いていました)。

于 2011-10-06T22:23:17.867 に答える
1

行列 A^TA は正の半正定であるため、問題は凸状です。ソルバーを設定するときは、必ずそれを利用してください。

ほとんどの頼りになる QP ソルバーは、Fortran および/または非フリーです。ただし、コピーを取得するのは少し面倒ですが、OOQP ( http://www.mcs.anl.gov/research/projects/otc/Tools/OOQP/OoqpRequestForm.html )について良いことを聞いています。

于 2010-06-10T05:04:42.047 に答える
1

Matlab をお持ちの場合、これはTFOCSで実行できます。これは、問題を解決するために使用する構文です。

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

A が大きすぎてメモリに収まらない場合は、関数ハンドルとして渡すことができます。

于 2011-10-06T04:48:24.867 に答える
1

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 はスパース行列をサポートしているため、便利です。

于 2010-06-20T16:58:17.637 に答える