python - 半定値計画法における絶対値の和の制約

Question

絶対値の合計に制約を付けて、現実世界の半明確なプログラミング最適化問題をさらに進めたいと考えています。例えば：

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

インターネットとドキュメントを検索しましたが、これを表す方法が見つかりませんでした。私はpythonとcvxoptモジュールを使用しています。

Answer 1

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 2

この制約は、次の 8 つの制約と同等です。

 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。