Build an explicit polyhedral representation of $\operatorname{Epi}(f)$

Question

Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ be defined by $f(x) = \max\limits_{1\leq i < j \leq n} \{ |x_i| + |x_j| \}$.

Furthermore, let $\operatorname{Epi}(f) = \{ [x; t] \; : \; f(x)\leq t\}$.

How would you build an explicit polyhedral representation of $f$ of the form:

$\operatorname{Epi}(f) = \{ [x; t] \in \mathbb{R}^n \times \mathbb{R} \; : \; \exists u\in \mathbb{R}^m \text{ s.t. } Ax + tb + Cu \leq d \} $

where we have that the number $\dim(u)$ of additional variables and the number $\dim(d)$ of constraints on variables $x, t, u$ grow linearly with $n$.

I tried finding a way to make $u$ related to the absolute value and max functions, but I can't seem to in a way that makes $\dim(u)$ and $\dim(d)$ linear in $n$. Could someone please point me in the right direction.

Answer 1

Not sure if this is what you are looking for:

Note that you can write $f(x) = \max_k b^T_k x$, where $\{b_k\}_k = \{ \pm e_i \pm e_j \}_{i<j}$.

Note that $(x,t) \in \operatorname{epi} f $ iff $f(x) \le t$ iff $b^T_k x +(-1) t \le 0$ for all $k$ iff $\binom{b_k}{-1}^T \binom{x}{t} \le 0$ for all $k$.

Answer 2

Let $u_i$ represent $|x_i|$. The usual linearization is: \begin{align} -t + u_i + u_j &\le 0 &&\text{for $1\le i < j \le n$} \tag1 \\ x_i - u_i &\le 0 &&\text{for all $i$} \tag2 \\ -x_i - u_i &\le 0 &&\text{for all $i$} \tag3 \end{align} Constraint $(1)$ enforces $t \ge \max_{1\le i<j \le n} \{u_i+u_j\}$. Constraints $(2)$ and $(3)$ enforce $u_i \ge |x_i|$. Here, $\dim(u)=n=O(n)$, but $\dim(d)=\binom{n}{2}=O(n^2)$.

---

Here's an alternative approach that avoids the quadratic growth. For $k\in\{1,\dots,n-1\}$, let $u_k$ represent $\max_{1 \le i \le k} \{|x_i|\}$ and $v_k$ represent $\max_{k < i \le n} \{|x_i|\}$. Now impose linear constraints \begin{align} -t + u_k + v_k &\le 0 &&\text{for $k\in\{1,\dots,n-1\}$} \tag4 \\ x_k - u_k &\le 0 &&\text{for $k\in\{1,\dots,n-1\}$} \tag5 \\ -x_k - u_k &\le 0 &&\text{for $k\in\{1,\dots,n-1\}$} \tag6 \\ u_{k-1} - u_k &\le 0 &&\text{for $k\in\{2,\dots,n-1\}$} \tag7 \\ x_{k+1} - v_k &\le 0 &&\text{for $k\in\{1,\dots,n-1\}$} \tag8 \\ -x_{k+1} - v_k &\le 0 &&\text{for $k\in\{1,\dots,n-1\}$} \tag9 \\ v_{k+1} - v_k &\le 0 &&\text{for $k\in\{1,\dots,n-2\}$} \tag{10} \end{align} Constraint $(4)$ enforces $t \ge \max_{1\le k \le n-1} \{u_k+v_k\}$. Constraints $(5)$-$(7)$ enforce $u_k \ge \max(|x_k|,u_{k-1})$. Constraints $(8)$-$(10)$ enforce $v_k \ge \max(|x_{k+1}|,v_{k+1})$.