I have the following nonlinear optimisation problem under bounds constraints and involving $\min$ functions and the euclidean norm in the objective function :
$$\underset{a,b,c,d}{\min} \Big\Vert \min(X_{:,1}-a,X_{:,2}-b) - \min(X_{:,3}-c,X_{:,4}-d)\Big\Vert_2$$
subject to the constraints $a \in \big[\underline{a},\overline{a}\big]$ $b \in \big[\underline{b},\overline{b}\big]$, $c \in \big[\underline{c},\overline{c}\big]$, $d \in \big[\underline{d},\overline{d}\big]$
where X is a matrix of size $n\times4$ and a,b,c,d $\in \mathbb{R}$ and $X_{:,i}$ stands for the vector corresponding to the $i-th$ colum of X.
I'd like to know if there a way to convert the objective function to standard LP format ? or a way to solve it ? Thank you.
I would approach this in steps.
(1) Linearize $y_{i,1} = \min(X_{i,1}-a,X_{i,2}-b)$
(2) Linearize $y_{i,2} = \min(X_{i,3}-c,X_{i,4}-d)$
(3) Form $z_i = y_{i,1}-y_{i,2}$
(4) Minimize $\sum_i z_i^2$
In general $z=\min(x,y)$ can be linearized as:
$$\begin{align} & z \le x\\ &z \le y \\& z \ge x - M\delta \\ & z \ge y - M(1-\delta) \\ &\delta \in \{0,1\} \end{align}$$ where $\delta$ is a binary variable and $M$ is a large enough constant (judiciously chosen). Notes:
The quadratic objective would make this a MIQP problem. If you allow the 2-norm to be approximated by the sum of absolute values, you can make a linear MIP problem out of this. There are several formulations for this. One is to change steps (3) and (4) into:
(3a) Form $-z_i \le y_{i,1}-y_{i,2} \le z_i$ (you have to split this into two inequalities) with $z_i\ge 0$ .
(4a) Minimize $\sum_i z_i$