Minimize the minimum - Linear programming

Question

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We want to minimize $\min_{1\leq i\leq m} f_i(x_1, \dots, x_n)$.

Is it possible to formulate this problem as a single linear programming one?

(Maybe it's trivial since everything is linear, I don't know. If it is, what about the same problem, except that every everything may not be linear and we want to formulate it as "$\min c^Tx$ s.t. [list of non-linear constraints]")

Answer 1

As far as I know the answer is negative: the point-wise minimum of affine functions is not convex and thus you cannot cast an an LP.

Answer 2

You can maximize a minimum or minimize a maximum with a single LP, but min-min and max-max are both non-convex.

Answer 3

Solve the $m$ different LPs : $\min\limits_{x} f_i(x)$, with your usual constraints. Then, select the $i$ with the lowest value of $f_i$. There is your minimum.

Why does this work? If $i_0$ gives you the lowest value for your LP with argument $x_0$, then $\forall i \in [1,m], \forall x \in \mathbb(R)^n, f_i(x) \geq \min\limits_{x} f_i(x) \geq f_{i_0}(x_0) $.