3
$\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$

3 Answers 3

Reset to default
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.

$\endgroup$
1
  • $\begingroup$ This is correct. $\endgroup$ Commented Oct 11, 2019 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) $.

$\endgroup$
1
  • $\begingroup$ The question asked for a single LP. $\endgroup$ Commented Oct 11, 2019 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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.