computational strategy for solving convex-concave minmax problem

Question

Assume f(x,y) is convex in $x$ and concave in $y$. Then \begin{equation}\min_x \max_y f(x,y)\end{equation} is globally solvable, because f is convex in x (max of convex is convex.) But can we find a globally optimal $x$ with coordinate descent? (aka alternating: i.e Fix x, find optimal y. Fix $y$ find optimal $x$ till convergence.) Why or why not?

Answer 1

Try an example: $f(x,y) = x y$. The optimal solution is $(x,y)=(0,0)$. If you allow all real values of $x$ and $y$, then for fixed $x \ne 0$ there is no optimal $y$. But let's say you restrict to a bounded domain, $-1 \le x \le 1$, $-1 \le y \le 1$. The optimal $y$ for $x=1$ is $1$. The optimal $x$ for $y=1$ is $-1$. The optimal $y$ for $x=-1$ is $-1$. The optimal $x$ for $y=-1$ is $1$. And so your procedure cycles.