absolute linear constraint

[Jaco Vermaak]

Hi there,

I want to implement a constraint of the form A |x| <= b. I am currently doing it by introducing the positive and negative parts of x such that x = x_p - x_n and |x| = x_p + x_n. Of course I also have to ensure that the non-zero elements of x_p and x_n are mutually exclusive, and I'm doing this by modifying my objective (to by minimised) as obj = <other terms> + gamma * (||x_p||_2 + ||x_n||_2).

gamma requires a bit of tuning to ensure <x_p, x_n> is within an acceptable tolerance from zero. However, I also find that the problem is sometimes 'distorted' even when the constraint is not biting (meaning the answer is different from the version without the constraint).

Is this the most straightforward way to implement such a constraint? I know it can also be formulated as a mixed-integer problem, but I want to avoid this as my application is sensitive to compute time.

Many thanks for your help!

Jaco Vermaak

[Erling D. Andersen]

Since

|x| <=1

-|x| <= -1

implies

x=1 or x=-1

then your problem is equivalent to solving a mixed integer problem in general. Therefore, only a MIP formulation can give you an exact answer.

Maybe using

gamma * (||x_p||_1+||x_n||_1)

would be better than the 2 norm you suggest since the one norm has a sparsifying effect. 

[Jaco Vermaak]

That is a good suggestion, thank you. I will try that.

[Erling D. Andersen]

You can replace

||x_p||_1 = sum_j  (x_p)_j

||x_n||_1 = sum_j  (x_n)_j

since x_p,x_n>=0

[Jaco Vermaak]

Thanks again for the help! I tested with the L1 norm and the sum, as above (they are the same), and they are generally better behaved in my setting. Specifically I need a smaller value for gamma to ensure mutual exclusiveness at the same tolerance level. Might be worth adding some notes on this option in the relevant places in the docs?

Kind regards, Jaco