I asked this question because I have trouble for taking a straight forward approach to find the equilibrium of a min-max problem. For example, consider the unconstrained optimization problem: $$ \inf_x\sup_y x^TAy+b^Tx+c^Ty+d $$
1- How can we show that if the equilibrium exist?
2- If exists, is there any closed form to represent it?
3- Can gradient descent help us to reach an equilibrium?
4- If so, seems we need two update rules for both $x$ and $y$ to reach equilibrium?
5- Is equilibrium always saddle point?
6- If so, all min-max problem have saddle point?
7 - If so, what is the standard way to reach them?
8- Why this function is convex with respect to $x$ and concave with respect to $y$?
I partly know about optimization but this is the intersection of game theory and optimization which I do not know much about it. For whom knows game theory well my questions might be obvious but I ask you to answer them in the context of optimization theory and flavor it by game theory.
Maybe considering the problem with simpler objective be helpful so consider the following
$$ \inf_x\sup_y x^TAy $$
I just know that the gradient updates are as follows
$$ x_{t+1} = x_t - \eta Ay $$
$$ y_{t+1} = y_t + \eta A^Tx $$
where $Ay$ is the gradient with respect to $x$ and $A^Tx$ is the gradient with respect to $y$ and $\eta$ is the step size. Also, we have $-$ for $x$-update because we want to decrease the value and $+$ for $y$-update because we want to increase the value.
I do not understand why still gradient method works?
Also, if $y$ is in the null space of $A$, $y \in \mathcal{N}(A)$ and $x$ is in the null space of $A^T$, $x \in \mathcal{N}(A^T)$ we have equilibrium because neither $x$ nor $y$ change.
I hope addressing all my questions separately help me to better understand this concept.
The problem is $$\inf_x\sup_y x^TAy+b^Tx+c^Ty+d = \inf_x g(x)$$ with $$g(x)=\sup_y (A^Tx+c)^Ty+b^Tx+d=\begin{cases}b^Tx+d &\text{if } A^Tx+c=0\\ \infty & \text{otherwise.}\end{cases}$$ Therefore, the problem simplifies to $\inf_x \{b^Tx+d : A^Tx+c=0\}$. This is an ordinary linear optimization problem, which can be solved with the simplex algorithm.