处理线性不等式约束的标准方法是将非负松弛变量添加到每个不等式约束以使其成为等式约束并将您的矩阵扩展为块对角矩阵，其中非负松弛变量在对角线上显示为 1x1 块。 $X$

在计算实践中，重要的是利用 SDP 求解器的能力来利用这种块对角结构，而不是简单地使变大。假设您只想证明 SDP 可以在多项式时间内求解，您应该满足于扩大的大小。 $X$$X$

因此，您需要在这里做的就是计算线性不等式约束的数量以获得松弛变量的数量（这将增加的大小），并计算产生的等式约束的数量（以获得。）$X$$m$

C1：等式约束，没有添加松弛变量。$F$

C2：松弛变量等式约束。$C(F,2)(F-2)$$C(F,2)(F-2)$

C3：等式约束，具有松弛变量。$F$$F$

C4：等式约束，具有松弛变量。$F^{2}$$F^{2}$

C5:已经是标准格式。 $X \succeq 0$

加起来，你最终得到

$m=F+C(F,2)(F-2)+F+F^{2}$

和

$n=F+C(F,2)(F-2)+F+F^{2}$

标准形式的 SDP 由矩阵和以及标量 ( ) 的数据定义，将原始问题最小化~C\bullet Z 参数化为和对偶问题服从。今天的大多数求解器都是原始对偶的，即它们同时计算和。因此，在遇到问题时，重要的是要了解您可以选择如何解释模型。我选择不调用任何变量或$C$$A_i$$b_i$$i=1\ldots m$$minimize~C\bullet Z$$A_i\bullet Z = b_i, Z\succeq 0$$maximize~b^T$$C-\sum A_i y_i \succeq 0$$Z$$y$$X$$x$为了强调你拥有的这种自由，不要让这个名字欺骗你。

在您的情况下，如果您以标准求解器为目标，则尝试从描述中提取数据以适合原始形式（您称之为标准相等）不一定是最佳选择。相反，当您有许多（或更多）线性不等式时，您很可能应该尝试将您的模型视为描述对偶的东西。实际上，可以看作是使用，即对应于定义对称矩阵的元素。这意味着您的模型具有复杂性，Brian 称之为$O(F^2)$$X\succeq 0$$C-\sum A_i y_i$$F(F+1)/2$$y$$m=F(F+1)/2$$C(F,2)$. 明显小于您尝试将模型拟合为标准等式形式（原始形式）所获得的结果。这些变量用于具有一个大小为的 LMI 约束和一堆线性不等式的模型中（与 Brian 在总结所需松弛数时相同的分析给出的总数，加上您的等式具有线性约束来编写）。$F$$F$$2F$