2
$\begingroup$

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]")

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.