Abstract

We introduce and study alternating minimization algorithms of the following type (x0,y0)∈X×Y, α,μ,ν>0 given,(xk,yk)→(xk+1,yk)→(xk+1,yk+1) as follows{xk+1=argmin{f(ξ)+μ2Q(ξ,yk)+α2∥ξ−xk∥2: ξ∈X}yk+1=argmin{g(η)+μ2Q(xk+1,η)+ν2∥η−yk∥2: η∈Y}\begin{array}{c} (x_0,y_0)\in\X\times\Y,\: \alpha,\mu,\nu>0\text{ given},\\ \rule{0pt}{12pt} (x_k,y_k)\rightarrow(\xku,y_k)\rightarrow(\xku,\yku)\text{ as follows} \\ \rule{0pt}{12pt} \left\{\begin{array}{l} \xku=\text{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=\text{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\X and Y\Y are real Hilbert spaces, f:X→R∪{+∞}f:\X\to\R\cup\{+\infty\}, g:Y→R∪{+∞}g:\Y\to\R\cup\{+\infty\} are closed convex proper functions, Q:(x,y)∈X×Y→R+Q:(x,y)\in\X\times\Y\to\R^+ is a nonnegative quadratic form (hence convex, but possibly nondefinite) which couples the variables xx and yy. A particular important situation is the ``weak coupling'' Q(x,y)=∥Ax−By∥2Q(x,y)=\parallel Ax-By\parallel^2 where A∈L(X,Z)A\in L(\X,\mathcal Z), B∈L(Y,Z)B\in L(\Y,\mathcal Z) are continuous linear operators acting respectively from X\X and Y\Y into a third Hilbert space Z\mathcal Z. The ``cost-to-move'' terms ∥ξ−x∥2\parallel\xi-x\parallel^{2} and ∥η−y∥2\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 (x0,y0)(x_0,y_0), the proximal-like algorithm generates a sequence (xk,yk)(x_k,y_k) which weakly converges to a minimum point of the convex function L(x,y)=f(x)+g(y)+μ2Q(x,y)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 LL could fail to produce a convergent sequence in the weak coupling case. 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.

Author information

Contact details are reproduced from the original publication and may be historical.

Hedy Attouch

Inst. de Mathématiques et de Modélisation, UMR CNRS 5149, CC 51, Université Montpellier II, Place Eugène Bataillon, 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 Bataillon, 34095 Montpellier, France

redont@math.univ-montp2.fr

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

Mathematics Subject Classification

65K05, 65K10, 46N10, 49J40, 49M27, 90B50, 90C25

References

  1. F. Acker, M.-A. Prestel: Convergence d’un schéma de minimisation alternée, Ann. Fac. Sci. Toulouse, V. Ser., Math. 2 (1980) 1–9.https://doi.org/10.5802/afst.541Google Scholar
  2. H. Attouch: Variational Convergence for Functions and Operators, Applicable Mathematics Series, Pitman, London (1984).Google Scholar
  3. H. Attouch, G. Buttazzo, G. Michaille: Variational Analysis in Sobolev and BV Spaces. Applications to PDEs and Optimization, MPS/SIAM Series on Optimization 6, SIAM, Philadelphia (2006).https://doi.org/10.1137/1.9780898718782Google Scholar
  4. H. Attouch, P. Redont, A. Soubeyran: A new class of alternating proximal minimization algorithms with costs-to-move, SIAM J. Optim. 18 (2007) 1061–1081.https://doi.org/10.1137/060657248Google Scholar
  5. H. Attouch, A. Soubeyran: Inertia and reactivity in decision making as cognitive variational inequalities, J. Convex Analysis 13 (2006) 207–224.https://doi.org/10.68381/jca13022Google Scholar
  6. H. Attouch, A. Soubeyran: A worthwhile to move approach of satisficing with not too much sacrificing, J. Math. Psychol., submitted.Google Scholar
  7. H. H. Bauschke, P. L. Combettes, D. Noll: Joint minimization with alternating Bregman proximity operators, Pac. J. Optim. 2(3) (2006) 401–424.Google Scholar
  8. H. H. Bauschke, P. L. Combettes, S. Reich: The asymptotic behavior of the composition of two resolvents, Nonlinear Anal., Theory Methods Appl. 60A (2005) 283–301.https://doi.org/10.1016/j.na.2004.07.054Google Scholar
  9. H. Brézis: Opérateurs maximaux monotones dans les espaces de Hilbert et équations d’évolution, Lecture Notes 5, North-Holland, Amsterdam (1972).Google Scholar
  10. C. Camerer, G. Loewenstein: Behavioral economics: past, present, future, in: Advances in Behavioral Economics, C. Camerer, G. Loewenstein, M. Rabin (eds.), Princeton University Press, Princeton (2003) 3–51.https://doi.org/10.1515/9781400829118-004Google Scholar
  11. P. L. Combettes: The foundations of set theoretic estimation, Proc. IEEE 81 (1993) 182–208.https://doi.org/10.1109/5.214546Google Scholar
  12. D. Kahneman: Maps of bounded rationality: psychology for behavioral economics, Amer. Econ. Rev. (2003) 1449–1475.https://doi.org/10.1257/000282803322655392Google Scholar
  13. J.-L. Lions: Contrôle des Systèmes Distribués Singuliers, Gauthier-Villars, Paris (1983).Google Scholar
  14. J. von Neumann: Functional Operators. Vol. II. The Geometry of Orthogonal Spaces, Annals of Mathematics Studies 22, Princeton University Press, Princeton (1950).Google Scholar
  15. Z. Opial: Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc. 73 (1967) 591–597.https://doi.org/10.1090/S0002-9904-1967-11761-0Google Scholar
  16. H. Simon: A behavioral model of rational choice, Quart. J. Econ. 69 (1975) 99–118.https://doi.org/10.2307/1884852Google Scholar
  17. P. Le Tallec: Domain decomposition methods in computational mechanics, Comput. Mech. Adv. 1(2) (1994) 121–220.Google Scholar
  18. T. Ui: A Shapley value representation of potential games, Games Econ. Behav. 31 (2000) 121–135.https://doi.org/10.1006/game.1999.0729Google Scholar

Suggested citation

H. Attouch, J. Bolte, P. Redont, A. Soubeyran. “Alternating Proximal Algorithms for Weakly Coupled Convex Minimization Problems. Applications to Dynamical Games and PDE's.” Journal of Convex Analysis 15 (2008), No. 3, 485–506. https://doi.org/10.68381/jca15035

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2008. Rights now held by Banach Press LLC.