## Thursday, December 1, 2016

### Modeling non-convex absolute value constraints with MILP

We are being asked if one can use MOSEK to express a constraint of the form $$\label{eq:sumabs}\sum_i|x_i|=c$$ for some $x\in\mathbb{R}^n$ and $c\in\mathbb{R}$. This condition is non-convex; for instance for $n=1$ it is equivalent to $x=\pm c$. Such constraints appear in long-short portfolio optimization problems (see stackoverflow, paper).

The idea is to introduce a binary vector indicating the positions of positive/negative entries in $x$. Concretely, we want to split $x$ into the positive and negative part $x=s-t$ with $s,t\geq 0$.

If we know an upper bound $M$ on $s_i$ and $t_i$, then the following system:
\begin{align*} 0\leq s_i&\leq My_i,\\ 0\leq t_i&\leq M(1-y_i),\\ & y_i\in \{0,1\} \end{align*} has the property that at most one of $s_i,t_i$ is non-zero. Indeed:
\begin{align*} s_i>0 \implies y_i=1 \implies t_i=0,\\ t_i>0 \implies y_i=0 \implies s_i=0. \end{align*} Given that we are looking at $\sum_i|x_i|=c$ we can choose $M=c$ as an upper bound for all $|x_i|$. Then an equivalent version of the condition $\eqref{eq:sumabs}$ as a mixed-integer linear program is:
\begin{align*} x&=s-t,\\ 0\leq s&\leq cy,\\ 0\leq t&\leq c(1-y),\\ 0\leq y&\leq 1,\\ c&=\sum_is_i+\sum_it_i,\\ & x,s,t\in\mathbb{R}^n,\ y\in\mathbb{Z}^n.\\ \end{align*}