2

我正在尝试进行二次规划。我有一个亲和力矩阵A，我必须最大化某些功能x'*A*x。这基本上与特征匹配有关，即匹配点到标签

这基本上与在加权图中的主导集和二次函数的局部最大化器之间建立联系有关

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

受制于

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

为了解决这个问题，我找到了 Pavan 和 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如果没有不等式约束，可以是，但它没有说 about ，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 回答