I have the following optimization problem where I have absolute value in my constraints:Let $\mathbf{x} \in \mathbb{R}^n$ and $\mathbf{f}_0, \mathbf{f}_1, \ldots, \mathbf{f}_m$ be column vectors of size $n$ each. We would like to solve the following:\begin{align}\min &\mathbf{f}_0^T \mathbf{x} \notag \\\text{s.t.}&|\mathbf{f}_1^T \mathbf{x}| \leq |\mathbf{f}_2^T \mathbf{x}| \leq \ldots \leq |\mathbf{f}_m^T \mathbf{x}|\end{align}I know that the feasible space will not be convex and I will probably need an MILP to solve the problem. I'm looking for the least number of binary variables that I would need and the setup that would solve the problem. Dealing with absolute values is generally easy when only one side of the inequality has an absolute value (http://lpsolve.sourceforge.net/5.1/absolute.htm); this case however seems to be more complicated. Thank you in advance.
Absolute Value in Linear Constraints
optimization;linear programming
The easiest way is to add $m$ binary values $s_i \in {0,1}$, and solve\begin{align}\min &\mathbf{f}_0^T \mathbf{x} \notag \\\text{s.t.} & 0 \le (2s_i-1) \mathbf{f}^T_i \mathbf{x} \le (2s_{i+1}-1) \mathbf{f}^T_{i+1} \mathbf{x}  & \forall i\end{align}I think that either (1) nothing substantially faster exists or (2) there is a special trick to reformulate as a convex program.  Probably (1).