×

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
PDF BibTeX XML Cite
Full Text: EuDML