Wartość bezwzględna w ograniczeniach liniowych

Mam następujący problem z optymalizacją, w którym mam bezwzględną wartość w moich ograniczeniach:

$\mathbf{x} \in \mathbb{R}^n$$\mathbf{f}_0, \mathbf{f}_1, \ldots, \mathbf{f}_m$$n$

$$\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}$$

Wiem, że możliwa przestrzeń nie będzie wypukła i prawdopodobnie będę potrzebować MILP, aby rozwiązać problem. Szukam najmniejszej liczby zmiennych binarnych, których potrzebowałbym i konfiguracji, która rozwiązałaby problem.

Radzenie sobie z wartościami bezwzględnymi jest na ogół łatwe, gdy tylko jedna strona nierówności ma wartość bezwzględną (http://lpsolve.sourceforge.net/5.1/absolute.htm); ta sprawa wydaje się jednak bardziej skomplikowana.

Z góry dziękuję.

Najprostszym sposobem jest dodanie wartości binarnych i rozwiązanie$m$$s_i \in {0,1}$

$$\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}$$

Myślę, że albo (1) nic nie istnieje znacznie szybciej, albo (2) istnieje specjalna sztuczka, którą można przeformułować jako program wypukły. Prawdopodobnie (1).

Możesz użyć solvera do rozwiązywania problemów z nieuporządkowanymi problemami. Zobacz http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm