1
$\begingroup$

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$,

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.