Loading [MathJax]/jax/output/HTML-CSS/autoload/mtable.js

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