Absolute Value in Linear Constraints

Question

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.

Answer 1

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).

Answer 2

You may use a solver for nonsmooth problems. See http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm