CODEWITHSUNDEEP
pythonoptimizationmathematical-optimizationcvxopt
user2593973
user2593973

Reputation:

sum of absolute values constraint in semi definite programming

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.

Upvotes: 6

Views: 4942

Answers (3)

NBF
NBF

Reputation: 200

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.

Upvotes: 0

Fanfan
Fanfan

Reputation: 1116

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.

Upvotes: 9

Warren Weckesser
Warren Weckesser

Reputation: 114781

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.

Upvotes: 3

Related Questions