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*}
$$