sum of absolute values constraint in semi definite programming

Question

I want to further my real world semi definite programming optimization problem with a constraint on sum of absolute values. For example:

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

I have searched internet and documentation but could not find a way to represent this. I am using python and cvxopt module.

Nikethamide

Answer 1

Your constraint is equivalent to the following eight constraints:

 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

I haven't used cvxopt, so I don't know if there is an easier way to handle your constraint with that package. For example, your constraint is equivalent to |x|_1 <= 10, where |x|_1 is the 1-norm of x.

Gennagennaro

Thats very clever Warren. I will have to create 2^n constraints in this case or put them in a matrix form. I would like to wait for a while before accepting your answer. Many thanks. – Nikethamide

I added a comment about the constraint being a 1-norm constraint, but I don't know if cvxopt (or semidefinite programming problems in general) handles such constraints. – Gennagennaro

Answer 2

As an alternative to Warren's solution involving 2^n constraints for a sum of n absolute value terms, one could introduce n extra variables y1, y2, ..., yn and write the following n pairs of inequalites

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

which, combined with a single equality

y1+y2+...+yn = 10

are equivalent to the original constraint

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

Total cost: n new variables and 2n+1 linear constraints.

Murrhine

Thank you Fanfan. This is definitely much better in terms of cost. – Nikethamide

Sorry for being dense, but how would this translate to the matrices G & A and vectors h & b (Gx <= h, Ax = b)? – Luettaluevano

Answer 3

I have also seen the variation:

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

and

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

and

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

Cost: an additional 2N variables, N equality constraints + 2N+1 inequality constraints. Much more than @fanfan's but with other benefits.

xₖ⁺ and xₖ⁻ can be used in an objective function to penalize either the absolute value of xₖ or to give different penalties for the positive and negative parts of xₖ. These slack variables are sometimes used to express transaction costs, e.g.,

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

theta = theta0+buy-sell

buy,sell>=0

and allow for an asymmetry in TC if required.

Obadias