Alternating Proximal Algorithms for Weakly Coupled Convex Minimization Problems. Applications to Dynamical Games and PDE's

H. Attouch ; J. Bolte ; P. Redont ; A. Soubeyran

Journal of convex analysis, Tome 15 (2008) no. 3, pp. 485-506

Résumé

\newcommand{\R}{{\mathbb R}} \newcommand{\X}{\mathcal X} \newcommand{\Y}{\mathcal Y} \newcommand{\xku}{x_{k+1}} \newcommand{\yku}{y_{k+1}} We introduce and study alternating minimization algorithms of the following type $$\begin{array}{c} (x_0,y_0)\in\X\times\Y,\: \alpha,\mu,\nu>0\mbox{ given},\\ \rule{0pt}{12pt} (x_k,y_k)\rightarrow(\xku,y_k)\rightarrow(\xku,\yku)\mbox{ as follows} \\ \rule{0pt}{12pt} \left\{\begin{array}{l} \xku=\mbox{argmin} \{f(\xi)+\frac{\mu}{2}Q(\xi,y_k)+ \frac{\alpha}{2}\parallel\xi-x_k\parallel^2:\ \xi\in\X\}\\ \rule{0pt}{12pt} \yku=\mbox{argmin} \{g(\eta)+\frac{\mu}{2}Q(\xku,\eta)+\frac{\nu}{2} \parallel\eta- y_k\parallel^2:\ \eta\in\Y\} \end{array}\right. \end{array}$$ where $\X$ and $\Y$ are real Hilbert spaces, $f:\X\to\R\cup\{+\infty\}$, $g:\Y\to\R\cup\{+\infty\}$ are closed convex proper functions, $Q:(x,y)\in\X\times\Y\to\R^+$ is a nonnegative quadratic form (hence convex, but possibly nondefinite) which couples the variables $x$ and $y$. A particular important situation is the ``weak coupling'' $Q(x,y)=\parallel Ax-By\parallel^2$ where $A\in L(\X,\mathcal Z)$, $B\in L(\Y,\mathcal Z)$ are continuous linear operators acting respectively from $\X$ and $\Y$ into a third Hilbert space $\mathcal Z$. \par The ``cost-to-move'' terms $\parallel\xi-x\parallel^{2}$ and $\parallel\eta-y\parallel^{2}$ induce dissipative effects which are similar to friction in mechanics, anchoring and inertia in decision sciences. As a result, for each initial data $(x_0,y_0)$, the proximal-like algorithm generates a sequence $(x_k,y_k)$ which weakly converges to a minimum point of the convex function $L(x,y)=f(x)+g(y)+\frac{\mu}{2}Q(x,y)$. The cost-to-move terms, which vanish asymptotically, have a crucial role in the convergence of the algorithm. A direct alternating minimization of the function $L$ could fail to produce a convergent sequence in the weak coupling case. \par Applications are given in game theory, variational problems and PDE's. These results are then extended to an arbitrary number of decision variables and to monotone inclusions.

Détail

Classification : 65K05, 65K10, 46N10, 49J40, 49M27, 90B50, 90C25
Mots-clés : Convex optimization, alternating minimization, splitting methods, proximal algorithm, weak coupling, quadratic coupling, costs to change, anchoring effect, dynamical games, best response, domain decomposition for PDE's, monotone inclusions