# Convex approximation of a constraint

I have a constraint given as $$\left|x_n+\beta x_{n+ 1}\right|-\varepsilon_{ky}\left|x_{n}\right|\leq0\hspace{1em}\forall n=1,2...,N$$ I need to convert this into a convex form to implement in CVX. $$x_n \in \mathcal{C}$$ is optimization variable $$\forall n=1,2...,N-1$$,

The first absolute value appears in a convex manner, so can be left as is in CVX or other convex optimization modeling tool.

The second absolute value appears in a non-convex manner. It can be handled exactly (i.e., without approximation) as shown in section 9.1.6 “Exact absolute value” of Mosek Modeling Cookbook. I modified that to allow lower and upper bounds on the $$x_n$$ to not necessarily have the same absolute value. That might make the formulation tighter and better performing.

Introduce a binary variable $$b_n$$ and continuous variables $$t_n, xPositive_n, xNegative_n$$ for each n from 1 to N-2. Let $$-L_n$$ and $$U_n$$ be lower and upper bounds respectively on those $$x_n$$.

Then replace $$|x_n|$$ with $$t_n$$.

Add the constraints for n from 1 to N-2: $$xPositve_n \ge 0, xNegative_n \ge 0$$ $$x_n = xPositive_n - xNegative_n$$ $$t_n = xPositive_n + xNegative_n$$ $$xPositive_n \le U_n b_n$$ $$xNegative_n \le L_n (1 - b_n)$$

These constraints force at least one of $$xNegative_n$$ and $$xPositive_n$$ to be zero for each n from 1 to N-2, which is what makes the formulation work.

To implement this in CVX, you will need to use a Mixed-Integer capable solver.

EDIT: I just noticed $$x_n \in \mathcal{C}$$. My formulation assumed the variables are real. If they are complex, I am not aware of any exact formulation compatible with CVX, nor any approximation which would necessarily be good.

• Dear @Mark L. Stone, do you assume that the problem is a form of minimization? Commented Feb 10 at 5:51
• @A.Omidi I make no assumption about minimization, maximization, or feasibility problem (no objective). I showed how to address the constraint. Commented Feb 10 at 12:13
• @MarkL.Stone, thanks for the answer. Is there any way I could separate the real and imaginary parts and apply the same approach? Commented Feb 10 at 14:07
• @Muhammad Not that I can think of. Commented Feb 10 at 14:59