# How to find optimizers with computer in this kind of minimax problem

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!

• Can you share the code you have so far? Jul 11 at 19:49
• 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}][], u0 >= 0, u1 >= 0, u0 + u1 == 1}, {u0, u1}] Jul 11 at 20:46
• 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?
– D.W.
Jul 12 at 3:51
• Check this MSE thread or any of several others that can be found by searching for "bilevel optimization". Jul 12 at 15:22
• @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. Jul 13 at 19:54