A New Class of Alternating Proximal Minimization Algorithms with Costs-to-Move

摘要: Given two objective functions $f:\mathcal X\mapsto\R\cup\{+\infty\}$ and $g:\mathcal Y\mapsto\R\cup\{+\infty\}$ on abstract spaces $\mathcal X$ Y$, a coupling function $c:\mathcal X\times\mathcal Y\mapsto\R^+$, we introduce study alternative minimization algorithms of the following type: $(x_0,y_0)\in\mathcal Y \mbox{ given; } (x_n,y_n)\rightarrow(x_{n+1},y_n)\rightarrow(x_{n+1},y_{n+1}) as follows: }\ \left\{\begin{array}{l} x_{n+1}\in\mbox{argmin} \{f(\xi)+\beta_n c(\xi,y_n)+\alpha_n h(x_n,\xi): \xi\in\mathcal X\},\ y_{n+1}\in\mbox{argmin} \{g(\eta)+\mu_n c(x_{n+1},\eta)+\nu_n k(y_n,\eta): \eta\in\mathcal Y\}. \end{array}\right.$ Their most original feature is introduction terms $h:\mathcal X\mapsto\R^+$ $k:\mathcal Y\times\mathcal Y\mapsto\R^+$ which are costs to change or move (distance-like functions, relative entropies) accounting for various inertial, friction, anchoring effects. These studied in general framework. The $h$ $k$ leads proximal minimizations with corresponding dissipative As result, enjoy nice convergent properties. Coefficients $\alpha_n$, $\beta_n$, $\mu_n$, $\nu_n$ nonnegative parameters. When taking $\alpha_n=\nu_n=0$ quadratic Hilbert space, one recovers classical alternating algorithm, itself natural extension projection algorithm von Neumann. A number new significant results hold metric spaces. We pay particular attention cases: (1.) $(\mathcal X,d_{\mathcal X})$ Y,d_{\mathcal Y})$ complete $h\geq d_{\mathcal X}$, $k\geq Y}$ (“high local move”); then provide sequences that converge Nash equilibria. (2.) X=\mathcal Y=\mathcal H$ (“low move”) $f,g:\mathcal H\mapsto\R\cup\{+\infty\}$ closed, convex, proper; some convergence theorems convex algorithms, including those Acker Prestel, properly extended proofs.