12

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.

Mohammad Fawaz
  • 523
  • 3
  • 9

2 Answers2

5

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

Geoffrey Irving
  • 3,969
  • 18
  • 41
3

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

Arnold Neumaier
  • 11,318
  • 20
  • 47