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$
1
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is correct. $\endgroup$ – RobPratt Oct 11 '19 at 19:45
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) $.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The question asked for a single LP. $\endgroup$ – RobPratt Oct 11 '19 at 19:44
0
$\begingroup$

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

| cite | improve this answer | |
$\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.