0

I'm dealing with an optimization problem of the form

$$\underset{x,y}{\text{min}}\ f(x,y)$$

but I'm having trouble finding a good reference on how to deal with this. Through Google searches, I think I've found that a problem like this can be decomposed into

$$\underset{x}{\text{min}}\left[ \underset{y}{\text{min}}\ f(x,y)\right]$$

but it's not clear to me why this would be equivalent in general. Are there conditions when this would be true or is it always true? Is this the standard way forward with a problem like this? I would be grateful if someone could prove to me why this is true, if it is true.

rbell
  • 453
  • If you've been through calculus, the only requirements for finding mini-max is that $f_x = 0$ and $f_y = 0$. The decomposition is just finding the zero of $f_y$ before moving on to $f_x$ it seems. – Christopher Marley May 31 '18 at 01:14
  • Of course, there are functions like $z=x^2-y^2$ that have no zeroes. Only a saddle point. For all continuous and differentiable functions, it seems like your method should work. I have no way to prove it though. – Christopher Marley May 31 '18 at 01:15
  • Suppose the minimum of the first problem is attained at a particular $(x^,y^)$. You can argue that the optimal solution of the second problem is no better than that of the first problem (since the inner minimization considers a fixed $x$). Finally, you can note that when you fix $x$ to $x^$ in the inner problem, $y = y^$ is feasible for the inner minimization. – madnessweasley May 31 '18 at 05:23

1 Answers1

0

Moving @madnessweasley's comment to the answer section and modify a little bit.

The statement is always true. The general idea is to iteratively show that doing two $\min$ gives you a value that is $\leq$ than everything else. Since solution to the first problem gives you a value also $\leq$ than everything else, they have to be equivalent.

Let $y^{\ast} = \arg \min_y f(x,y)$, then $ f(x,y^{\ast}) \leq f(x,y), \forall y$. Similarly, you have that $f(x^{\ast}, y^{\ast}) \leq f(x,y^{\ast}), \forall x$. Therefore $\min_x \min_y f(x,y) \leq f(x,y), \forall x,y$, including solution to the first problem (call it $f(x^{\star}, y^{\star}$).

To complete the proof, argue that solution to 1st problem is also $\leq$ than everything, including solution to the 2nd problem. Therefore they have to be the same.

Btw, seem to be a duplicate question but I can't seem to find the other source.

Tingkai Liu
  • 130
  • 1
  • 8