How to prove the equivalent of minimum over minimum function using big-M method?

189 Views Asked by At

I have a general minimum over minimum function as follows:

$(\textbf{P1}) \quad \min \{ \min \{ f_1(x), f_2(x), f_3(x) \} \} $

Based on the answer from this thread, we can simplify $z = \min \{ f_1(x), f_2(x), f_3(x)\}$, thus I have

\begin{equation} \begin{aligned} (\textbf{P2}) \quad \min \{ z \} \quad \text{s.t.} \quad \left\{ \begin{array}{ll} z \geq f_1(x) - \mathcal{M} y_1, \\ z \geq f_2(x) - \mathcal{M} y_2, \\ z \geq f_3(x) - \mathcal{M} y_3, \\ y_1+y_2+y_3=2\\ y_1,y_2,y_3\in\{0,1\}, \end{array} \right. \end{aligned} \end{equation}

where $\mathcal{M}$ is a big-M method. However, I do not understand how to guarantee that $\mathbf{P1}$ is equivalent to $\mathbf{P2}$. Alternatively, how to proof that $\mathbf{P1}$ is equivalent to $\mathbf{P2}$? and is there any theoretical analysis of this linearization?