2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Also posted here: math.stackexchange.com/q/3592868/10063 $\endgroup$
    – becko
    Mar 24, 2020 at 13:35
  • $\begingroup$ Why the close vote? $\endgroup$
    – becko
    Mar 24, 2020 at 19:39
  • $\begingroup$ 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? $\endgroup$ Mar 26, 2020 at 12:59
  • $\begingroup$ @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). $\endgroup$
    – becko
    Mar 26, 2020 at 14:01
  • $\begingroup$ 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. $\endgroup$
    – becko
    Mar 26, 2020 at 14:03

1 Answer 1

1
$\begingroup$

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.

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