mathematical-optimization - 将变量约束在二次规划中的两个不相交范围之一

Question

如何解决具有以下约束的二次优化问题：

最小化 (1/2)X^TQX + C^TX

服从 -0.01 < x_i < 0.01 或 0.05 < x_i < 0.20，对于 X 中的任何 x_i

其中Q是矩阵，C，X是向量。

似乎我无法将上述约束重新表述为标准约束或不等式约束

Answer 1

请注意，这里的可行区域是非凸的——如果我们有一个 x_1 = 0.01 的可行解决方案和另一个 x_1 = 0.05 的可行解决方案，那么这两个解决方案的任何适当凸组合都是不可行的。因此，不可能将这个问题重新表述为仅使用连续变量的标准二次规划。

相反，您将需要使用二进制变量。例如，我们可以引入二元变量 y_i（每个 x_i 变量一个）并将问题重新表述为：

Minimize (1/2)X^TQX + C^TX
Subject to -0.01 + 0.06y_i <= x_i <= 0.01 + 0.19y_i, for any x_i in X
y_i binary

请注意，现在对于任何 y_i = 0 的变量，你有 -0.01 <= x_i <= 0.01，对于任何 y_i = 1 的变量，你有 0.05 <= x_i <= 0.20。