半定规划（SDP）的最大化变体

计算科学优化半定规划

2021-12-21 10:36:08

考虑以下程序：

max_{a a} \sum_{i} z_{i} u . c . a a P P_{i} a a^{⊤} \geq z_{i}

$\max_{\pmb a} \sum_i z_i\\ u.c. \pmb a \pmb P_i\pmb a^\top\geq z_i$

其中 $\pmb a \in\mathbb{R}^p$ 和 $\pmb P_i$ 都是对称半正定矩阵（对于所有 $\pmb P_i$ 的特征值都是）并且是标量。 $\geq 0$ $i$ $z_i$

我想知道这是否确实是一个有效的半定编程问题（基本上我认为它可以重铸为标准形式，但我想确保在我将更多努力扩展到这个攻角之前我没有弄错）。

编辑：

实际上，为了简化问题，我留下了一些限制。实际问题是：

max_{a a} \sum_{i}^{I} z_{i} - \sum_{j}^{J} w_{j} a a P P_{i} a a^{⊤} \geq z_{i}, i = 1, \dots, I a a Q Q_{j} a a^{⊤} - w_{j} = 0, j = 1, \dots, J w_{j} \geq 0

$\max_{\pmb a} \sum_i^I z_i - \sum_j^J w_j\\ \pmb a \pmb P_i\pmb a^\top\geq z_i, i=1,\ldots,I\\ \quad\pmb a \pmb Q_j\pmb a^\top-w_j= 0, j=1,\ldots,J\\ \quad w_j\geq 0$

再次， $\pmb Q_j$ 都是对称非负定的。我认为 Borchers 教授在下面的回答可以很容易地适应完整的程序。添加的约束有助于使程序有界。

2个回答

您可以获得问题的半定松弛，这将为您的问题的最佳值提供一个界限，但它不会是您问题的精确半定公式。

从约束开始

$aP_{i}a^{T} \geq z_{i}$ , $i=1, 2, \ldots, n$

您可以使用产品轨迹的循环置换属性将其写为

$\mbox{tr}(P_{i}a^{T}a) \geq z_{i}$ , $i=1, 2, \ldots, n$

如果你让

$A=a^{T}a$ ,

那么你的约束是

$\mbox{tr}(P_{i}A) \geq z_{i}$ , $i=1, 2, \ldots, n$

和...一起

$A=a^{T}a$ 。

然后，您可以将约束放松到，以放松您的原始问题： $A=a^{T}a$ $A \succeq 0$

$\max_{A,z} \sum_{i} z_{i}$

受制于

$\mbox{tr}(P_{i}A) \geq z_{i}$ , $i=1, 2, \ldots, n$

$A \succeq 0$ 。

这是一个 SDP，它的最优值提供了原始公式最优值的上限。

约束是一个非凸秩一约束，不能在 SDP 中精确表述。 $A=a^{T}a$

可能我误解了某些东西（如果我是，请告诉我），但这是另一种方法：

根据您的表述，您的第一组不平等约束似乎总是很严格。而且由于，不需要约束。 $Q_i \succeq 0$ $w_i \geq 0$

这将允许您将问题重写为它可以再次被重写为一个没有约束的问题：

max_{a a} \sum_{i} z_{i} - \sum_{j} w_{j} a a P P_{i} a a^{⊤} = z_{i} a a Q Q_{j} a a^{⊤} = w_{j},

$\max_{\pmb a} \sum_i z_i - \sum_j w_j\\ \pmb a \pmb P_i\pmb a^\top = z_i\\ \quad\pmb a \pmb Q_j\pmb a^\top = w_j,$

max_{a a} \sum_{i} a a P P_{i} a a^{⊤} - \sum_{j} a a Q Q_{j} a a^{⊤} .

$\max_{\pmb a} \sum_i \pmb a \pmb P_i\pmb a^\top - \sum_j \quad\pmb a \pmb Q_j\pmb a^\top.$

如果我们让，那么问题等价于这很容易解决：如果有任何正特征值，最大化问题是无界的。否则，在处达到最大值。 $S = \sum_i P_i - \sum_j Q_j$

max_{a a} a a^{⊤} S S a a,

$\max_{\pmb a} \pmb a^\top \pmb S \pmb a,$

S

$S$

a = 0

$a = 0$

其它你可能感兴趣的问题

上一篇对称边界条件下一篇在给定矩阵方程的求解器的情况下找到矩阵逆A x = bAx=b