Absolutwert in linearen Abhängigkeiten

Ich habe das folgende Optimierungsproblem, bei dem meine Einschränkungen einen absoluten Wert haben:

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

Ich weiß, dass der realisierbare Raum nicht konvex sein wird, und ich werde wahrscheinlich eine MILP benötigen, um das Problem zu lösen. Ich suche nach der geringsten Anzahl von Binärvariablen, die ich benötigen würde, und dem Setup, das das Problem lösen würde.

Der Umgang mit absoluten Werten ist im Allgemeinen einfach, wenn nur eine Seite der Ungleichung einen absoluten Wert hat (http://lpsolve.sourceforge.net/5.1/absolute.htm); Dieser Fall scheint jedoch komplizierter zu sein.

Danke im Voraus.

Am einfachsten ist es, Binärwerte s_i \ in {0,1} zu addieren und zu lösen$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}$$

Ich denke, dass entweder (1) nichts wesentlich schnelleres existiert oder (2) es einen speziellen Trick gibt, der als konvexes Programm umformuliert werden kann. Wahrscheinlich (1).

Sie können einen Löser für nicht glatte Probleme verwenden. Siehe http://www.mat.univie.ac.at/~neum/glopt/software_l.html#nonsm