zbMATH — the first resource for mathematics

Verification of the convergence of Brown’s method for convex-concave functions by means of the Lyapunov function. (Russian) Zbl 0766.90093
The problem of finding a saddle point $$(x^*,y^*)\in X\times Y$$ for a strictly convex-concave continuous function $$F(x,y)$$ on a convex compact $$X\times Y$$ is considered. Brown’s method for solving the problem generates sequences $$\{x_ n,y_ n\}$$, $$\{\tilde x_ n,\tilde y_ n\}$$ where $x_{n+1}=\varphi(\tilde y_ n),\;y_{n+1}=\psi(\tilde x_ n),\;\tilde y_ n={1\over n}\sum^ n_{k=1} y_ k,\;\tilde x_ n={1\over n}\sum^ n_{k=1} x_ k,$
$\varphi(y)=\arg\min_{x\in X} F(x,y),\quad\psi(y)=\arg \min_{y\in Y} F(x,y).$ The following main result is proved: $$\lim_{n\to \infty} \tilde x_ n=x^*$$, $$\lim_{n\to\infty} \tilde y_ n=y^*$$.
For the case of a convex-concave function $$F(x,y)$$ and set-valued mappings $$\varphi(y)$$, $$\psi(x)$$, sufficient additional conditions are given which guarantee the convergence of $$\{\tilde x_ n,\tilde y_ n\}$$ to the set of saddle points of $$F(x,y)$$ on $$X\times Y$$.
MSC:
 91A05 2-person games
Full Text: