Journal of Convex Analysis 15 (2008), No. 3, 485--506
Copyright Heldermann Verlag 2008
Alternating Proximal Algorithms for Weakly Coupled Convex Minimization Problems. Applications to Dynamical Games and PDE's
Hedy Attouch
Inst. de Mathématiques et de Modélisation, UMR CNRS 5149, CC 51, Université Montpellier II, Place Eugène Batallion, 34095 Montpellier, France
attouch@math.univ-montp2.fr
Jérôme Bolte
Equipe Combinatoire et Optimisation, Université Paris 6, Place Jussieu, 75252 Paris, France
bolte@math.jussieu.fr
Patrick Redont
Inst. de Mathématiques et de Modélisation, UMR CNRS 5149, CC 51, Université Montpellier II, Place Eugène Batallion, 34095 Montpellier, France
redont@math.univ-montp2.fr
Antoine Soubeyran
GREQAM UMR CNRS 6579, Université de la Méditerranée, 13290 Les Milles, France
antoine.soubeyran@univmed.fr
[Abstract-pdf]
\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.
Keywords: 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.
MSC: 65K05, 65K10, 46N10, 49J40, 49M27, 90B50, 90C25
[ Fulltext-pdf (208 KB)] for subscribers only.