# When does $\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$ hold for a real function $f(x,y)$?

Let $$f(x,y)$$ be a real function of the variables $$x,y$$ (which can be real vectors). Under what conditions do we have the following equality:

$$\min_x \max_yf(x,y) = \min_y \max_x f(x,y)$$

For example, this equality is true if $$f(x,y) = xy$$ and $$x,y$$ are real scalars.

Note that this is not the same as Von Neumann's minimax theorem (https://en.wikipedia.org/wiki/Minimax_theorem), because here the role of the variables is exchanged (e.g., $$x$$ is minimized on the left-hand side, but it is maximized on the right-hand side).

Though I do not know if convexity/concavity of $$f(x,y)$$ with respect to either arguments plays a role here (like it does for Von Neumann's minimax), I am using the convex-related tags here since that's the context where I've seen related questions. Similarly I am tagging game-theory, though I'm not sure it's directly applicable.

I also expect that the a condition for this equality to be true is that the saddle-points of both sides of the equation be attained at points where the gradient of $$f$$ vanishes (see my answer below).

• Also posted here: math.stackexchange.com/q/3592868/10063 Mar 24, 2020 at 13:35
• Why the close vote? Mar 24, 2020 at 19:39
• It's a slightly strange question, since for example the equality wouldn't even hold for $ax+by$ in $[0,1]\times [0,1]$ (unlike the Minimax Theorem). Any particular reason why you are interested in this? Mar 26, 2020 at 12:59
• @YaakovBaruch I have a variational formulation of a certain statistical mechanics problem, where I derive an optimization like one side of this equation, but where it would make a lot of sense physically that the optimization were like the other side. I need to understand when both sides are equal, because if they are not it would be potentially interesting. Numerically I find they typically are equal (but this could be because I am only looking at the points where the derivative are zero). Mar 26, 2020 at 14:01
• In your example $ax+by$, the saddle occurs at the boundary of the domain, where the gradient of $f$ need not be zero. I do not expect my equality to hold in that case. Mar 26, 2020 at 14:03

Here is a tentative proof, under some assumptions. Would like to see some additional arguments (or counterexamples) to make this clearer.

Assumptions:

1. We suppose that $$f(x,y)$$ is concave in $$y$$ for all $$x$$.
2. That the equation $$\partial f/\partial y=0$$ has a unique solution $$x$$ for every $$y$$.
3. That the solution to both saddle-point optimizations is attained at a point where $$\partial f/\partial x = \partial f/\partial y = 0$$.

Proof:

Then finding $$\max_y f(x,y)$$ is equivalent to $$\partial f/\partial y = 0$$. It follows that the original problem is equivalent to a constrained minimization over all variables:

\begin{aligned} \min_x \max_y f(x,y) &= \min_{x,y} f(x,y) \quad \left(\text{subject to }\frac{\partial f}{\partial y}=0\right) \\ &= \min_y \min_x f(x,y) \quad \left(\text{subject to }\frac{\partial f}{\partial y}=0\right) \end{aligned}

where we simply changed the order of the minimizations. Since there is a unique $$x$$ that makes $$\partial f/\partial y=0$$ for any $$y$$, the inner minimization on $$x$$ is trivial, and can be formally changed to a maximization:

\begin{aligned} \min_x \max_y f(x,y) &= \min_y \max_x f(x,y) \quad \left(\text{subject to }\frac{\partial f}{\partial y}=0\right) \end{aligned}

Finally, if the unconstrained version of the right-hand side optimization is solved at a point where $$\partial f/\partial y=0$$ (this assumption 3 above), then the constrain can be ignored:

$$\min_y \max_x f(x,y) = \min_y \max_x f(x,y) \quad \left(\text{subject to }\frac{\partial f}{\partial y}=0\right)$$

In this case, we obtain:

$$\min_x \max_y f(x,y) = \min_y \max_x f(x,y)$$

as desired.