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

Question

我希望通过对绝对值之和的约束来推进我的真实世界半定规划优化问题.例如:

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

我搜索过互联网和文档,但找不到表示方式.我正在使用python和cvxopt模块.

Answer 1

作为沃伦解决方案的替代方案,涉及n个绝对值项之和的2 ^ n个约束,可以引入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 2

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

 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是 的 1-范数x。