I have a minimax problem of the form $$\max_{\substack{u_1,\dots,u_n \ge 0 \\ u_1+\dots+u_n = 1}} \min_{\substack{v_1,\dots,v_m \ge 0 \\ v_1+\dots+v_m = 1 \\ v_{j_1} \le v_{j_2} \hspace{1mm} \forall (j_1,j_2) \in J}} \sum_{i=1}^n \sum_{j=1}^m c_{i,j} u_i v_j,$$ where $J$ is some (given) subset of $[m]\times[m]$ and each $c_{i,j} \in \{0,1\}$ (is given).

So it's a normal kind of minimax problem, except we have some inequalities amongst the $v_j$'s.

By the minimax theorem, there are $u^* = (u_i^*)_{i=1}^n, v^* = (v_j^*)_{j=1}^m$ that are ``best responses" to one another.

Let's assume our problem is such that there is only one such $u^*$.

Question: How can I quickly (in practice, on a computer) find $u^*$?

The values of $n$ and $m$ I am working with are actually very small (e.g. $n \le 7, m \le 14$). However, Mathematica seemingly takes forever to compute the minimax, even with $n=2,m=4$.

Using Mathematica, I can find (some) $v^*$ rather quickly by interchanging the max and the min, and then noting that the max of the double sum over the possible $(u_i)_{i=1}^n$'s is simply a max of the double sum over the $n$ tuples $(u_i)_{i=1}^n$ with exactly one $1$ (and the rest $0$). However, this doesn't help me find $u^*$.

I'd appreciate any advice. Thanks!

  • $\begingroup$ Can you share the code you have so far? $\endgroup$
    – MarcoB
    Jul 11, 2022 at 19:49
  • $\begingroup$ Here's the code for the example that seemingly takes forever. Apologies if it is very stupid. Maximize[{Minimize[{u0*(v1 + v3) + u1*(v2 + v3), v0 >= 0, v1 >= 0, v2 >= 0, v3 >= 0, v0 <= v1, v0 <= v2, v1 <= v3, v2 <= v3, v0 + v1 + v2 + v3 == 1}, {v0, v1, v2, v3}][[1]], u0 >= 0, u1 >= 0, u0 + u1 == 1}, {u0, u1}] $\endgroup$ Jul 11, 2022 at 20:46
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/152922/755, mathematica.stackexchange.com/q/270651/40712. Please do not post the same question on multiple sites. Which site do you think is most appropriate for this question? $\endgroup$
    – D.W.
    Jul 12, 2022 at 3:51
  • $\begingroup$ Check this MSE thread or any of several others that can be found by searching for "bilevel optimization". $\endgroup$ Jul 12, 2022 at 15:22
  • $\begingroup$ @DanielLichtblau Thanks a lot! Adding a separate function with the "?NumericQ" helped! The only issue now is that, with that separate function successfully defined with Minimize (not NMinize), I can only do NMaximize of that function instead of Maximize. Is there any way to do Maximize? I want to find the optimal maximizer, not just a numeric approximation. Thanks. $\endgroup$ Jul 13, 2022 at 19:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.