I'm reading a paper on solving an optimization problem for a non-convex function. This paper is suggesting a method using a game theoretic approach:
Optimizing the Lagrangian can be interpreted as playing a two-player zero-sum game: the first player chooses $\theta$ to minimize $L(\theta, \lambda)$, and the second player chooses $\lambda$ to maximize it.
where $\theta$ is model parameter and $\lambda$ is Lagrangian multiplier. I was wondering if you could interpret the following for me:
Figure shows a case in which a pure Nash equilibrium of the Lagrangian game does not exist. The plotted rectangular region is the domain $\Theta$, the contours are those of the strictly concave minimization objective function $g_0$, and the shaded triangle is the feasible region determined by the three linear inequality constraints $g_1, > \dots, g_3$. The red dot is the optimal feasible point. The Lagrangian $L(\theta, \lambda)$ is strictly concave in $\theta$ for any choice of $\lambda$, so the optimal choice(s) for the $\theta$-player will always lie on the boundary of the plotted rectangle. However, these points are infeasible, and therefore suboptimal for the $\lambda$-player.
I attempted to decipher this starting with the Nash equilibrium, what it means in this context, and how is that different from pure Nash equilibrium.
A Nash Equilibrium is a stable pair of strategies (could be randomized). Stable means that neither player has incentive to deviate on their own.
How is this different from
A pure Nash equilibrium is a strategy profile in which no player would benefit by deviating, given that all other players don't deviate