## 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*}
{"ft_lang_label":"__label__en","ft_lang_prob":0.7485646,"math_prob":0.99997175,"size":1271,"snap":"2019-13-2019-22","text_gpt3_token_len":480,"char_repetition_ratio":0.11207577,"word_repetition_ratio":0.0,"special_character_ratio":0.3461841,"punctuation_ratio":0.11510792,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99998534,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-05-20T12:25:08Z\",\"WARC-Record-ID\":\"<urn:uuid:1d699ac7-a8a2-4350-92eb-d455617d64be>\",\"Content-Length\":\"82397\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:98bc120f-b01f-411e-ad4e-310c3475b367>\",\"WARC-Concurrent-To\":\"<urn:uuid:9f4d82e6-a498-470a-b40f-633202c879e4>\",\"WARC-IP-Address\":\"172.217.7.161\",\"WARC-Target-URI\":\"https://themosekblog.blogspot.com/2016/12/modeling-non-convex-absolute-value.html\",\"WARC-Payload-Digest\":\"sha1:OPINDGPST7O4YI52W75GRVNCH2AMXQBL\",\"WARC-Block-Digest\":\"sha1:CLODY42TXYXQ5LKED7CSIMZL47IJ5D4Y\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-22/CC-MAIN-2019-22_segments_1558232255944.3_warc_CC-MAIN-20190520121941-20190520143941-00168.warc.gz\"}"}