半定规划中的绝对值和约束

Question

我想进一步解决我的现实世界半定规划优化问题，它对绝对值之和有约束。例如：

abs(x1) + abs(x2) + abs(x3) <= 10.

我搜索了互联网和文档，但找不到表示此内容的方法。我正在使用 python 和 cvxopt 模块。

Answer 1

您的约束相当于以下八个约束：

 x1 + x2 + x3 <= 10
 x1 + x2 - x3 <= 10
 x1 - x2 + x3 <= 10
 x1 - x2 - x3 <= 10
-x1 + x2 + x3 <= 10
-x1 + x2 - x3 <= 10
-x1 - x2 + x3 <= 10
-x1 - x2 - x3 <= 10

我没有使用过 cvxopt，所以我不知道是否有更简单的方法来处理您对该包的约束。例如，您的约束等效于 |x|_1 <= 10，其中 |x|_1 是 x 的 1 范数。

Answer 2

作为涉及 n 个绝对值项之和的 2^n 个约束的 Warren 解决方案的替代方案，可以引入 n 个额外变量 y1、y2、...、yn 并写出以下 n 对不等式

-y1 <= x1 <= y1
-y2 <= x2 <= y2
...
-yn <= xn <= yn

其中，结合一个等式

y1+y2+...+yn = 10

等同于原始约束

abs(x1) + abs(x2) + ... + abs(xn) <= 10

总成本：n 个新变量和 2n+1 个线性约束。

Answer 3

我也看到了变体：

x₁ = x₁⁺ - x₁⁻
x₂ = x₂⁺ - x₂⁻
…
xₙ = xₙ⁺ - xₙ⁻

和

x₁⁺, x₁⁻ ≥ 0
x₂⁺, x₂⁻ ≥ 0
…
xₙ⁺, xₙ⁻ ≥ 0

和

(x₁⁺ + x₁⁻) + (x₂⁺ + x₂⁻) + … + (xₙ⁺ + xₙ⁻) ≤ 10

代价：增加2N个变量，N个等式约束+2N+1个不等式约束。比@fanfan 的要多得多，但还有其他好处。

xₖ⁺ 和 xₖ⁻ 可以用在 objective 函数中，以惩罚 xₖ 的绝对值或对 xₖ 的正负部分给予不同的惩罚。这些松弛变量有时用于表示交易成本，例如，

max theta'mu - lambda/2 theta'Sigma theta -TC(buy+sell)

theta = theta0+buy-sell

buy,sell>=0

并在需要时允许 TC 不对称。

半定规划中的绝对值和约束

sum of absolute values constraint in semi definite programming

python

optimization

mathematical-optimization

cvxopt