Linear programming with two maxes in a min function

linear programmingoptimization

Suppose $A, B, C$ are sets such that $B,C$ are disjoint.
Let $f : A\times (B\cup C) \rightarrow \mathbb{R}$ where for fixed $y\in B\cup C$, we have that $f(a, y)$ is linear in $a$.
Then is it true that the linear program

$\min\limits_{a\in A} \left( \max\limits_{b\in B} f(a, b) + \max\limits_{c\in C} f(a, c) \right) $

is equivalent to the linear program

$\begin{align} \min\limits_{a\in A} & \quad (z_1 + z_2) \\
\text{subject to}& \quad z_1\geq f(a,b) &\forall b\in B\\
& \quad z_2 \geq f(a,c) &\forall c\in C \end{align}$

My belief is that they are, but I just wanted to verify this.

Best Answer

Yes, this works. If you want to check this, the key facts are that:

  1. For every feasible point $a \in A$ of the first problem, there is a feasible point of the second problem with the same objective value: the point $(a, z_1, z_2)$ where $z_1 = \max\limits_{b\in B} f(a, b)$ and $z_2 = \max\limits_{c\in C} f(a, c)$.
  2. For every feasible point $(a, z_1, z_2)$ of the second problem, there is a feasible point of the first problem with an objective value that's at least as good: the point $a$. The constraints on the second problem imply that $\max\limits_{b\in B} f(a, b) + \max\limits_{c\in C} f(a, c) \le z_1 + z_2$.

Fact 1 tells us that the optimal value of the second problem is at most the optimal value of the first problem. Fact 2 tells us that the optimal value of the first problem is at most the optimal value of the second problem. What's more, if you solve one of the problems, you can use one of the facts to get an optimal solution to the other, as well.

So in this sense, the two programs are equivalent. (They don't have the same feasible region, though; not only is the second program higher-dimensional, but it also does have feasible points that don't correspond to feasible points of the first program.)

Some nitpicks:

  • The first problem is not a linear program, since the objective function isn't linear (it has $\max$ in it). It may be equivalent to a linear program, but that's technically not the same thing.
  • If $A$ is not a polyhedron, then neither problem is a linear program. Actually, $a \in A$ should be phrased as a set of constraints on $a \in \mathbb R^n$ (which are hopefully linear constraints).
  • If $B$ or $C$ is infinite, then neither problem is a linear program: the second problem would then have infinitely many constraints. This can sometimes be avoided by only including a constraint for every extreme point of $B$ and $C$, in the second problem - if there are finitely many of those.
  • In any case, the second problem should be written as a $\min$ over $(a, z_1, z_2)$, not just as a $\min$ over $a$.

Even if you are already aware of these, I want to mention them for any future readers.

Related Question