17
$\begingroup$

I am solving two-stage optimization problems in the form of $$\max_{x \in X}\min_{y \in Y} f(x,y),$$ where $f(x,y)$ is the solution of a mixed integer linear program (MIP). As the constraints of the MIP link the $x$ and $y$ elements, it is clear that we cannot apply the classic minimax theorem to interchange the minimization and the maximization. (Actually, I am solving a trilevel optimization problem and interchanging the minimization and the maximization will be very helpful).

We all know that the minimax theorem states that $$\max_{x \in X}\min_{y \in Y} f(x,y) \leq \min_{y \in Y}\max_{x \in X} f(x,y)$$ for any function $f$ mapping the $X,Y$ space to a real set (assuming the max and min can be attained).

My question is the following: In the above sketched case, this equation will not be strict (i.e., it won't hold with equality). However, are there any particular useful results on how large this gap might be, both worst-case as well as numerically? If it is not too big (in general), it might suffice as a bound on the larger (and not relevant for this question) trilevel optimization problem.

$\endgroup$
  • 2
    $\begingroup$ You could try thinking about the Shapley-Folkmann lemma; this paper might be a place to start: web.stanford.edu/~boyd/papers/pdf/duality_bound.pdf. $\endgroup$ – Ryan Cory-Wright May 31 '19 at 13:49
  • 1
    $\begingroup$ This doesn’t answer your question but FWIW the gap can be arbitrarily large in general: $f(x,y)=M\sin(x+y)$ for arbitrarily large $M$. $\endgroup$ – David M. Jun 14 '19 at 3:36
  • 2
    $\begingroup$ Shouldn't it be $\displaystyle\max_{x \in X}\min_{y \in Y} f(x,y) \leq \min_{y \in Y}\max_{x \in X} f(x,y)$ instead of $ \min\limits_{x \in X}\max\limits_{y \in Y} f(x,y)$ on the right hand side? $\endgroup$ – YukiJ Jun 14 '19 at 9:28
  • $\begingroup$ Yes, of course! Changed $\endgroup$ – Albert Schrotenboer Jun 14 '19 at 9:45
  • 2
    $\begingroup$ Conventionally, $\min\limits_{y\in\emptyset}h(y)=+\infty$ and $\max\limits_{x\in\emptyset}h(x)=-\infty$. So unless you know that the problem defining $f()$ is feasible for all $(x,y)\in X\times Y$, you may find that the max-min problem has value $+\infty$ (because some $x\in X$ makes the minimization problem infeasible) and/or the min-max problem has value $-\infty$ (because some $y\in Y$ makes the maximization problem infeasible). $\endgroup$ – prubin Aug 18 '19 at 15:15
4
$\begingroup$

While these equations have many interpretations in OR (e.g. robust optimization), in this case I like to understand what happens here using a Game Theory perspective. These two equations can be interpreted as a Stackelberg game, sometimes referred two as leader follower games. Consider a two player zero sum game, where player 1 has to pick an element from $X$ maximizing the outcome and player 2 has to pick an element from $Y$ minimizing the outcome. Let's say we have the following game matrix where $X$ is the set of rows and $Y$ is the set of columns: $$\left[ \begin{array}{cc} a & 0 \\ 0 & b \end{array} \right]$$ We assume w.l.o.g. that $a > b > 0$. Now we have that $$\max_{x\in X}\min_{y \in Y} f(x,y) = 0$$ as this corresponds to the situation where player 1 picks first and player 2 responds, and player 2 can always choose the column such that the outcome is $0$. On the right hand side, we get $$\min_{y \in Y}\max_{x \in X} f(x,y) = b$$ as now player 2 gets to pick first and player 1 responds. Obviously, player 2 prefers $b$ over $a$, but can't prevent the first player from getting a positive outcome. Since we can pick $a$ and $b$ arbitrarily large, this gap is clearly unbounded, both in a relative and absolute sense.

These kind of problems are particularly nasty if you are not able to exploit any special structure of your function, which is only possible if you are somewhat lucky, e.g. you can apply a strong duality results somewhere or have additional information that you can use to bound $f$. In fact, these problems are widely believed to be more difficult than NP-hard problems. Gerhard Woeginger gave a really good keynote on the difficulty of these multilevel problems at EURO2018 in Valencia from a computational complexity perspective (he talks mostly about universal and existential quantors, but the idea is the same). He mentions a few rare cases where you end up being lucky, and others where basically no-one knows what to do. There is a video available on the EURO2018 website.

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