2

私は二次計画法をやろうとしています。アフィニティ マトリックスAがあり、特定の関数を最大化する必要がありますx'*A*x。これは基本的にフィーチャ マッチング、つまりポイントとラベルのマッチングに関連しています。

これは基本的に、重み付きグラフの支配的なセットと二次関数の局所最大化数との間の接続を確立することに関連しています。

maximize(f({x} = x^{T}A{x})

の対象となる

x \epsilon\Delta, \Delta:\sum_{j}x_j=1

この問題を解決するために、Pavan and Pelillo IEEE PAMI 2007 によって与えられたレプリケーター方程式と呼ばれる方法を見つけました。

初期化x(1)が与えられると、離散レプリケータ方程式を使用して局所解 x *を取得できます。

x_i(t+1) = x_i(t+1) \frac{(Ax(t))_i}{x(t)^TAx(t)}

レプリケーター方程式を使用すると、正しい結果が得られます。ただし、このようにmatlabのquadprog関数を使用して解決しようとすると

X = quadprog(-A,[],[],[],Aeq,Beq,s);

正しい値が得られません。7 つのポイントと 7 つのラベルを一致させたいとします。アフィニティ マトリックスを定義してから、上記を使用します。ただし、レプリケーター方程式を使用すると、正しい結果が得られます。しかし、quadprog だけを使用しても正しい結果が得られません。助言がありますか？

私は何か間違ったことをしていますか？

4

2 に答える 2

1

quadprog()ドキュメンテーションショー:

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)

A不等式の制約がない場合は可能ですが、約 とは言っていないbので、ベクトルに設定する必要があると想定しています。また、マークしたものが初期化である場合、正しい位置に配置されていません。[]ffzeross

あなたが書いた行：

X = quadprog(-A,[],[],[],Aeq,Beq,s);

次のようにする必要があります。

X = quadprog(-A,f,[],[],Aeq,Beq,[],[],s);

ここfで、 はゼロ ベクトルです。

ところで、これが凸状の場合、初期化ポイントは必要ありません。凸状でない場合、レプリケーター メソッドと同じローカル ソリューションを見つけることが保証されるかどうかはわかりません。

于 2012-12-06T15:34:32.543 に答える
1

A が半正定値の場合、最大化問題は凸問題ではなく凹問題になります。A が負の半正定値の場合、-A は正の半正定値です。matlab で x^T(-A)x を最適化できます。

すなわち：

min x^TAx

凸であり、

と

max x^TAx  =  min x^T(-A)x

凹です。

もしも

A>0 (Positive semidefinite)

また、quadprog には凸形が必要です

matlab quadprog が失敗するので、 A は正の半正定値だと思います。eig(A) を実行して、すべての固有値が正であるかどうかを確認できるため、凹面の最適化ソリューションが必要です。

于 2012-12-06T16:24:09.977 に答える